用隊列實現(xiàn)棧

請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通隊列的全部四種操作（push、top、pop 和 empty）。

實現(xiàn) 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（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。
這道題的關(guān)鍵之處就是push的操作，如何可以讓后入隊的數(shù)據(jù)成為隊頭呢？
隊列化棧有兩種辦法：
1，兩個隊列
隊列是先進先出，而棧則是先進后出，可以設(shè)兩個隊列q1和q2，q2作為一個輔助隊列，每次進棧元素先入隊到q2中，這就是棧頂，然后在依次將q1中的元素依次入隊到q2中，則q2的數(shù)據(jù)就是棧的存儲方式，然后再交換q1和q2，當再有新的數(shù)據(jù)入棧時再重復這幾步；代碼如下：

class MyStack { private:queue<int> q1,q2; public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {q2.push(x);while(!q1.empty())//將q1的數(shù)據(jù)依次入隊到q2中{q2.push(q1.front());q1.pop();}swap(q1,q2);}/** Removes the element on top of the stack and returns that element. */int pop() {int front=q1.front();q1.pop();return front;}/** Get the top element. */int top() {return q1.front();}/** Returns whether the stack is empty. */bool empty() {return q1.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();*/

2，一個隊列
想法是類似的，只要有新數(shù)據(jù)入隊，只需要把該數(shù)據(jù)之前的所有數(shù)據(jù)移到該數(shù)據(jù)之后就可以了；
代碼如下：

class MyStack {queue<int> q; public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {q.push(x);int i=q.size()-1;//每次入隊的數(shù)據(jù)一定在最后一個，只需要將最后一個數(shù)據(jù)前的所有數(shù)據(jù)依次排到該數(shù)據(jù)之后即可while(i--){q.push(q.front());q.pop();}}/** Removes the element on top of the stack and returns that element. */int pop() {int front=q.front();q.pop();return front;}/** Get the top element. */int top() {return q.front();}/** Returns whether the stack is empty. */bool empty() {return q.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();*/

棧化隊列

實現(xiàn)一個MyQueue類，該類用兩個棧來實現(xiàn)一個隊列。

示例：

MyQueue queue = new MyQueue();

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

說明：
你只能使用標準的棧操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。

兩個棧實現(xiàn)
我們可以通過兩個棧來實現(xiàn)隊列先進先出，設(shè)棧s1和s2，先將數(shù)據(jù)入棧到s1中，s1的數(shù)據(jù)再依次出棧到s2中，這樣s1的棧頂就成了s2的棧底，而s1中最先入棧的數(shù)據(jù)就成了s2的棧頂，這樣就實現(xiàn)了先進先出；
總的來說就是s1只用來入棧，而s2只用來出棧，即s1執(zhí)行的入隊操作，s2是出隊操作；
代碼如下：

class MyQueue { private:stack<int> s1,s2; public:/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {s1.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {if(s2.empty())//s2為空時將s1數(shù)據(jù)出棧依次入棧到s2{while(!s1.empty()){s2.push(s1.top());s1.pop();}}int top=s2.top();s2.pop();return top;}/** Get the front element. */int peek() {if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}}return s2.top();}/** Returns whether the queue is empty. */bool empty() {return s1.empty()&&s2.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();*/

總結(jié)：這兩道題雖然是棧和隊列的互換，但是細細體會就會感受到不同數(shù)據(jù)結(jié)構(gòu)之間的聯(lián)系，對數(shù)據(jù)的處理方式還需不斷理解體會；

總結(jié)

以上是生活随笔為你收集整理的队列化栈栈化队列（力扣）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。