用隊列實現棧

題目描述

????????請你僅使用兩個隊列實現一個后入先出（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
}

用棧實現隊列

題目描述

鏈接：簡單232.用棧實現隊列

????????請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現?MyQueue?類：

• void push(int x)?將元素 x 推到隊列的末尾代碼
• int pop()?從隊列的開頭移除并返回元素
• int peek()?返回隊列開頭的元素
• boolean empty()?如果隊列為空，返回?true?；否則，返回?false

說明：

• 你?只能?使用標準的棧操作 —— 也就是只有?push to top,?peek/pop from top,?size, 和?is empty?操作是合法的。
• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

解題思路

????????將一個棧當作輸入棧，用于壓入 push傳入的數據；另一個棧當作輸出棧，用于 pop和 peek操作。每次 pop或 peek時，若輸出棧為空則將輸入棧的全部數據依次彈出并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊列從隊首往隊尾的順序。

復雜度分析

時間復雜度：push和 emptyO(1)，pop和 peek為均攤 O(1)。對于每個元素，至多入棧和出棧各兩次，故均攤復雜度為 O(1)。

空間復雜度：O(n)。其中 n是操作總數。對于有 n次 push操作的情況，隊列中會有 n個元素，故空間復雜度為 O(n)。

代碼

#include <stack>
#include <iostream>
using namespace std;
class MyQueue
{
public:MyQueue(){}void push(int x){// 1.把s1所有元素彈出后依次放入s2while (!s1.empty()){s2.push(s1.top());s1.pop();}// 2.新元素加入到s2頂部s2.push(x);// 3.把s2所有元素彈出后依次放入s1while (!s2.empty()){s1.push(s2.top());s2.pop();}}int pop(){int ret = s1.top();s1.pop();return ret;}int peek(){return s1.top();}bool empty(){return s1.empty();}private:stack<int> s1;stack<int> s2;
};
int main()
{MyQueue myQueue;myQueue.push(1); // queue is: [1]myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)cout << myQueue.peek() << endl; // return 1cout << myQueue.pop() << endl; // return 1, queue is [2]cout << myQueue.empty() <<endl; // return false
}