LeetCode 232：用棧實(shí)現(xiàn)隊(duì)列
往期回顧
三分鐘基礎(chǔ)：什么是時(shí)間｜空間復(fù)雜度
三分鐘基礎(chǔ)之鏈表訓(xùn)練：環(huán)形鏈表
三分鐘基礎(chǔ)之鏈表訓(xùn)練：環(huán)形鏈表升級(jí)版
今天用棧實(shí)現(xiàn)隊(duì)列這道題，是考察對(duì)”棧和隊(duì)列理解程度“的好題。
放心，在實(shí)際工作的時(shí)候，不是腦殘十級(jí)，幾乎不會(huì)提出這樣奇怪的需求。
話不多說，直接開整。
???LeetCode 232：用棧實(shí)現(xiàn)隊(duì)列
題意
僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列，隊(duì)列支持一般隊(duì)列支持的所有操作：
void push(int x)：將元素 x 推到隊(duì)列的末尾。
int pop()：從隊(duì)列的開頭移除并返回元素。
int peek()：返回隊(duì)列開頭的元素。
boolean empty()：如果隊(duì)列為空，返回 true；否則，返回 false。
示例
提示
1 <= x <=?9
最多調(diào)用 100 次 push、pop、peek 和 empty
假設(shè)所有操作都是有效的（eg. 一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）
題目解析
水題，難度簡單，主要考察對(duì)棧和隊(duì)列的理解能力。
如果對(duì)棧和隊(duì)列還不熟悉，看一下下面這篇文章，某帥比寫的：
仔細(xì)來看，主要涉及 4 種常規(guī)操作：
入隊(duì)?push
出隊(duì) pop
判空 empty
取隊(duì)首元素 peek
知道了要求，剩下就是如何用棧模擬隊(duì)列。
隊(duì)列是一種先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，而棧是一種后入先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，所以一個(gè)棧絕對(duì)滿足不了隊(duì)列的 FIFO 的特性。
比如 1 2 3，隊(duì)列 1 2 3 進(jìn)，應(yīng)該 1 2 3 出，但是 1 2 3 進(jìn)了棧，出來以后會(huì)成 3 2 1，和 1 2 3 是相反的，所以再需要一個(gè)棧，把 3 2 1 返成 1 2 3。
因此這里需要兩個(gè)棧，分別是輸入棧和輸出棧：
輸入棧來反轉(zhuǎn)元素的入隊(duì)順序，元素入只能從輸入棧進(jìn)（push）。
輸出棧用來存儲(chǔ)元素的正常順序，元素出只能從輸出棧出（pop、peek）。
圖解
首先初始化輸入棧和輸出棧。
def __init__(self):# 初始化輸入棧和輸出棧self.inStack = []self.outStack = []
push(x) ，入隊(duì)操作，直接壓入輸入棧即可。
比如 push(1)、push(2)。
def?push(self,?x:?int)?->?None:# 有新元素進(jìn)來，進(jìn)入輸入棧self.inStack.append(x)
push 操作，每個(gè)元素入棧的時(shí)間復(fù)雜度為 O(1)，隊(duì)列長度為 n，所以時(shí)間復(fù)雜度為 O(n)。因?yàn)樾枰~外的棧來存儲(chǔ)隊(duì)列中的元素，所以空間復(fù)雜度為?O(n)。
pop()，?出隊(duì)操作，如果輸出棧不為空的話，直接扔出棧頂元素，輸出棧為空的話，那把輸入棧的所有元素壓入輸出棧中，然后再扔出棧頂元素。
def?pop(self)?->?int:# 如果為空if self.empty():????????return?None# 如果輸出棧不為空，返回輸出棧中的元素if self.outStack:return self.outStack.pop()# 輸出棧為空,將輸入棧的元素壓入輸出棧else:while self.inStack:val = self.inStack.pop()self.outStack.append(val)return self.outStack.pop()
pop 操作的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)。
empty()，判空操作。判空很簡單，輸入棧和輸出棧都為空，則隊(duì)列為空，否則隊(duì)列不為空。
def?empty(self)?->?bool:# 兩個(gè)棧都為空，隊(duì)列才為空if not(self.inStack or self.outStack):return Truereturn False
這個(gè)沒啥好說的，做了一步判斷，時(shí)間復(fù)雜度為 O(1)，空間復(fù)雜度均為 O(n)。
peek()，取隊(duì)列的首元素，和 pop() 的操作差不多。唯一的區(qū)別是，pop 是刪掉了隊(duì)首元素，而 peek 只是看隊(duì)首元素。
def?peek(self)?->?int:# 使用已有的函數(shù) popres = self.pop()# pop 函數(shù)彈出了 res，所以要再添加回去self.outStack.append(res)return res
隊(duì)列的首元素使用已有的 pop 函數(shù)，時(shí)間復(fù)雜度和空間復(fù)雜度和 pop 一樣，時(shí)間復(fù)雜度和空間復(fù)雜度都為 O(n)。
代碼實(shí)現(xiàn)
Python 代碼實(shí)現(xiàn)
class MyQueue:def __init__(self):"""Initialize your data structure here."""# 初始化輸入棧和輸出棧self.inStack = []self.outStack = []def push(self, x: int) -> None:"""Push element x to the back of queue."""# 有新元素進(jìn)來，進(jìn)入輸入棧self.inStack.append(x)def pop(self) -> int:"""Removes the element from in front of queue and returns that element."""????????#?如果為空if self.empty():return None# 如果輸出棧不為空，返回輸出棧中的元素if self.outStack:return self.outStack.pop()# 輸出棧為空,將輸入棧的元素壓入輸出棧else:while self.inStack:val = self.inStack.pop()self.outStack.append(val)return self.outStack.pop()def peek(self) -> int:"""Get the front element."""# 使用已有的函數(shù) popres = self.pop()# pop 函數(shù)彈出了 res，所以要再添加回去self.outStack.append(res)return resdef empty(self) -> bool:"""Returns whether the queue is empty."""# 兩個(gè)棧都為空，隊(duì)列才為空if not(self.inStack or self.outStack):return Truereturn False# Your MyQueue object will be instantiated and called as such:# obj = MyQueue()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.peek()# param_4 = obj.empty()
Java 代碼實(shí)現(xiàn)
class MyQueue {Stackstack1; Stackstack2; /** Initialize your data structure here. */public MyQueue() {stack1 = new Stack<>(); // 負(fù)責(zé)進(jìn)棧stack2 = new Stack<>(); // 負(fù)責(zé)出棧}/** Push element x to the back of queue. */public void push(int x) {stack1.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {dumpStack1();return stack2.pop();}/** Get the front element. */public int peek() {dumpStack1();return stack2.peek();}/** Returns whether the queue is empty. */public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}// 如果stack2為空，那么將stack1中的元素全部放到stack2中private void dumpStack1(){if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}}}/*** 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();* boolean param_4 = obj.empty();*/
圖解棧實(shí)現(xiàn)隊(duì)列到這就結(jié)束啦，是不是很簡單吶，只要熟悉棧和隊(duì)列就一定會(huì)。
