題目
棧和隊(duì)列是常見的數(shù)據(jù)結(jié)構(gòu)，棧的特點(diǎn)是 先進(jìn)后出前痘，而隊(duì)列的特點(diǎn)是 先進(jìn)先出元媚。
請使用 棧 模擬實(shí)現(xiàn)隊(duì)列的下列操作：
- push(x) -- 將元素 x 推到隊(duì)列的末尾
- pop() -- 從隊(duì)列的開頭移除并返回元素
- peek() -- 返回隊(duì)列開頭的元素
- empty() -- 判斷隊(duì)列是否為空
說明：
- 可以用 列表list 來模擬棧，但只允許使用棧的基本操作。
- 假設(shè)每次調(diào)用 pop 和 peek 都能保證隊(duì)列不為空样眠。
實(shí)現(xiàn)思路1
- 使用兩個棧，一個作為輸入棧 stack1 ，另一個作為輸出棧 stack2
- 每次 push 入隊(duì)操作蜂筹，直接把 待入隊(duì)的新元素 入棧到 stack1 即可
- 每次 pop 出隊(duì)操作，stack2的棧頂就相當(dāng)于隊(duì)列的隊(duì)頭芦倒，直接從 stack2 彈出棧頂元素即可艺挪，如果 stack2 為空，那么就把 stack1 的所有元素導(dǎo)入到 stack2 中熙暴，最后再從 stack2 彈出數(shù)據(jù)
- 每次 peek 獲取隊(duì)頭元素操作闺属，可以復(fù)用出隊(duì)操作的實(shí)現(xiàn)，從而拿到隊(duì)列開頭的元素
- 每次 empty 操作周霉，則需判斷 stack1 和 stack2 是否都為空
代碼實(shí)現(xiàn)1
class MyQueue:
def __init__(self):
self.stack1 = [] # 輸入棧
self.stack2 = [] # 輸出棧
def push(self, x):
self.stack1.append(x)
def pop(self):
if self.stack2 == []:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self):
tmp = self.pop()
self.stack2.append(tmp)
return tmp
def empty(self):
return self.stack1 == [] and self.stack2 == []
實(shí)現(xiàn)思路2
- 使用兩個棧掂器，一個作為輔助棧 stack1 ，另一個作為存放隊(duì)列元素的棧 stack2
- 每次 push 入隊(duì)操作俱箱，需先把 stack2 中全部元素導(dǎo)入到 stack1 国瓮，接著把 待入隊(duì)的新元素 入棧到 stack1 ，最后把 stack1 中全部元素導(dǎo)入到 stack2狞谱，這樣一來乃摹，stack2的棧頂就相當(dāng)于隊(duì)列的隊(duì)頭
- 每次 pop 出隊(duì)操作，直接從 stack2 彈出棧頂元素
- 每次 peek 獲取隊(duì)頭元素操作跟衅，直接從 stack2 獲取棧頂元素
- 每次 empty 操作孵睬，則只需判斷 stack2 是否為空
代碼實(shí)現(xiàn)2
class MyQueue:
def __init__(self):
self.stack1 = [] # 輔助棧
self.stack2 = [] # 存放隊(duì)列元素
def push(self, x):
while self.stack2:
self.stack1.append(self.stack2.pop())
self.stack1.append(x)
while self.stack1:
self.stack2.append(self.stack1.pop())
def pop(self):
return self.stack2.pop()
def peek(self):
return self.stack2[-1]
def empty(self):
return self.stack2 == []
更多Python編程題，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
