我们可以以列表的形式创建队列吗

Question

我最近一直在学习队列数据结构。我们实际上是如何创建队列的？我们可以简单地使用列表并从列表中插入和删除项目吗？还是我需要做其他事情？我也尝试过创建一个队列类。正确的方法是什么？

class Queue:

def __init__(self, capacity):
self.capacity = capacity
self.queue = []
def IsEmpty(self):
return len(self.queue) == self.capacity
def IsFull(self):
return len(self.queue) == 0
def Enqueue(self, x):
if len(self.queue) == self.capacity:
return 'Queue overloaded'
self.queue.insert(0, x)
return f'{x} enqueued into queue.'
def Dequeue(self):
return f'{self.queue[0]} dequeued fron queue.'
self.queue.pop(0)
def GetFront(self):
return self.queue[0]
def GetBack(self):
return self.queue[len(self.queue) - 1]

Answer 1

实现队列的常见方法基本上有：

1. 与ArrayList一样，您使用一个数组，如果数组已满，则会重新分配一个更大的数组。与数组列表不同，您需要允许队列中的元素从末尾到开头换行。这就是javaArrayDeque所做的，并且可能是最常见的实现。有些变体会浪费更多内存，但不会循环使用，如果有时必须将队列的一部分作为连续区域传递给其他函数，则通常会使用这些变体。

2. 使用单独链接的列表，但也要保留一个指向尾部节点的指针，以便可以快速将项目排入队列。这通常是一个侵入性列表(即，您刚刚和下一个指向您已经拥有的对象的指针(，或者。。。

3. 线程安全队列有一个特别简单的无锁实现，它使用一个带有额外头节点(以及指向尾节点的指针(的单链表。这就是Java的ConcurrentLinkedQueue所使用的。

队列的实现不是这些。python列表由类似(1(的数组支持，但第一项始终位于数组的开头。因此，pop((操作可能需要很长时间，因为所有其他项目都必须移向起点。