队列
最低要求功能
与队列相关的基本操作有两个:
函数名* 提供的功能 排队(我)
插入元素我在队伍的尾部。 出列()
删除队列头部的元素。 此外,队列通常通过以下操作来实现以节省计算:
函数名* 提供的功能 尺寸()
返回队列的当前大小 peek ()
返回队列头部的元素无需改变队列 *不要求具体姓名。事实上,某些功能可以通过特定的语法直接由给定的语言提供。
使用列表的Python实现示例
下面是一个用Python实现的队列。该实现使用Python列表作为其数据结构。
在这里,头是在数组的最低可能下标处(在左侧),而尾巴位于可能的最高索引(在右侧)。
注意:队列已经在Python中使用它们的列表类型和一些函数实现了。这是一个重新实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
示例:添加和删除队列中的项目
属性以上使用Python实现一个队列。
实例化队列:
>>> queue = queue () >>> queue.size() 0
在队列中加入三个人:
> > > queue.enqueue(爱丽丝)> > > queue.enqueue (Bob) > > > queue.enqueue(“查理”)> > > queue.size () 3
队列当前看起来像这样(记住,头在左边):
> > >队列。qlist['Alice', 'Bob', 'Charlie']
退出队列:
> > > queue.dequeue ()'Alice' >>>队列。qlist['Bob', 'Charlie'] >>> queue.dequeue() 'Bob' >>> queue.qlist ['Charlie'] >>> queue.dequeue() 'Charlie' >>>queue.qlist []
现在队列是空的,不能进行脱队列或偷看:
>>> queue.dequeue()队列下流>>> queue.peek()队列为空
时间复杂度
队列的时间复杂度取决于所使用的数据结构类型和构建的特定实现。下面是一些数据结构及其入队列和出队列的复杂度分析:
尽管这个概念可能很简单,但编程队列并不像编程堆栈那么简单。自助餐厅排队的例子再次解释了为什么a链表比an快多了数组当谈到出列:
一个人离开了自助餐厅的队伍。这个人背后的每个人都必须站出来。在数组中,这个过程一次发生一个人,一次只能有一个人移动。第一个人离开了。然后第二个人向前走,填补第一个人留下的空白,然后第三个人向前走,填补第二个人留下的空白,以此类推。这条线移动得确实很慢。
在最好的而且最坏的情况是,每个人都要前进1。这需要 时间,因为运动的次数取决于排队的人数。
然而,在链表的情况下,只有1人必须移动。这就像在自助餐厅排队,点菜的人向前走,而不是整个队伍。一旦链表让排在队列前面的人退出队列,下一个人就会成为队列的新前排。他们和其他排队的人都不需要往前走。因为这个操作不依赖于线的长度,它需要 或者常数,时间。
例子问题
假设有10个人在快餐店排队购买食物。假设这条线用a表示队列.
- 队伍的头在哪里,前面的人还是后面的人?
- 如果前面的人买了他们的食物然后离开,有多少人需要移动(不包括离开的人)?
- 这是O(n)次还是O(1)次?这个队列是使用数组还是链表实现的?
A1。队伍的头是排在队伍前面的人。
A2。9个人必须离开(10个人减去离开的1个人)。
A3。这是O(n)时间,因为它取决于排队的人数(在本例中为10)。这个队列是使用数组实现的。
标准应用程序
队列最常用于实现列表,以便以与条目到达的顺序相同的方式检索它们。它们在各个领域提供了许多实际应用,例如操作系统、邮件服务、CPU调度、电梯和键盘缓冲。
队列在网络中非常有用,尤其是在Internet上。例如,当你给同一个人发两条短信时,你的手机可能会显示“发送两条中的一条”。网络使用了一个队列来存储你的文本,这样它们就会按照你发送的顺序到达。或者,当你向一个网站发送数据时,你想确保数据以正确的顺序到达那里。所以,网站有一个队列,它收集你的数据,因为它等待它被处理。
循环队列
有几种实现队列的基本方法。第一种方法是创建一个数组并移动所有元素以适应入队列和出队列。正如我们上面看到的,这是缓慢的。
前一种方法的缓慢之处在于有很多元素,转换需要时间。因此,实现队列的另一种方法是移动入队点和出队点。在前面提到的自助餐厅排队的例子中,如果队伍在每个人离开队伍时不断向后移动,那么人们就不需要向前或向后走,从而节省时间。
然而,这为循环队列引入了一个重要的不变量——它们必须具有最大容量!否则,将无法知道您是否已经到达队列的末尾,并且将失去好处。
在此实现中,队列中使用占位符。这样,如果队列在中间清空自己,也不会失去它的位置。这也使用一个列表作为它的数据结构。下面的代码演示了循环队列的用法:
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
|
要理解这个循环实现,可以将数组看作一个圆。当一个元素从队列中退出时,队列不会将所有元素前移到队列的开头。相反,该类将队列的开始位置移回。最终,队列的开始位置将移动到超出数组结束位置的位置。这就是圆的作用。当队列到达数组的末尾时,它会绕到数组的开头。我们用模数学来做这个包装头和尾巴队列的。