栈与队列理论基础
来源：第 5 章 栈与队列 - Hello 算法 (hello-algo.com)
提问：
- C++中stack 是容器么？
- 我们使用的stack是属于哪个版本的STL？
- 我们使用的STL中stack是如何实现的？
- stack 提供迭代器来遍历stack空间么？
5.1 栈
「栈 stack」是一种遵循先入后出的逻辑的线性数据结构。
5.1.1 常用操作
- 入栈：push（）
- 出栈：pop（）
- 访问栈顶元素：peek（）
5.1.2 栈的实现
基于链表
基于数组
5.1.3 两种实现对比¶
支持操作
两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。
时间效率
在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为O(n)。
在基于链表的实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。
综上所述，当入栈与出栈操作的元素是基本数据类型时，例如 int 或 double ，我们可以得出以下结论。
- 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
- 基于链表实现的栈可以提供更加稳定的效率表现。
空间效率
在初始化列表时，系统会为列表分配“初始容量”，该容量可能超出实际需求；并且，扩容机制通常是按照特定倍率（例如 2 倍）进行扩容的，扩容后的容量也可能超出实际需求。因此，基于数组实现的栈可能造成一定的空间浪费。
然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。
综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。
5.2 队列
「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。
5.2.1 队列常见操作
- push()
- pop()
- peek()
时间复杂度O(1)
5.2.2 队列实现
- 基于链表
- 基于数组
2. 用栈实现队列
2.1 思路：
栈的函数：pop、push、top、size、empty
- 定义2个栈，一个输入，一个输出。
- push()：输入栈push
- pop(): 把输入栈的元素全部push到输出栈中，然后再pop一次。一般情况，输出不空的时候，数据肯定是先放进去的。
- peek():同pop输出栈的第一个元素肯定是队列首元素
2.2 代码复现：
class MyQueue
{
private:
/* data */
public:
stack<int> stIn;
stack<int> stOut;
MyQueue(/* args */);
~MyQueue();
void push(int num){
stIn.push(num);
}
int pop(){
if(stOut.empty()){
while (!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek(){
int res = pop();
cout << "res: " << res <<endl;
stOut.push(res);
return res;
}
};
3. 用队列实现栈
3.1 思路：
队列函数：
- push() 在队尾插入一个元素
- pop() 删除队列第一个元素
- size() 返回队列中元素个数
- empty() 如果队列空则返回true
- front() 返回队列中的第一个元素
- back() 返回队列中最后一个元素
实现
- push：向队列1输入一个数据
- pop：将队列1的size-1个数据备份到队列2中，最后一个数据pop
- top：使用队列的back函数，队列最后一个数据就是栈顶数据
3.2 代码复现：
class MyStack
{
public:
queue<int> queue1;
queue<int> queue2;
void push(int num){
queue1.push(num);
}
int pop(){
int size = queue1.size();
size--;
while (size--)
{
queue2.push(queue1.front());
queue1.pop();
}
int result = queue1.front();
queue1.pop();
queue1 = queue2;
while (!queue2.empty())
{
queue2.pop();
}
return result;
}
int top(){
return queue1.back();
}
};