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.