stack

栈（stack）是一种遵循先入后出（FILO）逻辑的线性数据结构。其只能从容器的一端进行元素的插入与提取操作。

我们可以把他比作串串，我们在串肉的时候都是从底依次往上串肉，然后在吃的时候是从串顶依次向下吃，将串上的肉比作各种类型的元素（如整数、字符、对象等），串子比作适配器容器，就得到了栈这种数据结构。

如图所示，我们把容器内元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。（图片取自hello算法）

栈的常用操作

成员函数	功能
empty()	判断栈是否为空，空返回真，不为空返回假
size()	获取栈中有效元素个数，返回值为size_t
top()	获取栈顶元素
push()	元素入栈
pop()	元素出栈
swap()	交换两个栈中的数据（可以部分也可以交换全部）

其实在c语言中就已经存在了stack，但是c++后又引入了模板，所以c++STL标准库里面就存在了stack的模板，但是要需要引用头文件#include<stack> 

#include<iostream>
#include<stack>
using namespace std;int main()
{stack<int> st;// 元素入栈st.push(1);st.push(3);st.push(2);st.push(5);st.push(4);//访问栈顶元素 int top = st.top();// 元素出栈 st.pop(); // 无返回值// 获取栈的长度 int size = st.size();// 判断是否为空 bool empty = st.empty();return 0;
}

可视化监视： 

 栈的实现：

 以下是基于deque实现栈的示例代码：

deque就是双向队列；

如果不是很了解可以看这篇文章：C++中deque的用法（超详细，入门必看）_c++ deque-CSDN博客

需要补充的一点就是deque底层是不连续的数组构成，他是又多个连续的小子数组组成。

    template<class T, class Con = deque<T>>class stack{public:stack(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top()const{return _c.back();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};

那么如果用链表怎么来实现呢？

下面是基于链表实现stack：

    template<class T>struct stack_node{stack_node(const T& _val):next(nullptr), val(_val){}stack_node* next;T val;};template<class T>class stack{public:stack(){stackTop = nullptr;stkSize = 0;}~stack(){delete[]stackTop;stackTop = nullptr;stkSize = 0;}int size(){return stkSize;}bool empty(){return size() == 0;}void push(int num){stack_node<T>* node = new stack_node<T>(num);node->next = stackTop;stackTop = node;stkSize++;}int pop(){assert(!empty());int num = top();stack_node<T>* tmp = stackTop;stackTop = stackTop->next;// 释放内存delete tmp;stkSize--;return num;}int top(){assert(!empty());return stackTop->val;}private:stack_node<T>* stackTop; // 将头节点作为栈顶int stkSize;        // 栈的长度};

同样还存在着用数组来实现栈

class stack{public:int size() {return stack.size();}bool empty() {return stack.size() == 0;}void push(int num) {stack.push_back(num);}int pop() {int num = top();stack.pop_back();return num;}int top() {assert(!empty());return stack.back();}private:vector<int> stack;}
};

三种实现方法的对比：

三种实现对此来说第一种实现是标准库的标准实现方法，二三都是我们自己可以通过自己思考可以想出来的实现方法，两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。

首先第三种方法的缺点之一就是如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为0（n）；

缺点二就是方法三在扩容上会存在大量的浪费空间，比如已经存在100个元素了，恰好数组正好填满，但是如果还要添加数据，链表只需要对应数据个数添加结点，但是数组要进行倍数扩容，会又大量浪费；

栈的典型应用

（取自hello算法）

• 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
• 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

  ---

  ---

  queue

 队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

他就像我们打饭的时候，先去的人先打完饭，所以队列相对应就是（FIFO），

如图所示，我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。（图片取自hello算法）

 队列常用操作

成员函数	功能
empty()	判断队列是否为空
size()	获取队列中有效元素个数
front()	获取队头元素
back()	获取队尾元素
push()	队尾入队列
pop()	队头出队列
swap()	交换两个队列中的数据，可以交换部分也可以交换全部

int main()
{/* 初始化队列 */queue<int> queue;/* 元素入队 */queue.push(1);queue.push(3);queue.push(2);queue.push(5);queue.push(4);/* 访问队首元素 */cout << queue.front() << endl;/* 元素出队 */queue.pop();/* 获取队列的长度 */cout << queue.size() << endl;/* 判断队列是否为空 */cout << queue.empty() << endl;return 0;
}

运行效果： 

 队列的实现：

利用deque实现：

    template<class T, class Con = deque<T>>class queue{public:queue(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};

本人有点懒，以后有空会补充用链表来实现队列：

省略......

利用数组来实现：（全部摘自hello算法）

注意：里面有一点小优化，要注意哦

在数组中删除首元素的时间复杂度为 0(n) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如图所示。

• 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
• 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 0(1) 。

你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现，代码如下所示：

/* 基于环形数组实现的队列 */
class ArrayQueue {private:int *nums;       // 用于存储队列元素的数组int front;       // 队首指针，指向队首元素int queSize;     // 队列长度int queCapacity; // 队列容量public:ArrayQueue(int capacity) {// 初始化数组nums = new int[capacity];queCapacity = capacity;front = queSize = 0;}~ArrayQueue() {delete[] nums;}/* 获取队列的容量 */int capacity() {return queCapacity;}/* 获取队列的长度 */int size() {return queSize;}/* 判断队列是否为空 */bool isEmpty() {return size() == 0;}/* 入队 */void push(int num) {if (queSize == queCapacity) {cout << "队列已满" << endl;return;}// 计算队尾指针，指向队尾索引 + 1// 通过取余操作实现 rear 越过数组尾部后回到头部int rear = (front + queSize) % queCapacity;// 将 num 添加至队尾nums[rear] = num;queSize++;}/* 出队 */int pop() {int num = peek();// 队首指针向后移动一位，若越过尾部，则返回到数组头部front = (front + 1) % queCapacity;queSize--;return num;}/* 访问队首元素 */int peek() {if (isEmpty())throw out_of_range("队列为空");return nums[front];}/* 将数组转化为 Vector 并返回 */vector<int> toVector() {// 仅转换有效长度范围内的列表元素vector<int> arr(queSize);for (int i = 0, j = front; i < queSize; i++, j++) {arr[i] = nums[j % queCapacity];}return arr;}
};

队列典型应用

• 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。