《大話資料結構》第四章：棧與隊列（筆記）

第四章：棧與隊列

棧(stack)：限定僅在表尾進行插入和删除操作的線性表

隊列：隻允許在一端插入操作，在另一端進行删除操作的線性表

棧的定義：

• 允許插入和删除的一端稱為棧頂(top)，另一端稱為棧底(bottom)，不含任何元素的棧稱為空棧，是一種**後進先出(Last In Fast Out，LIFO)**的線性表。
• 棧的插入操作(push)：進棧、壓棧或入棧
• 棧的删除操作(pop)：出棧或彈棧

棧的順序存儲結構：

• 順序棧，可用數組實作，将下标為0的一端作為棧底，存放首元素top = -1 時表示空棧

兩棧共享空間：

• 當我們有兩個類型相同的棧時，可将記憶體共享，數組兩個端點分别為棧底bottom1=0，bottom2=n-1

這樣的共享棧結構，通常運用于兩個棧空間需求有相反關系時。

棧的鍊式存儲結構：

• 鍊棧，鍊式存儲結構，由于單連結清單有頭指針，棧頂指針也是必須的，是以選擇單連結清單頭部作為棧頂。

棧的應用——遞歸

斐波那契數列(Fibonacci)的實作：

def Fibonacci(i):
    if i < 2:  # 基線條件
        return i

    else:  # 遞歸條件
        return Fibonacci(i - 1) + Fibonacci(i - 2)


def main():
    fibonacci_number = 12
    for i in range(1, fibonacci_number + 1):
        print(Fibonacci(i), end=' ')


if __name__ == '__main__':
    main()
           

當然用循環疊代同樣可實作斐波那契數列，遞歸則使代碼更加幹淨，遞歸函數一定注意其基線條件，避免形成死循環。

棧的應用——四則運算表達式

• 字尾（逆波蘭）表達式：一種不需要括号的字尾表達式，平時我們常見的都為中綴表達式，便于計算機内部實作四則運算。

隊列的定義(Queue)：

• 隊列是一種**先進先出(First In First Out，FIFO)**的線性表
• 允許插入的一端稱為：隊尾，允許删除的一端稱為：隊頭

順序存儲循環隊列，隊列頭尾相接的順序結構

• front 指針指向隊頭元素，rear指針指向隊尾元素的下一個位置，當front等于rear時，隊列為空隊列（rear == front）
• 對于循環隊列時：( rear +1 ) % QueueSize == front 時，隊列滿。
• 計算隊列長度：( rear - front + QueueSize) & QueueSize

鍊式存儲機構，應用線性表的單連結清單

• 将隊列的頭指針front指向鍊隊列的頭結點，對尾指針指向終端結點

用清單實作隊列入隊出隊：

class Queue(object):  # 建立隊列類
    def __init__(self):
        self.queue_list = []

    def is_empyt(self):  # 判斷隊列是否為空
        return self.queue_list == []

    def en_queue(self, data):  # 在隊列尾部添加新元素——入隊
        self.queue_list.append(data)

    def de_queue(self):  # 隊頭元素出隊，并傳回其值
        de_queue_value = self.queue_list.pop(0)
        return de_queue_value

    def size_queue(self):  # 傳回目前隊列長度
        return len(self.queue_list)


if __name__ == '__main__':
    q = Queue()
    print('目前隊列長度:', q.size_queue())
    q.en_queue(1)
    q.en_queue(2)
    q.en_queue(3)
    print('入隊三個元素後長度:', q.size_queue())
    print('出隊元素:', q.de_queue())