題目描述
????????請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。
實現?MyStack?類：
void push(int x)?將元素 x 壓入棧頂。int pop()?移除并返回棧頂元素。int top()?返回棧頂元素。boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。
輸入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 輸出： [null, null, null, 2, 2, false] 解釋： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
解題思路
棧是一種后進先出的數據結構，元素從頂端入棧，然后從頂端出棧。
隊列是一種先進先出的數據結構，元素從后端入隊，然后從前端出隊。
????????為了滿足棧的特性，即最后入棧的元素最先出棧，在使用隊列實現棧時，應滿足隊列前端的元素是最后入棧的元素。可以使用兩個隊列實現棧的操作，其中queue1用于存儲棧內的元素，queue2作為入棧操作的輔助隊列。
????????入棧操作時，首先將元素入隊到 queue2，然后將 queue1的全部元素依次出隊并入隊到 queue2,此時 queue2的前端的元素即為新入棧的元素，再將 queue1和 queue2互換，則 queue1的元素即為棧內的元素，queue1的前端和后端分別對應棧頂和棧底。
????????由于每次入棧操作都確保 queue1的前端元素為棧頂元素，因此出棧操作和獲得棧頂元素操作都可以簡單實現。出棧操作只需要移除 queue1的前端元素并返回即可，獲得棧頂元素操作只需要獲得 queue1的前端元素并返回即可（不移除元素）。
????????由于 queue1用于存儲棧內的元素，判斷棧是否為空時，只需要判斷 queue1是否為空即可。?
復雜度分析
時間復雜度：入棧操作O(n),其余操作都是O(1),n是棧內的元素個數
空間復雜度：O(n),需要使用兩個隊列存儲站內的元素
代碼
#include <queue>
#include <array>
#include <iostream>
using namespace std;
class MyStack
{
public:queue<int> queue1;queue<int> queue2;/** 初始化棧. */MyStack(){}/** 向棧內添加元素. */void push(int x){queue2.push(x);while (!queue1.empty()){queue2.push(queue1.front());queue1.pop();}swap(queue1, queue2);}/** 移除棧頂元素 */int pop(){int r = queue1.front();queue1.pop();return r;}/** 返回棧頂元素. */int top(){int r = queue1.front();return r;}/** 返回棧是否為空. */bool empty(){return queue1.empty();}
};
int main()
{MyStack myStack;myStack.push(1);myStack.push(2);cout << myStack.top() << endl; // 返回 2cout << myStack.pop() << endl;; // 返回 2cout << myStack.empty() << endl; // 返回 False
}
)
