劍指Offer09.用兩個棧實(shí)現(xiàn)隊(duì)列
難度：簡單
題目：
用兩個棧實(shí)現(xiàn)一個隊(duì)列。隊(duì)列的聲明如下唆阿，請實(shí)現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead 丹弱，
分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能勤揩。(若隊(duì)列中沒有元素驹针，deleteHead操作返回 -1 )
提示：
- 1 <= values <= 10000
- 最多會對 appendTail逞刷、deleteHead 進(jìn)行 10000 次調(diào)用
示例：
示例 1：
輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：
輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
分析
首先掃盲隊(duì)列與棧的知識：
- 隊(duì)列：先進(jìn)先出
- 棧：后進(jìn)先出
那么纠俭，為什么要雙棧實(shí)現(xiàn)隊(duì)列呢冰木？其實(shí)大家只要思考下：
我們準(zhǔn)備兩個棧add_stack和pop_stack：
- 先把1,2,3先挨個加入add_stack棧
- 下來依次將add_stack棧內(nèi)的數(shù)據(jù)出棧穷劈，同時將出棧的數(shù)據(jù)加入pop_stack棧中
- 1、2執(zhí)行完成后踊沸，add_stack變成了空歇终，pop_stack棧中存儲的數(shù)據(jù)成了[3,2,1]
- 那么下次出棧時，直接將pop_stack的棧內(nèi)數(shù)據(jù)彈出逼龟，不就成了列隊(duì)的先進(jìn)先出评凝！
關(guān)于什么時候執(zhí)行2步驟需要注意下：
- 如果pop_stack棧中有數(shù)據(jù)，就直接return pop的數(shù)據(jù)
- 如果pop_stack棧中沒有數(shù)據(jù)
a. add_stack也沒有數(shù)據(jù)腺律，return -1
b. add_stack有數(shù)據(jù)奕短，執(zhí)行上面步驟2，將add_stack數(shù)據(jù)加入pop_stack中 - 返回pop_stack棧彈出的數(shù)據(jù)
解題：
class CQueue:
def __init__(self):
self.add_stack, self.pop_stack = [], []
def appendTail(self, value: int) -> None:
self.add_stack.append(value)
def deleteHead(self) -> int:
if self.pop_stack:
return self.pop_stack.pop()
if not self.add_stack:
return -1
while self.add_stack:
self.pop_stack.append(self.add_stack.pop())
return self.pop_stack.pop()
225.用隊(duì)列實(shí)現(xiàn)棧
難度：簡單
題目：
請你僅使用兩個隊(duì)列實(shí)現(xiàn)一個后入先出（LIFO）的棧匀钧，并支持普通隊(duì)列的全部四種操作（push翎碑、top、pop 和 empty）之斯。
實(shí)現(xiàn) MyStack 類：
void push(int x) 將元素 x 壓入棧頂日杈。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素佑刷。
boolean empty() 如果棧是空的莉擒，返回 true ；否則瘫絮，返回 false 涨冀。
注意：
- 你只能使用隊(duì)列的基本操作 —— 也就是push to back、peek/pop from front麦萤、size 和is empty這些操作蝇裤。
- 你所使用的語言也許不支持隊(duì)列。你可以使用 list （列表）或者 deque（雙端隊(duì)列）來模擬一個隊(duì)列, 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可频鉴。
示例：
輸入：
["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
分析
這道題的關(guān)鍵在于每次入隊(duì)時，如何保證入隊(duì)后新入隊(duì)的元素排在隊(duì)首恋拍，題目要求使用兩個隊(duì)列實(shí)現(xiàn)垛孔。
- 首先我們創(chuàng)建兩個隊(duì)列，python操作為
from collections import deque - 元素入隊(duì)時施敢，將元素加入q1
- 判斷q2是否存在元素周荐，如果存在元素狭莱，則將元素依次出隊(duì)并加入q1的隊(duì)尾
- 交換q1與q2
至于出隊(duì)、查詢top概作、是否為空腋妙，都在q2上操作即可
解題：
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q1.append(x)
while self.q2:
self.q1.append(self.q2.popleft())
self.q1, self.q2 = self.q2, self.q1
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.q2.popleft()
def top(self) -> int:
"""
Get the top element.
"""
return self.q2[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not self.q2
歡迎關(guān)注我的公眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時讯榕，了解更多python小知識骤素。
我的個人博客：https://qingfengpython.cn
