3.11. 队列的抽象数据类型¶

3.11. The Queue Abstract Data Type

原文: https://runestone.academy/ns/books/published/pythonds3/BasicDS/TheQueueAbstractDataType.html?mode=browsing

中文英文

队列抽象数据类型由以下结构和操作定义。队列的结构如上所述，是一个有序的项集合，新项在一个端点添加，称为尾部，而从另一个端点移除，称为前端。队列保持 FIFO（先进先出）排序属性。队列操作如下：

Queue() 创建一个新的空队列。它不需要参数，返回一个空队列。
enqueue(item) 将一个新项添加到队列的尾部。它需要项作为参数，不返回任何值。
dequeue() 从队列的前端移除一个项。它不需要参数，返回该项。队列会被修改。
is_empty() 测试队列是否为空。它不需要参数，返回布尔值。
size() 返回队列中项的数量。它不需要参数，返回一个整数。

作为示例，假设 q 是一个已经创建并且当前为空的队列，Table 5 显示了一系列队列操作的结果。队列的内容显示如下，前端在右侧。第一个入队的项是 4，因此它是 dequeue 返回的第一个项。

表 5：队列操作示例

队列操作	队列内容	返回值
`q.is_empty()`	`[]`	`True`
`q.enqueue(4)`	`[4]`
`q.enqueue("dog")`	`['dog', 4]`
`q.enqueue(True)`	`[True, 'dog', 4]`
`q.size()`	`[True, 'dog', 4]`	`3`
`q.is_empty()`	`[True, 'dog', 4]`	`False`
`q.enqueue(8.4)`	`[8.4, True, 'dog', 4]`
`q.dequeue()`	`[8.4, True, 'dog']`	`4`
`q.dequeue()`	`[8.4, True]`	`'dog'`
`q.size()`	`[8.4, True]`	`2`

The queue abstract data type is defined by the following structure and operations. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the rear, and removed from the other end, called the front. Queues maintain a FIFO ordering property. The queue operations are given below.

Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
is_empty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
size() returns the number of items in the queue. It needs no parameters and returns an integer.

As an example, if we assume that q is a queue that has been created and is currently empty, then Table 5 shows the results of a sequence of queue operations. The queue contents are shown such that the front is on the right. The first item enqueued was 4 so it is the first item returned by dequeue.

Table 5: Example Queue Operations

Queue Operation	Queue Contents	Return Value
`q.is_empty()`	`[]`	`True`
`q.enqueue(4)`	`[4]`
`q.enqueue("dog")`	`['dog',4]`
`q.enqueue(True)`	`[True, 'dog', 4]`
`q.size()`	`[True, 'dog', 4]`	`3`
`q.is_empty()`	`[True, 'dog', 4]`	`False`
`q.enqueue(8.4)`	`[8.4,True, 'dog', 4]`
`q.dequeue()`	`[8.4, True, 'dog']`	`4`
`q.dequeue()`	`[8.4, True]`	`'dog'`
`q.size()`	`[8.4, True]`	`2`

最后更新: 2024年9月12日
创建日期: 2024年9月9日