題目描述

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。實現 MyStack 類：
void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。注意：
你只能使用隊列的標準操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。
你所使用的語言也許不支持隊列。 你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。示例：輸入：
["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

思路

用單個隊列實現了棧的行為。棧是一種后入先出（LIFO）的數據結構，通常支持 push、pop、top 和 empty 操作。在這個實現中，通過對隊列的操作，模擬了棧的行為。

類定義和構造函數

class MyStack {
public:std::queue<int> que;MyStack() {}

MyStack 類中定義了一個公有成員 que，類型為 std::queue，用于存儲棧中的元素。
構造函數 MyStack() 是一個空構造函數，不進行任何操作。隊列 que 的初始化由其默認構造函數處理。

push()

    void push(int x) {que.push(x);}

push(int x) 方法直接將元素 x 加入隊列的尾部。在棧的行為中，這將是最后一個被彈出的元素，符合后入先出的特性。

pop()

    int pop() {for(int i = 0; i < que.size() - 1; i++){que.push(que.front());que.pop();}int result = que.front();que.pop();return result;}

pop() 方法移除并返回棧頂元素。為了達到這個目的，首先將隊列前面的元素（除最后一個元素外）依次出隊并重新入隊到隊列尾部。這樣，原本的最后一個元素（棧頂元素）就移到了隊列的前端，可以通過 que.pop() 直接移除并返回。
循環 for(int i = 0; i < que.size() - 1; i++) 確保除了最后一個元素，其他所有元素都被重新排列。

top()

    int top() {return que.back();}

top() 方法返回棧頂元素的值，但不移除它。由于隊列的 back() 方法可以直接訪問隊尾元素，這里的隊尾元素正是最后入棧的元素，因此可以直接返回。

empty()

    bool empty() {return que.empty();}

empty() 方法檢查棧（隊列）是否為空。如果隊列為空，則棧也為空，返回 true；否則返回 false。

完整代碼

#include<stack>
#include<queue>
#include<iostream>class MyStack {
public:std::queue<int> que;MyStack() {}void push(int x) {que.push(x);}int pop() {for(int i = 0; i < que.size() - 1; i++){que.push(que.front());que.pop();}int result = que.front();que.pop();return result;}int top() {return que.back();}bool empty() {return que.empty();}
};int main() {MyStack myStack;myStack.push(1);myStack.push(2);std::cout << "Top: " << myStack.top() << std::endl;  // 返回 2std::cout << "Pop: " << myStack.pop() << std::endl;  // 返回 2std::cout << "Empty: " << (myStack.empty() ? "true" : "false") << std::endl;  // 返回 falsereturn 0;
}

時間復雜度: pop為O(n)，其他為O(1)
空間復雜度: O(n)