淺析數(shù)據(jù)結(jié)構(gòu)棧和隊列的相互實現(xiàn)
" 編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學，編程只不過將數(shù)學題進行代碼化。"
算法，一門既不容易入門，也不容易精通的學問。
棧和隊列都是用來保存數(shù)據(jù)的，無論底層是使用數(shù)組還是鏈表來實現(xiàn)，其基本原理是不變的，那就是棧的特點的先進后出，隊列的特點是先進先出。
棧
棧 (Stack)是一種后進先出(last in first off，LIFO)的數(shù)據(jù)結(jié)構(gòu)。線性表是用數(shù)組來實現(xiàn)的，對于棧這種只能一頭插入刪除的線性表來說，用數(shù)組下標為0(棧底不變，只需要跟蹤棧頂?shù)淖兓纯?的一端作為棧底比較合適。
列表封裝的這些方法，實現(xiàn)棧這個常用的數(shù)據(jù)結(jié)構(gòu)比較容易。棧是一種只能在列表一端進出的特殊列表，pop方法正好完美實現(xiàn)：
- 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 操作的時間復(fù)雜度都為 O(1)
隊列
隊列(Queue)則是一種先進先出 (fisrt in first out，F(xiàn)IFO)的結(jié)構(gòu).。使用順序表存儲隊列時，隊列元素的出隊是在隊頭，即下標為0的地方，當有元素出隊時，出隊元素后面的所有元素都需要向前移動，保證隊列的隊頭始終處在下標為0的位置，此時會大大增加時間復(fù)雜度。
使用列表模擬隊列，需要借助Python的collections模塊中的雙端隊列deque實現(xiàn)。如下模擬隊列的先進先出，后進后出：
- 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題：用隊列實現(xiàn)棧#使用隊列實現(xiàn)棧
- #使用隊列實現(xiàn)棧的下列操作：
- # push(x) -- 元素 x 入棧
- # pop() -- 移除棧頂元素
- # top() -- 獲取棧頂元素
- # empty() -- 返回棧是否為空
- # 注意:
- # 你只能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
- # 你所使用的語言也許不支持隊列。 你可以使用 list 或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。
- # 你可以假設(shè)所有操作都是有效的（例如, 對一個空的棧不會調(diào)用 pop 或者 top 操作）。
- # Related Topics 棧 設(shè)計
根據(jù)題意，我們只能使用隊列的基本操作，隊列因為是先進先出，要實現(xiàn)先進后出的棧。
無論是用隊列實現(xiàn)棧，還是用棧實現(xiàn)隊列。常見的解法方法是使用兩個隊列或者兩個棧。
假設(shè)有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)
取棧頂元素。這里其實可以巧妙地解決，我們直接調(diào)用pop方法進行刪除，在pop進行刪除時用一個變量進行保存，還需要對該元素重新進行插入操作。
- def top(self) -> int:
- ans = self.pop()
- self.q1.append(ans)
- return ans
下面就是用隊列實現(xiàn)棧完整代碼
- 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題：用棧實現(xiàn)隊列
- #使用棧實現(xiàn)隊列的下列操作：
- # 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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
- # 假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。
- # Related Topics 棧 設(shè)計
最簡單的方法使用list表示一個棧，只能使用棧的相關(guān)方法，如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)
當然也可以使用兩個棧，這個是比較復(fù)雜的操作，「但也是比較常見的算法考點。」
(1)初始化兩個棧結(jié)構(gòu)，s1為主棧，s2為輔助棧。
(2)push往s1末尾添加元素，利用append即可實現(xiàn)。
(3)pop時候，先將s1元素向s2轉(zhuǎn)移，知道s1只剩下一個元素時候(這就是我們要返回的隊列首部元素)，然后我們再把2中的元素轉(zhuǎn)移回s1中即可。
(4)返回隊列首部的元素，類似于步驟(3)的操作，唯一不同是這里我們需要將elenment先添加回stack2，然后再將stack2的元素轉(zhuǎn)移回stack1中，因為peek操作不需要刪除隊列首部元素
(5)empty判斷stack1尺寸即可。
出隊操作首先判斷緩存棧s2是否有元素，有的話直接取出s2棧頂元素;若s2為空并且s1中有元素，將s1中元素全部轉(zhuǎn)移到s2中，再取出s2棧頂元素，即可模擬隊列出隊操作;本例中沒有出現(xiàn)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:
https://github.com/MaoliRUNsen/runsenlearnpy100
