六十二、數據結構棧和隊列的相互實現
@Author：Runsen
編程的本質來源於演算法，而演算法的本質來源於數學，編程只不過將數學題進行程式碼化。 —- Runsen
演算法，一門既不容易入門，也不容易精通的學問。
棧和隊列都是用來保存數據的，無論底層是使用數組還是鏈表來實現，其基本原理是不變的，那就是棧的特點的先進後出，隊列的特點是先進先出。
棧
棧 (Stack)是一種後進先出(last in first off，LIFO)的數據結構。線性表是用數組來實現的，對於棧這種只能一頭插入刪除的線性表來說，用數組下標為0（棧底不變，只需要跟蹤棧頂的變化即可）的一端作為棧底比較合適。
列表封裝的這些方法，實現棧這個常用的數據結構比較容易。棧是一種只能在列表一端進出的特殊列表，pop方法正好完美實現：
In [1]: stack=[1,3,5]
In [2]: stack.append(0) # push元素0到尾端，不需要指定索引
In [3]: stack
Out[3]: [1, 3, 5, 0]
In [4]: stack.pop() # pop元素，不需指定索引，此時移出尾端元素
Out[4]: 0
In [5]: stack
Out[5]: [1, 3, 5]
由此可見Python的列表當做棧用，完全沒有問題，push 和 pop 操作的時間複雜度都為 O(1)
隊列
隊列(Queue)則是一種先進先出 (fisrt in first out，FIFO)的結構.。使用順序表存儲隊列時，隊列元素的出隊是在隊頭，即下標為0的地方，當有元素出隊時，出隊元素後面的所有元素都需要向前移動，保證隊列的隊頭始終處在下標為0的位置，此時會大大增加時間複雜度。
使用列表模擬隊列，需要藉助Python的collections模組中的雙端隊列deque實現。如下模擬隊列的先進先出，後進後出：
In [1]: from collections import deque
In [2]: queue = [1,3,5]
In [3]: deq = deque(queue)
In [4]: deq.append(0)
In [5]: deq
Out[5]: deque([1, 3, 5, 0]) # 後進插入到隊列尾部
In [6]: deq.popleft()
Out[6]: 1
In [7]: deq
Out[7]: deque([3, 5, 0])# 先進的先出
LeetCode 第 225題：用隊列實現棧
#使用隊列實現棧的下列操作：
# push(x) -- 元素 x 入棧
# pop() -- 移除棧頂元素
# top() -- 獲取棧頂元素
# empty() -- 返回棧是否為空
# 注意:
# 你只能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
# 你所使用的語言也許不支援隊列。 你可以使用 list 或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。
# 你可以假設所有操作都是有效的（例如, 對一個空的棧不會調用 pop 或者 top 操作）。
# Related Topics 棧 設計
根據題意，我們只能使用隊列的基本操作，隊列因為是先進先出，要實現先進後出的棧。
無論是用隊列實現棧，還是用棧實現隊列。常見的解法方法是使用兩個隊列或者兩個棧。
假設有q1，q2兩個隊列，我們先初始化隊列。
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q1 = deque()
self.q2 = deque()
push(x) ：元素 x 入棧 時和隊列添加元素的方法一樣。
壓入棧時，加入到q1的末尾，那麼q1末尾的元素就是棧頂元素。因此只需要append(x)即可。
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q1.append(x)
對於pop刪除元素，我們可以使用q2保存q1的最後的元素之前的元素，然後將q1的元素進行刪除，最後將兩個隊列進行互換。
我們需要彈出棧頂元素，也就是q1最後的元素，隊列只能是先進先出，我們得用q2把q1出隊的元素裝著，最後一個出隊元素就是棧頂元素。
因此，程式碼需要對q1的長度進行判斷，如果q1的長度大於1，那麼將q1的頭部元素添加到q2，直到q1隻有最後一個元素。
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
tmp = self.q1.popleft()
self.q2, self.q1 = self.q1, self.q2
return tmp
判斷是否為空，只需要判斷q1的隊列是否為空。
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not bool(self.q1)
取棧頂元素。這裡其實可以巧妙地解決，我們直接調用pop方法進行刪除，在pop進行刪除時用一個變數進行保存，還需要對該元素重新進行插入操作。
def top(self) -> int:
ans = self.pop()
self.q1.append(ans)
return ans
下面就是用隊列實現棧完整程式碼
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)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
tmp = self.q1.popleft()
self.q2,self.q1 = self.q1, self.q2
return tmp
def top(self) -> int:
"""
Get the top element.
"""
ans = self.pop()
self.q1.append(ans)
return ans
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not bool(self.q1)
LeetCode 第232題：用棧實現隊列
#使用棧實現隊列的下列操作：
# push(x) -- 將一個元素放入隊列的尾部。
# pop() -- 從隊列首部移除元素。
# peek() -- 返回隊列首部的元素。
# empty() -- 返回隊列是否為空。
# 示例:
# 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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
# 假設所有操作都是有效的 （例如，一個空的隊列不會調用 pop 或者 peek 操作）。
# Related Topics 棧 設計
最簡單的方法使用list表示一個棧，只能使用棧的相關方法，如append()，pop()，s[-1]，分別是棧頂追加元素,刪除棧頂元素,取出棧頂元素.。
class MyQueue:
def __init__(self):
self.s = []
def push(self, x: int) -> None:
self.s.append(x)
def pop(self) -> int:
return self.s.pop(0)
def peek(self) -> int:
return self.s[0]
def empty(self) -> bool:
return not bool(self.s)
當然也可以使用兩個棧，這個是比較複雜的操作，但也是比較常見的演算法考點。
（1）初始化兩個棧結構，s1為主棧，s2為輔助棧。
（2）push往s1末尾添加元素，利用append即可實現。
（3）pop時候，先將s1元素向s2轉移，知道s1隻剩下一個元素時候（這就是我們要返回的隊列首部元素），然後我們再把2中的元素轉移回s1中即可。
（4）返回隊列首部的元素，類似於步驟（3）的操作，唯一不同是這裡我們需要將elenment先添加回stack2，然後再將stack2的元素轉移回stack1中，因為peek操作不需要刪除隊列首部元素
（5）empty判斷stack1尺寸即可。
出隊操作首先判斷快取棧s2是否有元素，有的話直接取出s2棧頂元素；若s2為空並且s1中有元素，將s1中元素全部轉移到s2中，再取出s2棧頂元素，即可模擬隊列出隊操作；本例中沒有出現s2和s1都為空的情況。
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.s1.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.s2:
return self.s2.pop()
else:
if self.s1 :
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if self.s2:
return self.s2[-1]
else:
if self.s1 :
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if self.s1 or self.s2:
return False
else:
return True
# 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()
本文已收錄 GitHub，傳送門~ ，裡面更有大廠面試完整考點，歡迎 Star。
