今日主题:栈、队列、递归
栈(STACK)
栈是一种线性结构,他只能从一端放入元素,也只能从这一端出来,拥有先进后出的特点(FILO)(First In Last out)
手写栈
手写栈是用数组模拟栈,是使用栈的一种方法(也是最累的一种,所以别用
栈有一些操作,包括:
1. 入栈
2. 栈顶元素获取
3. 出栈
4. 判空
5. 获得栈大小
手写栈初始化:
1.入栈:
2.栈顶元素获取
3.出栈
4.判空
if(top == 0)
这个就是判空
5.获得栈的大小:
top-1
栈的大小
STL封装的STACK
定义:STACK<数据类型>栈名称
这里以stack<int>stk;为例
入栈:STK.PUSH(入栈元素);
出栈:STK.POP();
栈顶元素:STK.TOP();
判空:STK.EMPTY();
栈的大小:STK.SIZE();
个人出的练习题可以来做一下题目链接
队列(QUEUE)
队列是一种线性结构他只能从一端入,另一端出,并且拥有先进先出(FIFO)(First in First out)
手写队列
手写队列是用数组模拟队列的一种写法,拥有以下几个操作
1. 入队
2. 出队
3. 判空
4. 获得队首元素
5. 队列的大小
手写队列初始化:
1.入队:
2.出队:
3.判空:
4.获取队首元素
获得队列大小:REAR-FRONT;(懒得改了)
STL 封装的队列
这里假装定义一个int类型的队列que
1. 定义方式queue<int>que;
2. 入队que.push();
3. 出队que.pop();
4. 判空que.empty();
5. 获取队首元素que.front()
6. 获得队列大小que.size()
这个是我自己的练习题目题目链接
递归
递归是指通过被定义对象的自身来为其下定义,即自我复制的定义方式。这种方法在数理逻辑和计算机科学中尤为常见,其本质是将复杂问题分解为与原问题相似但规模更小的子问题,通过逐步解决子问题最终完成整体求解。
递归两要素:
1. 递归边界
2. 调用自身(递归式)
例子:
从前有座山,山里有座庙,庙里有个老和尚给小和尚讲:“从前有座山,山里有座庙,庙里有个...”直到讲到有个“老和尚”不想讲了,就一层一层回来。
递归是自上而下的考虑问题,递归其实并没有什么技巧,多练就好了