棧

棧，是先進后出的線性表，標準STL的棧包括如下5種操作，設棧S:
1.取出棧頂元素:S.top();
2.判斷棧是否為空:S.empty();
3.將元素x添加至棧:S.push(x)
4.彈出棧頂:S.pop();
5.求棧存儲元素的個數(shù):S.size()

#include <stdio.h>
#include <stack>
int main(){
    std:: stack<int> S;
    if(S.empty()){
        printf("S is empty!");
     }
    S.push(5);
    S.push(6);
    S.push(10);
    printf("S.top = %d\n",S.top());
    S.pop();
    S.pop();
    printf("S.top = %d\n",S.top());
    printf("S.size = %d\n",S.size());
    return 0;
}

隊列

隊列，是先進先出的線性表，標準STL的隊列包括如下6種操作，設隊列Q:
1.判斷隊列是否為空:Q.empty();
2.返回隊列頭部元素:Q.front();
3.返回隊列尾部元素:Q.back()
4.彈出隊列頭部元素:Q.pop();
5.將元素x添加至隊列:Q.push(x);
6.求隊列存儲元素的個數(shù):Q.size()

# include <stdio.h>
# include <queue>
int main(){
    std::queue<int> Q;
    if(Q.empty()){
        printf("Q is empty!\n");
    }
    Q.push(5);
    Q.push(6);
    Q.push(10);
    printf("Q.front = %d \n",Q.front());
    Q.pop();
    Q.pop();
    printf("Q.front = %d \n",Q.front());
    Q.push(1);
    printf("Q.back = %d \n",Q.back());
    printf("Q.size = %d\n",Q.size());
    return 0;
    
}

1.使用隊列實現(xiàn)棧

LeetCode 225. Implement Stack using Queues
設計一個棧，支持如下操作，棧的內部存儲數(shù)據的結構為隊列，隊列的方法只 能包括push、peek(front)、pop、size、empty等標準的隊列方法。

class MyStack{
public:
    MyStack(){
}
    void push(int x){
}
    int pop(){
}
    int top(){
}
    bool empty(){
}        
};

算法設計，push時調整

普通隊列實現(xiàn)棧stack，內部存儲結構時隊列Queue：

#include<queue>
class Mystack{
public:
    Mystack(){}
    void push(int x){
        std::queue<int> temp_queue;
        temp_queue.push(x);//先將新元素push進入temp_queue
        while(!_data.empty()){
            temp_queue.push(_data.front());//將數(shù)據隊列元素導入臨時隊列
            _data.pop();
        }
        while(!temp_queue.empty()){
            _data.push(temp_queue.front());//將臨時隊列元素再導入數(shù)據隊列
            temp_queue.pop();
        }
    }
int pop(){
    int x= _data.front();
    _data.pop();
    return x;
}
int top(){
    return _data.front();
}
bool empty(){
     return _data.empty();
}
private:
    std::queue<int> _data;
}；

使用棧實現(xiàn)隊列

LeetCode 232. Implement Queue using Stacks
設計一個隊列，隊列支持如下操作，盡量使隊列的各項操作的平均時間復雜度是 常數(shù)級O(1);隊列的內部存儲數(shù)據的結構為棧，棧的方法只能包括push、top、
pop、size、empty等標準的棧方法。
1.push(x) : 將元素x壓入隊列中
2.pop() : 彈出(移除)隊列頭部元素
3.peek() : 返回隊列頭部元素(即為front)
4.empty() : 判斷隊列是否是空

算法設計1，push時調整

1.在隊列push元素時，利用臨時棧調換元素次序

2.將原數(shù)據棧內容push進入臨時棧temp_stack

3.將新數(shù)據push進入臨時棧temp_stack

4.將臨時棧temp_stack中的元素push進入數(shù)據棧data_stack

#include <stack>
class MyQueue{
public:
    MyQueue(){
    }
    void push(int x){
        std::stack<int> temp_stack
        while(! _data.empty){
            temp_stack.push(_data.top());
            _data.pop();
    }
        temp_stack.push(x);   
        while(!temp_stack.empty()){
        _data.push(temp_stack.top());
        temp.pop()  
    }
    }
int pop(){
    int x = _data.top();
    _data.pop;
    return x;
}
int peek(){
    return _data.top();
}
bool empty(){
    return _data.empty();
}
};

算法設計2，雙棧法

雙棧法，即用兩個棧，來實現(xiàn)隊列的功能。一個棧為輸入棧input_stack，一個棧為輸出棧output_stack。 算法過程，整體各項操作的平均算法復雜度常數(shù)級，O(1):
1.push(x)操作:將待壓入的元素x直接push至input_stack中。
2.pop或peek(front)操作，在獲取隊列頭部元素時，可能需要對兩個棧進行調整(adjust): 如果output_stack不空，不需要調整，直接返回或彈出output_stack棧頂元素。 否則，將input_stack全部元素push進入output_stack，每push一個元素input_stack彈出一個元素;然后再返回或彈 出output_stack棧頂元素。
3.empty操作:input_stack與output_stack均為空時，返回true，否則返回false。

#include <stack>
class MyQueue{
public:
    MyQueue(){
    }
    void push(int x){
        _input.push(x);//直接將x push進入_input
    }
    int pop(){
        adjust();//調整再進行pop
        int x = _output.top();
        _output.pop();
        return x;    
    }
    int peek(){
        adjust();
        return _output.top();
    }
    bool empty(){//當input_stack與output_stack 同時為空時，才返回true
        return _input.empty()&&_output.empty();
    }
private:
    void adjust(){
        if(!_output.empty()){
            return ;
        }
        while(!_input.empty()){
            _output.push(_input.top());
            _input.pop();
        }
}
    std::stack<int> _input;
    std::stack<int> _output;
};