個人博客主頁：http://myblog.nxx.nx.cn
代碼GitHub地址：https://github.com/nx-xn2002/Data_Structure.git

Day10

232. 用棧實現隊列

題目鏈接：
https://leetcode.cn/problems/implement-queue-using-stacks/

題目描述：
請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

思路：
題目讓我們使用兩個棧來實現隊列，已知棧是先進后出的數據結構，隊列是先進先出，因此顯然要想使得先被壓入棧中的元素先被彈出，只使用一個棧是不夠的，需要一個輔助棧來實現，將原棧中的元素都放入到輔助棧里再進行出棧操作，就能夠做到先壓入的元素先被彈出來。于是，對于題目要求實現的各個方法有以下實現思路（下面設數據棧為棧A，輔助棧為棧B）:

• void push(int x) 將元素 x 推到隊列的末尾：直接將元素壓入棧A中即可
• int pop() 從隊列的開頭移除并返回元素：如果棧B不為空，則出棧并返回棧B的棧頂元素。否則，將棧A所有元素依次出棧并壓入到棧B中，然后出棧并返回棧B的棧頂元素
• int peek() 返回隊列開頭的元素：如果棧B不為空，則返回棧B的棧頂元素。否則，將棧A所有元素依次出棧并壓入到棧B中，然后返回棧B的棧頂元素
• boolean empty() 如果隊列為空，返回 true ；否則，返回 false：若棧A和棧B均為空，則返回 true，否則，返回 false

代碼實現：

class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack2.isEmpty() && stack1.isEmpty();}
}

225. 用隊列實現棧

題目鏈接：
https://leetcode.cn/problems/implement-stack-using-queues/

題目描述：
請你僅使用兩個隊列實現一個后入先出（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（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。

思路：
這一題和上一題思路類似，只需要牢牢抓住棧和隊列的特點就行了。也是需要兩個隊列來實現，基本各方法實現思路如下（隊列A為數據隊列，隊列B為輔助隊列）：

• void push(int x) 將元素 x 壓入棧頂：如果隊列A為空，則直接將 x 入隊。否則，將隊列A中所有元素出隊并入隊到隊列B中，將 x 入隊到隊列A中然后將隊列B中所有元素出隊并入隊到隊列A中
• int pop() 移除并返回棧頂元素：直接將隊列A的隊首元素出隊并返回即可
• int top() 返回棧頂元素：將隊列A的隊首元素返回即可
• boolean empty() 如果棧是空的，返回 true ；否則，返回 false ：若隊列A為空，則返回 true，否則，返回 fasle

代碼實現：

class MyStack {Queue<Integer> data;Queue<Integer> help;public MyStack() {data = new LinkedList<>();help = new LinkedList<>();}public void push(int x) {while (!data.isEmpty()) {help.add(data.poll());}data.add(x);while (!help.isEmpty()) {data.add(help.poll());}}public int pop() {return data.poll();}public int top() {return data.peek();}public boolean empty() {return data.isEmpty();}
}

總結：今天的題目基本都比較簡單，核心都是深入理解棧和隊列的特點