DSA 佇列

佇列

佇列可以容納許多元素。

{{ x.dieNmbr }}

{{ resultText }}: {{ currVal }}

enqueue() dequeue() peek() isEmpty() size()

將佇列想象成超市裡排隊的人。

第一個排隊的人也是第一個可以付款並離開超市的人。這種組織元素的方式稱為 FIFO：先進先出（First In First Out）。

我們可以對佇列執行的基本操作有：

• 入隊 (Enqueue): 將一個新元素新增到佇列。
• 出隊 (Dequeue): 移除並返回佇列中的第一個（前端）元素。
• 檢視 (Peek): 返回佇列中的第一個元素。
• isEmpty: 檢查佇列是否為空。
• Size: 查詢佇列中的元素數量。

在上面的佇列動畫中嘗試這些基本操作。

佇列可以透過陣列或連結串列實現。

佇列可用於實現印表機的作業排程、電子票務的訂單處理，或建立圖中廣度優先搜尋的演算法。

佇列經常與棧（Stack）一起提及，棧是相似的資料結構，請參閱 上一頁。

使用陣列實現佇列

為了更好地理解使用陣列或連結串列實現佇列的好處，你應該檢視 此頁面，它解釋了陣列和連結串列在記憶體中的儲存方式。

使用陣列作為佇列的外觀如下：

使用陣列實現佇列的原因

• 記憶體效率高: 陣列元素不像連結串列節點那樣儲存下一個元素的地址。
• 易於實現和理解: 使用陣列實現佇列比使用連結串列需要的程式碼更少，因此通常也更容易理解。

不使用陣列實現佇列的原因

• 固定大小: 陣列佔用固定大小的記憶體。這意味著它可能佔用比所需更多的記憶體，或者如果陣列已滿，則無法容納更多元素。調整陣列大小可能會很昂貴。
• 移位成本: 出隊會導致佇列中的第一個元素被移除，其他元素必須移位以填補被移除元素的位置。這效率低下，並且可能導致問題，尤其是當佇列很長時。
• 替代方案: 一些程式語言內建了針對佇列操作最佳化的資料結構，這些資料結構比使用陣列更好。

由於 Python 列表在實現佇列所需的功能方面具有良好的支援，因此我們可以用幾行程式碼建立一個佇列並執行佇列操作。

queue = []

# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)

# Dequeue
element = queue.pop(0)
print("Dequeue: ", element)

# Peek
frontElement = queue[0]
print("Peek: ", frontElement)

# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)

# Size
print("Size: ", len(queue))

但是，為了顯式地建立一個用於佇列的資料結構，幷包含基本操作，我們應該建立一個佇列類。這種在 Python 中建立佇列的方式也更類似於其他程式語言（如 C 和 Java）中建立佇列的方式。

class Queue:
    def __init__(self):
        self.queue = []
    
    def enqueue(self, element):
        self.queue.append(element)
    
    def dequeue(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.queue.pop(0)
    
    def peek(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.queue[0]
    
    def isEmpty(self):
        return len(self.queue) == 0
    
    def size(self):
        return len(self.queue)

# Create a queue
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)

print("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())

使用連結串列實現佇列

使用連結串列實現佇列的原因

• 動態大小: 佇列可以動態地增長和縮小，不像陣列。
• 無需移位: 可以移除佇列的前端元素（入隊），而無需在記憶體中移動其他元素。

不使用連結串列實現佇列的原因

• 額外記憶體: 每個佇列元素必須包含指向下一個元素的地址（下一個連結串列節點）。
• 可讀性: 程式碼可能對某些人來說更難讀寫，因為它更長、更復雜。

這是使用連結串列實現佇列的方法。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.length = 0
    
    def enqueue(self, element):
        new_node = Node(element)
        if self.rear is None:
            self.front = self.rear = new_node
            self.length += 1
            return
        self.rear.next = new_node
        self.rear = new_node
        self.length += 1
    
    def dequeue(self):
        if self.isEmpty():
            return "Queue is empty"
        temp = self.front
        self.front = temp.next
        self.length -= 1
        if self.front is None:
            self.rear = None
        return temp.data
    
    def peek(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.front.data
    
    def isEmpty(self):
        return self.length == 0
    
    def size(self):
        return self.length

    def printQueue(self):
        temp = self.front
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()

# Create a queue
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()

print("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())

enqueue(7): 
    value 7 is placed on 
    index  in the array.

dequeue(): 
    value  is taken 
    out of the queue.