淺析數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列的相互實(shí)現(xiàn)

作者：小sen 2020-12-17 10:12:33

" 編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。"算法，一門既不容易入門，也不容易精通的學(xué)問。

" 編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。"

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

棧和隊(duì)列都是用來保存數(shù)據(jù)的，無論底層是使用數(shù)組還是鏈表來實(shí)現(xiàn)，其基本原理是不變的，那就是棧的特點(diǎn)的先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。

棧

棧 (Stack)是一種后進(jìn)先出(last in first off，LIFO)的數(shù)據(jù)結(jié)構(gòu)。線性表是用數(shù)組來實(shí)現(xiàn)的，對于棧這種只能一頭插入刪除的線性表來說，用數(shù)組下標(biāo)為0(棧底不變，只需要跟蹤棧頂?shù)淖兓纯?的一端作為棧底比較合適。

列表封裝的這些方法，實(shí)現(xiàn)棧這個常用的數(shù)據(jù)結(jié)構(gòu)比較容易。棧是一種只能在列表一端進(jìn)出的特殊列表，pop方法正好完美實(shí)現(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的列表當(dāng)做棧用，完全沒有問題，push 和 pop 操作的時間復(fù)雜度都為 O(1)

隊(duì)列

隊(duì)列(Queue)則是一種先進(jìn)先出 (fisrt in first out，F(xiàn)IFO)的結(jié)構(gòu).。使用順序表存儲隊(duì)列時，隊(duì)列元素的出隊(duì)是在隊(duì)頭，即下標(biāo)為0的地方，當(dāng)有元素出隊(duì)時，出隊(duì)元素后面的所有元素都需要向前移動，保證隊(duì)列的隊(duì)頭始終處在下標(biāo)為0的位置，此時會大大增加時間復(fù)雜度。

使用列表模擬隊(duì)列，需要借助Python的collections模塊中的雙端隊(duì)列deque實(shí)現(xiàn)。如下模擬隊(duì)列的先進(jìn)先出，后進(jì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]) # 后進(jìn)插入到隊(duì)列尾部 
 
In [6]: deq.popleft()   
Out[6]: 1 
 
In [7]: deq 
Out[7]: deque([3, 5, 0])# 先進(jìn)的先出

LeetCode 第 225題：用隊(duì)列實(shí)現(xiàn)棧#使用隊(duì)列實(shí)現(xiàn)棧

#使用隊(duì)列實(shí)現(xiàn)棧的下列操作：  
# push(x) -- 元素 x 入棧  
# pop() -- 移除棧頂元素  
# top() -- 獲取棧頂元素  
# empty() -- 返回棧是否為空  
# 注意:  
# 你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。  
# 你所使用的語言也許不支持隊(duì)列。 你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。  
# 你可以假設(shè)所有操作都是有效的（例如, 對一個空的棧不會調(diào)用 pop 或者 top 操作）。  
# Related Topics 棧 設(shè)計

根據(jù)題意，我們只能使用隊(duì)列的基本操作，隊(duì)列因?yàn)槭窍冗M(jìn)先出，要實(shí)現(xiàn)先進(jìn)后出的棧。

無論是用隊(duì)列實(shí)現(xiàn)棧，還是用棧實(shí)現(xiàn)隊(duì)列。常見的解法方法是使用兩個隊(duì)列或者兩個棧。

假設(shè)有q1，q2兩個隊(duì)列，我們先初始化隊(duì)列。

from collections import deque 
class MyStack: 
    def __init__(self): 
        """ 
        Initialize your data structure here. 
        """ 
        self.q1 = deque() 
        self.q2 = deque()

push(x) ：元素 x 入棧時和隊(duì)列添加元素的方法一樣。

壓入棧時，加入到q1的末尾，那么q1末尾的元素就是棧頂元素。因此只需要append(x)即可。

def push(self, x: int) -> None: 
    """ 
    Push element x onto stack. 
    """ 
    self.q1.append(x)

對于pop刪除元素，我們可以使用q2保存q1的最后的元素之前的元素，然后將q1的元素進(jìn)行刪除，最后將兩個隊(duì)列進(jìn)行互換。

我們需要彈出棧頂元素，也就是q1最后的元素，隊(duì)列只能是先進(jìn)先出，我們得用q2把q1出隊(duì)的元素裝著，最后一個出隊(duì)元素就是棧頂元素。

因此，代碼需要對q1的長度進(jìn)行判斷，如果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的隊(duì)列是否為空。

def empty(self) -> bool: 
    """ 
    Returns whether the stack is empty. 
    """ 
    return not bool(self.q1)

取棧頂元素。這里其實(shí)可以巧妙地解決，我們直接調(diào)用pop方法進(jìn)行刪除，在pop進(jìn)行刪除時用一個變量進(jìn)行保存，還需要對該元素重新進(jìn)行插入操作。

def top(self) -> int: 
    ans = self.pop() 
    self.q1.append(ans) 
    return ans

下面就是用隊(duì)列實(shí)現(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題：用棧實(shí)現(xiàn)隊(duì)列

#使用棧實(shí)現(xiàn)隊(duì)列的下列操作： 
# push(x) -- 將一個元素放入隊(duì)列的尾部。  
# pop() -- 從隊(duì)列首部移除元素。  
# peek() -- 返回隊(duì)列首部的元素。  
# empty() -- 返回隊(duì)列是否為空。 
# 示例: 
# MyQueue queue = new MyQueue(); 
#queue.push(1); 
#queue.push(2);   
#queue.peek();  // 返回 1 
#queue.pop();   // 返回 1 
#queue.empty(); // 返回 false 
# 說明: 
# 你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。  
# 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。  
# 假設(shè)所有操作都是有效的 （例如，一個空的隊(duì)列不會調(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)

當(dāng)然也可以使用兩個棧，這個是比較復(fù)雜的操作，「但也是比較常見的算法考點(diǎn)。」

(1)初始化兩個棧結(jié)構(gòu)，s1為主棧，s2為輔助棧。

(2)push往s1末尾添加元素，利用append即可實(shí)現(xiàn)。

(3)pop時候，先將s1元素向s2轉(zhuǎn)移，知道s1只剩下一個元素時候(這就是我們要返回的隊(duì)列首部元素)，然后我們再把2中的元素轉(zhuǎn)移回s1中即可。

(4)返回隊(duì)列首部的元素，類似于步驟(3)的操作，唯一不同是這里我們需要將elenment先添加回stack2，然后再將stack2的元素轉(zhuǎn)移回stack1中，因?yàn)閜eek操作不需要刪除隊(duì)列首部元素

(5)empty判斷stack1尺寸即可。

出隊(duì)操作首先判斷緩存棧s2是否有元素，有的話直接取出s2棧頂元素;若s2為空并且s1中有元素，將s1中元素全部轉(zhuǎn)移到s2中，再取出s2棧頂元素，即可模擬隊(duì)列出隊(duì)操作;本例中沒有出現(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()