本節(jié)我們將介紹 STL 中的 stack 和 queue 容器使用逆日。

棧和隊(duì)列都是極其重要的數(shù)據(jù)結(jié)構(gòu)，C++ STL 中也提供了 stack 和 queue 等容器萄凤。它們的概念理解起來不難室抽，使用起來也十分方便，接下來我們將一一介紹這些容器蛙卤，并結(jié)合一些相關(guān)的例題來加深理解狠半。

stack 容器

stack<T> 容器適配器中的數(shù)據(jù)是以 LIFO 的方式組織的，即先進(jìn)后出颤难，當(dāng)想訪問棧內(nèi)某一元素時(shí)神年，必須將其頂部的元素都彈出出棧后，才能訪問該元素行嗤。
下圖演示了 stack 容器的一些基本操作已日。

stack 容器

棧(stack) 有著廣泛的應(yīng)用。例如我們?cè)诤芏嘬浖惺褂玫某蜂N操作(ctrl + z)栅屏，信心觀察會(huì)發(fā)現(xiàn)飘千，不同軟件中撤銷操作回撤的數(shù)據(jù)量是不同的堂鲜，這也許和棧的不同有關(guān)吧。還有算術(shù)表達(dá)式的求值等等护奈，都會(huì)用到棧這種數(shù)據(jù)結(jié)構(gòu)缔莲。

stack 的定義

定義一個(gè)存放字符串棧：

stack<string> data;

stack 容器適配器的模板有兩個(gè)參數(shù)：
第一個(gè)參數(shù)是存儲(chǔ)對(duì)象的類型。
第二個(gè)參數(shù)是底層容器的類型霉旗。
stack<T> 的底層容器默認(rèn)是 deque<T> 容器痴奏，因此模板類型其實(shí)是

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

通過指定第二個(gè)模板類型參數(shù)，可以使用任意類型的底層容器厌秒，只要它們支持 back()读拆，push_back()，pop_back()鸵闪。

下面展示了如何定義一個(gè)使用了 list<T> 的堆棧：

stack<int,list<int>> data;

在創(chuàng)建堆棧時(shí)檐晕，不能在初始化列表中初始化，但是可以用另一個(gè)容器來初始化蚌讼，只要堆棧的底層容器類型和這個(gè)容器的類型是相同的辟灰。

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

第二條語句生成了一個(gè)包含 data_ 元素副本的 data 。
這里不能在 stack 構(gòu)造函數(shù)中使用初始化列表啦逆，必須使用圓括號(hào)伞矩。如果沒有在第二個(gè) stack 模板類型參數(shù)中將底層容器指定為 list，那么底層容器可能是 deque夏志，這樣就不能用 list 的內(nèi)容來初始化 stack乃坤，而只能接受 deque。

stack<T> 模板定義了拷貝構(gòu)造函數(shù)沟蔑，因而可以復(fù)制現(xiàn)有的 stack 容器：

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

copy_data 是 data 的副本湿诊。
在使用拷貝構(gòu)造函數(shù)時(shí)，既可以用初始化列表瘦材，也可以用圓括號(hào)厅须。
而在 stack 構(gòu)造函數(shù)中必須使用圓括號(hào)。

stack的相關(guān)操作

和之前介紹的容器相比食棕，stack 是一類存儲(chǔ)機(jī)制簡單朗和、所提供操作較少的容器。
下面是 stack 容器可以提供的一套完整操作：

stack 的訪問：

deque<int> data_ {0,1,2,3,4};
//初始化一個(gè)棧
stack<int> data(data_);
cout<<"data : "<<data.size()<<endl;
while(!data.empty()){
       //獲得棧頂元素
   cout<<data.top()<<" ";
       //棧頂元素出棧
   data.pop();
   }
cout<<endl;
cout<<"data : "<<data.size()<<endl;

打印的結(jié)果為：

data : 5
4 3 2 1 0
data : 0

stack<T> 模板也定義了復(fù)制和移動(dòng)版的 operator=() 函數(shù)耀里，因此可以將一個(gè) stack 對(duì)象賦值給另一個(gè) stack 對(duì)象。stack 對(duì)象有一整套比較運(yùn)算符拾氓。比較運(yùn)算通過字典的方式來比較底層容器中相應(yīng)的元素冯挎。字典比較是一種用來對(duì)字典中的單詞進(jìn)行排序的方式。依次比較對(duì)應(yīng)元素的值痪枫，直到遇到兩個(gè)不相等的元素织堂。第一個(gè)不匹配的元素會(huì)作為字典比較的結(jié)果。如果一個(gè) stack 的元素比另一個(gè) stack 的多奶陈，但是所匹配的元素都相等，那么元素多的那個(gè) stack 容器大于元素少的 stack 容器附较。

queue 容器

queue<T> 是一種只能訪問第一個(gè)和最后一個(gè)元素的容器適配器吃粒，只能在容器的末尾添加新元素，只能從頭部移除元素拒课。

許多程序都使用了 queue 容器徐勃，如生活中的排隊(duì)隊(duì)列，對(duì)于任何需要用 FIFO 準(zhǔn)則處理的序列來說早像，使用 queue 容器適配器都是好的選擇僻肖。

下圖展示了一個(gè) queue 容器及其一些基本操作

queue 容器

queue 的定義

queue 的生成方法和 stack 相同。
創(chuàng)建一個(gè)保存整形數(shù)據(jù)的隊(duì)列：

queue<int> data;

使用 list 創(chuàng)建隊(duì)列：

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

使用拷貝構(gòu)造函數(shù)：

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> 這類適配器類都默認(rèn)封裝了一個(gè) deque<T> 容器臀脏，也可以通過指定第二個(gè)模板類型參數(shù)來使用其他類型的容器：

queue<int,list<int>> data;

底層容器必須提供這些操作：front()，back()冀自，push_back()揉稚，pop_front()，empty() 和 size()熬粗。

queuu 操作

queue 和 stack 有一些成員函數(shù)相似搀玖，但某些情況下，功能有些不同：

和 stack 一樣嗦明，queue 也沒有迭代器。訪問元素的唯一方式是遍歷容器內(nèi)容蚪燕，并移除訪問過的每一個(gè)元素娶牌。例如：

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;

打印的內(nèi)容為：

data : 5
0 1 2 3 4
data : 0

用循環(huán)打印 data 的全部內(nèi)容，循環(huán)由 empty() 返回的值控制馆纳。調(diào)用 empty() 可以保證我們能夠調(diào)用一個(gè)空隊(duì)列的 front() 函數(shù)诗良。
如上所示，為了訪問 queue 中的全部元素鲁驶，必須刪除它們鉴裹。如果不想刪除容器中的元素，必須將它們復(fù)制到另一個(gè)容器中钥弯。如果一定要這么操作径荔，我們可能需要換一個(gè)容器。

queue<T> 模板定義了拷貝和移動(dòng)版的 operator=()脆霎，對(duì)于所保存元素類型相同的 queue 對(duì)象总处，它們有一整套的比較運(yùn)算符，這些運(yùn)算符的工作方式和 stack 容器相同睛蛛。

典例

這里列舉兩個(gè)來自 LeetCode 的題鹦马。

用隊(duì)列實(shí)現(xiàn)棧

使用隊(duì)列實(shí)現(xiàn)棧的下列操作：

    push(x) -- 元素 x 入棧
    pop() -- 移除棧頂元素
    top() -- 獲取棧頂元素
    empty() -- 返回棧是否為空

注意:
你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
你所使用的語言也許不支持隊(duì)列玖院。 你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可菠红。
你可以假設(shè)所有操作都是有效的（例如, 對(duì)一個(gè)空的棧不會(huì)調(diào)用 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();
 */

該題要求使用隊(duì)列實(shí)現(xiàn)棧难菌，即我們需要用隊(duì)列的函數(shù)來實(shí)現(xiàn)棧的函數(shù)围段，棧是在棧頂入棧元素和出棧元素精盅，隊(duì)列是只能在尾部增加元素，在隊(duì)頭刪除元素，因此可以將隊(duì)列頭部作為棧頂初橘，尾部作為棧底勾习。
首先轧坎，我們得建立一個(gè)隊(duì)列作為成員函數(shù)股耽。

queue<int> nums;

先從最簡單的 empty() 函數(shù)開始，返回棧是否為空褐健，顯然：

return nums.empty();

之后考慮 top() 函數(shù)付鹿，棧的 top() 函數(shù)是獲取棧頂元素澜汤，那么我們只需要返回隊(duì)列第一個(gè)元素即可。

return nums.front();

再考慮 pop() 函數(shù)舵匾，移除棧頂元素俊抵，返回隊(duì)頭元素，并彈出坐梯。

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

最后考慮 push(int x) 徽诲，元素 x 入棧。

隊(duì)列是只能在尾部增加元素吵血，在隊(duì)頭刪除元素谎替，之前提到過，我們將隊(duì)列頭部的刪除元素功能當(dāng)作出棧功能蹋辅，同時(shí)棧頂也有入棧功能钱贯。
為此，當(dāng)在隊(duì)列尾部增加元素后晕翠，該元素在隊(duì)列尾喷舀，對(duì)應(yīng)棧，該元素卻在棧底淋肾，不在棧頂。
因此爸邢，在進(jìn)入隊(duì)列時(shí)樊卓，需要將隊(duì)列其他元素出隊(duì)列，然后入隊(duì)列杠河，這樣新加入的元素才能在隊(duì)列頭部碌尔，相當(dāng)于棧頂。

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();
 */

這樣券敌，我們就實(shí)現(xiàn)了用隊(duì)列實(shí)現(xiàn)棧了唾戚。

用棧實(shí)現(xiàn)隊(duì)列

使用棧實(shí)現(xiàn)隊(duì)列的下列操作：

    push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。
    pop() -- 從隊(duì)列首部移除元素待诅。
    peek() -- 返回隊(duì)列首部的元素叹坦。
    empty() -- 返回隊(duì)列是否為空。

示例:

MyQueue queue = new MyQueue();

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

說明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的卑雁。
你所使用的語言也許不支持棧募书。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可测蹲。
假設(shè)所有操作都是有效的 （例如莹捡，一個(gè)空的隊(duì)列不會(huì)調(diào)用 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();
 */

類似的扣甲，我們需要用棧的函數(shù)來實(shí)現(xiàn)隊(duì)列的函數(shù)篮赢。
棧是只能在棧頂入元素和彈出元素的，而隊(duì)列是在頭部彈出元素，尾部增加元素的启泣。
顯然涣脚，一個(gè)棧是不夠用的，我們需要兩個(gè)棧种远，用一個(gè)主棧 data1 和一個(gè)輔助棧 data2 存儲(chǔ)數(shù)據(jù)涩澡。
data1 是主棧，其棧底當(dāng)作隊(duì)列的頭部坠敷，其棧頂當(dāng)作隊(duì)列的尾部妙同。
data2 輔助完成隊(duì)列的 peek()，pop() 和 push(int x) 功能膝迎。

首先粥帚，我們建立兩個(gè)棧作為類成員。

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

先從 empty() 函數(shù)出發(fā)限次，返回隊(duì)列是否為空芒涡，顯然：

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

之后考慮 peek() 函數(shù)，返回隊(duì)列首部的元素卖漫。
data1 是主棧费尽，需要獲得其棧底元素，當(dāng)作隊(duì)列的首部元素羊始。
我們可以先將 data1 的所有元素出棧旱幼，入棧至 data2 中，此時(shí) data2 的棧頂為隊(duì)列首部元素突委。

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

然后 pop() 函數(shù)柏卤，從隊(duì)列首部移除元素，和 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) 函數(shù)敌蚜，將一個(gè)元素放入隊(duì)列的尾部桥滨。
我們知道 data1 的棧頂使當(dāng)作隊(duì)列的尾部，而在之前的 pop() 和 peek() 中钝侠，數(shù)據(jù)都保存在 data2 中的该园，因此我們先將 data2 中的數(shù)據(jù)出棧并入棧到 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();
 */

這樣里初，我們就實(shí)現(xiàn)了用棧實(shí)現(xiàn)隊(duì)列了。

這兩個(gè)題雖然簡單忽舟，但是幫助我們對(duì)棧和隊(duì)列的理解是大有裨益的双妨，棧和隊(duì)列還有著很重要的應(yīng)用淮阐，多多做題無疑是熟練使用它們的一個(gè)很好手段。

至此刁品，stack 和 queue 容器的介紹就暫告一段落了泣特。