今天來學習兩個新的資料結構，Stack (堆疊) 和 Queue (佇列)

Stack (堆疊)

概念

Stack 是一種 FILO (先進後出) 的資料結構，所謂 FILO 就是，先放進 Stack 的資料，再取出的時候，會是最後一個被取出的，也可以說是 LIFO (後進先出)，如下圖

操作

Stack 的基礎操作有兩個，放資料、取資料，通常寫作 push、pop (因為都從頂部操作)。

會有一個 top 來追蹤頂部在哪裡

參考程式碼

class Stack:
    def __init__(self, size):
        self.size = size
        self.items = [None] * size # 預先配置大小，用 List 代替 Array
        self.top = 0  

    def is_empty(self):  # 判斷 stack 是否為空
        return self.top == 0

    def is_full(self):  # 判斷 stack 是否為滿了
        return self.top == self.size

    def push(self, data):  # 放一個資料進 stack
        if self.is_full():
            raise Exception("Overflow")
        self.items[self.top] = data
        self.top += 1

    def pop(self):  # 取一個資料出來
        if self.is_empty():
            raise Exception("Underflow")
        self.top -= 1
        item = self.items[self.top]
        self.items[self.top] = None
        return item

Queue (佇列)

概念

Queue 是一種 FIFO (先進先出) 的資料結構，所謂 FIFO 就是，先放進 Queue 的資料，再取出的時候，會是第一個被取出的，如下圖

操作

Queue 的基礎操作有兩個，放資料、取資料，通常寫作 enqueue、dequeue

會有一個 head、tail (也有人用 front、rear) 來追蹤最前面跟最後面在哪裡

參考程式碼

class Queue:
    def __init__(self, size):
        self.size = size
        self.items = [None] * size  # 預先配置大小，用 List 代替 Array
        self.head = 0  # 最前面的
        self.tail = 0  # 最後面的
        self.count = 0 # 裡面有多少

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.size

    def enqueue(self, data): # 放一個資料進 queue
        if self.is_full():
            raise Exception("Overflow")
        self.items[self.tail] = data
        self.tail = (self.tail + 1) % self.size # 透過 mod 避免 tail 無限增長
        self.count += 1
        return

    def dequeue(self):  # 取一個資料出來
        if self.is_empty():
            raise Exception("Underflow")  
        data = self.items[self.head]
        self.items[self.head] = None
        self.head = (self.head + 1) % self.size # 透過 mod 避免 head 無限增長
        self.count -= 1

        return data