C++ STL 之 stack 和 queue

本节我们将介绍 STL 中的 stack 和 queue 容器使用。

---

---

栈和队列都是极其重要的数据结构，C++ STL 中也提供了 stack 和 queue 等容器。它们的概念理解起来不难，使用起来也十分方便，接下来我们将一一介绍这些容器，并结合一些相关的例题来加深理解。

stack 容器

stack<T> 容器适配器中的数据是以 LIFO 的方式组织的，即先进后出，当想访问栈内某一元素时，必须将其顶部的元素都弹出出栈后，才能访问该元素。
下图演示了 stack 容器的一些基本操作。

stack 容器

栈(stack) 有着广泛的应用。例如我们在很多软件中使用的撤销操作(ctrl + z)，信心观察会发现，不同软件中撤销操作回撤的数据量是不同的，这也许和栈的不同有关吧。还有算术表达式的求值等等，都会用到栈这种数据结构。

stack 的定义

定义一个存放字符串栈：

stack<string> data;

stack 容器适配器的模板有两个参数：
第一个参数是存储对象的类型。
第二个参数是底层容器的类型。
stack<T> 的底层容器默认是 deque<T> 容器，因此模板类型其实是

stack<typename T, typename Container = deque<T>>

通过指定第二个模板类型参数，可以使用任意类型的底层容器，只要它们支持 back()，push_back()，pop_back()。

下面展示了如何定义一个使用了 list<T> 的堆栈：

stack<int,list<int>> data;

在创建堆栈时，不能在初始化列表中初始化，但是可以用另一个容器来初始化，只要堆栈的底层容器类型和这个容器的类型是相同的。

list<int> data_ {0,1,2,3};
stack<int,list<int>> data(data_);

第二条语句生成了一个包含 data_ 元素副本的 data 。
这里不能在 stack 构造函数中使用初始化列表，必须使用圆括号。如果没有在第二个 stack 模板类型参数中将底层容器指定为 list，那么底层容器可能是 deque，这样就不能用 list 的内容来初始化 stack，而只能接受 deque。

stack<T> 模板定义了拷贝构造函数，因而可以复制现有的 stack 容器：

stack<int,list<double>> copy_data {data};

copy_data 是 data 的副本。
在使用拷贝构造函数时，既可以用初始化列表，也可以用圆括号。
而在 stack 构造函数中必须使用圆括号。

stack的相关操作

和之前介绍的容器相比，stack 是一类存储机制简单、所提供操作较少的容器。
下面是 stack 容器可以提供的一套完整操作：

函数	功能
top()	返回栈顶元素的引用，类型为 T&，如果栈为空，返回值未定义
pop()	栈顶元素出栈
size()	返回栈中元素的个数
empty()	栈中没有元素时返回 true
emplace()	使用传入的参数调用构造函数，在栈顶生成对象
push(const T& obj)	将对象副本压入栈顶，通过调用底层容器的 push_back() 函数实现
push(T&& obj)	以移动对象的方式将对象压入栈，通过调用底层容器的有右值引用参数的 push_back() 函数实现
swap(stack<T> & other_stack)	将当前栈中的元素和参数中的元素交换，参数所包含元素的类型必须和当前栈的相同，对于 stack 对象有一个特例化的全局函数 swap() 可以使用

stack 的访问：

deque<int> data_ {0,1,2,3,4};
//初始化一个栈
stack<int> data(data_);
cout<<"data : "<<data.size()<<endl;
while(!data.empty()){
       //获得栈顶元素
   cout<<data.top()<<" ";
       //栈顶元素出栈
   data.pop();
   }
cout<<endl;
cout<<"data : "<<data.size()<<endl;

打印的结果为：

data : 5
4 3 2 1 0
data : 0

stack<T> 模板也定义了复制和移动版的 operator=() 函数，因此可以将一个 stack 对象赋值给另一个 stack 对象。stack 对象有一整套比较运算符。比较运算通过字典的方式来比较底层容器中相应的元素。字典比较是一种用来对字典中的单词进行排序的方式。依次比较对应元素的值，直到遇到两个不相等的元素。第一个不匹配的元素会作为字典比较的结果。如果一个 stack 的元素比另一个 stack 的多，但是所匹配的元素都相等，那么元素多的那个 stack 容器大于元素少的 stack 容器。

queue 容器

queue<T> 是一种只能访问第一个和最后一个元素的容器适配器，只能在容器的末尾添加新元素，只能从头部移除元素。

许多程序都使用了 queue 容器，如生活中的排队队列，对于任何需要用 FIFO 准则处理的序列来说，使用 queue 容器适配器都是好的选择。

下图展示了一个 queue 容器及其一些基本操作

queue 容器

queue 的定义

queue 的生成方法和 stack 相同。
创建一个保存整形数据的队列：

queue<int> data;

使用 list 创建队列：

list<int> data_{0,1,2,3};
queue<int,list<int>> q(data_);

使用拷贝构造函数：

list<int> data_{0,1,2,3};
queue<int,list<int>> q(data_);
queue<int,list<int>> copy_q {q};

或者：

deque<int> data_{1,2,3,0,4};
queue<int> q (data_);

stack<T>、queue<T> 这类适配器类都默认封装了一个 deque<T> 容器，也可以通过指定第二个模板类型参数来使用其他类型的容器：

queue<int,list<int>> data;

底层容器必须提供这些操作：front()，back()，push_back()，pop_front()，empty() 和 size()。

queuu 操作

queue 和 stack 有一些成员函数相似，但某些情况下，功能有些不同：

函数	功能
front()	返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的
back()	返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的
push(const T& obj)	在 queue 的尾部添加一个元素的副本。通过调用底层容器的成员函数 push_back() 实现
push(T&& obj)	以移动的方式在 queue 的尾部添加元素。通过调用底层容器的具有右值引用参数的成员函数 push_back() 实现
pop()	删除 queue 中的第一个元素(头部元素)
size()	返回 queue 中元素的个数
empty()	如果 queue 中没有元素，返回 true
emplace()	使用 emplace() 中的参数调用 T 的构造函数，在 queue 的尾部生成对象
swap(queue<T> &other_q)	将当前 queue 中的元素和参数 queue 中的元素交换。包含元素的类型相同。也可以调用全局函数模板 swap() 来完成同样的操作

和 stack 一样，queue 也没有迭代器。访问元素的唯一方式是遍历容器内容，并移除访问过的每一个元素。例如：

deque<int> data_ {0,1,2,3,4};
queue<int> data(data_);
cout<<"data : "<<data.size()<<endl;
while(!data.empty()){
    cout<<data.front()<<" ";
    data.pop();
    }
cout<<endl;
cout<<"data : "<<data.size()<<endl;

打印的内容为：

data : 5
0 1 2 3 4
data : 0

用循环打印 data 的全部内容，循环由 empty() 返回的值控制。调用 empty() 可以保证我们能够调用一个空队列的 front() 函数。
如上所示，为了访问 queue 中的全部元素，必须删除它们。如果不想删除容器中的元素，必须将它们复制到另一个容器中。如果一定要这么操作，我们可能需要换一个容器。

queue<T> 模板定义了拷贝和移动版的 operator=()，对于所保存元素类型相同的 queue 对象，它们有一整套的比较运算符，这些运算符的工作方式和 stack 容器相同。

典例

这里列举两个来自 LeetCode 的题。

用队列实现栈

使用队列实现栈的下列操作：

    push(x) -- 元素 x 入栈
    pop() -- 移除栈顶元素
    top() -- 获取栈顶元素
    empty() -- 返回栈是否为空

注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues

代码模板：

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        
    }
    
    /** Get the top element. */
    int top() {
        
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

该题要求使用队列实现栈，即我们需要用队列的函数来实现栈的函数，栈是在栈顶入栈元素和出栈元素，队列是只能在尾部增加元素，在队头删除元素，因此可以将队列头部作为栈顶，尾部作为栈底。
首先，我们得建立一个队列作为成员函数。

queue<int> nums;

先从最简单的 empty() 函数开始，返回栈是否为空，显然：

return nums.empty();

之后考虑 top() 函数，栈的 top() 函数是获取栈顶元素，那么我们只需要返回队列第一个元素即可。

return nums.front();

再考虑 pop() 函数，移除栈顶元素，返回队头元素，并弹出。

int num=nums.front();
nums.pop();
return num;

最后考虑 push(int x) ，元素 x 入栈。

队列是只能在尾部增加元素，在队头删除元素，之前提到过，我们将队列头部的删除元素功能当作出栈功能，同时栈顶也有入栈功能。
为此，当在队列尾部增加元素后，该元素在队列尾，对应栈，该元素却在栈底，不在栈顶。
因此，在进入队列时，需要将队列其他元素出队列，然后入队列，这样新加入的元素才能在队列头部，相当于栈顶。

nums.push(x);
for(int i=1;i<nums.size();i++){
     int num=nums.front();
     nums.push(num);
     nums.pop();
}

完整代码如下：

class MyStack {
public:
    queue<int> nums;
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        nums.push(x);
        for(int i=1;i<nums.size();i++){
            int num=nums.front();
            nums.push(num);
            nums.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int num=nums.front();
        nums.pop();
        return num;
    }
    
    /** Get the top element. */
    int top() {
        return nums.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return nums.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

这样，我们就实现了用队列实现栈了。

用栈实现队列

使用栈实现队列的下列操作：

    push(x) -- 将一个元素放入队列的尾部。
    pop() -- 从队列首部移除元素。
    peek() -- 返回队列首部的元素。
    empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks

代码模板:

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        
    }
    
    /** Get the front element. */
    int peek() {
        
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

类似的，我们需要用栈的函数来实现队列的函数。
栈是只能在栈顶入元素和弹出元素的，而队列是在头部弹出元素，尾部增加元素的。
显然，一个栈是不够用的，我们需要两个栈，用一个主栈 data1 和一个辅助栈 data2 存储数据。
data1 是主栈，其栈底当作队列的头部，其栈顶当作队列的尾部。
data2 辅助完成队列的 peek()，pop() 和 push(int x) 功能。

首先，我们建立两个栈作为类成员。

stack<int> data1;
stack<int> data2;

先从 empty() 函数出发，返回队列是否为空，显然：

return data1.empty() && data2.empty();

之后考虑 peek() 函数，返回队列首部的元素。
data1 是主栈，需要获得其栈底元素，当作队列的首部元素。
我们可以先将 data1 的所有元素出栈，入栈至 data2 中，此时 data2 的栈顶为队列首部元素。

while(!data1.empty()){
    int num = data1.top();
    data2.push(num);
    data1.pop();
}
return data2.top();

然后 pop() 函数，从队列首部移除元素，和 peek() 类似，只要使 data2 的栈顶元素出栈即可。

while(!data1.empty()){
    int num = data1.top();
    data2.push(num);
    data1.pop();
}
int num_ = data2.top();
data2.pop();
return num_; 

最后，push(int x) 函数，将一个元素放入队列的尾部。
我们知道 data1 的栈顶使当作队列的尾部，而在之前的 pop() 和 peek() 中，数据都保存在 data2 中的，因此我们先将 data2 中的数据出栈并入栈到 data1 中，然后将 x 入栈至 data1 中即可。

while(!data2.empty()){
    int num = data2.top();
    data1.push(num);
    data2.pop();
}
data1.push(x);

完整代码如下：

class MyQueue {
public:
    stack<int> data1;
    stack<int> data2;
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        while(!data2.empty()){
            int num = data2.top();
            data1.push(num);
            data2.pop();
        }
        data1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(!data1.empty()){
            int num = data1.top();
            data2.push(num);
            data1.pop();
        }
        int num_ = data2.top();
        data2.pop();
        return num_; 
    }
    
    /** Get the front element. */
    int peek() {
        while(!data1.empty()){
            int num = data1.top();
            data2.push(num);
            data1.pop();
        }
        return data2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return data1.empty() && data2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

这样，我们就实现了用栈实现队列了。

---

---

这两个题虽然简单，但是帮助我们对栈和队列的理解是大有裨益的，栈和队列还有着很重要的应用，多多做题无疑是熟练使用它们的一个很好手段。

至此，stack 和 queue 容器的介绍就暂告一段落了。