DSA 队列

队列

队列是一种可以容纳多个元素的数据结构。

{{ x.dieNmbr }}

{{ resultText }}: {{ currVal }}

入队() 出队() 查看() 为空() 大小()

可以把队列想象成超市里排队的人。

第一个排队的人也是第一个可以付款并离开超市的人。这种组织元素的方式称为 FIFO：先进先出。

我们可以对队列进行的基本操作有

• 入队：向队列添加一个新元素。
• 出队：从队列中移除并返回第一个（头部）元素。
• 查看：返回队列中的第一个元素。
• 为空：检查队列是否为空。
• 大小：查找队列中元素的数量。

在上面的队列动画中，尝试使用这些基本操作。

队列可以使用数组或链表来实现。

队列可以用来实现办公室打印机的作业调度，电子票的订单处理，或者创建图的广度优先搜索算法。

队列通常与栈一起提及，栈是一个类似的数据结构，在上一页有介绍。

使用数组实现队列

为了更好地理解使用数组或链表实现队列的好处，你应该查看此页面，它解释了数组和链表如何在内存中存储。

这就是使用数组作为队列时的样子

使用数组实现队列的理由

• 内存效率高：数组元素不像链表节点那样保存下一个元素的地址。
• 易于实现和理解：使用数组实现队列需要比使用链表更少的代码，因此通常也更容易理解。

不使用数组实现队列的理由

• 固定大小：数组占据内存中的固定部分。这意味着它可能占用比需要更多的内存，或者如果数组满了，它就无法容纳更多元素。调整数组大小可能会很昂贵。
• 移位成本：出队会导致队列中的第一个元素被移除，而其他元素必须移动以占据被移除元素的位置。这效率低下，尤其是在队列很长的情况下，会导致问题。
• 备选方案：一些编程语言内置了针对队列操作优化的数据结构，比使用数组更好。

由于 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.