[[358323]]

" 編程的本質來源于算法，而算法的本質來源于數學，編程只不過將數學題進行代碼化。"

算法，一門既不容易入門，也不容易精通的學問。

棧和隊列都是用來保存數據的，無論底層是使用數組還是鏈表來實現，其基本原理是不變的，那就是棧的特點的先進后出，隊列的特點是先進先出。

棧

棧 (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:

https://github.com/MaoliRUNsen/runsenlearnpy100