3.16. 双端队列的抽象数据类型

3.16. The Deque Abstract Data Type

中文英文

双端队列（deque）抽象数据类型的结构和操作定义如下。双端队列如上所述，是一个有序项的集合，项可以从前端或后端添加和移除。双端队列的操作如下所示：

• Deque() 创建一个新的空双端队列。此操作不需要参数，并返回一个空的双端队列。

• add_front(item) 将新项添加到双端队列的前端。此操作需要项作为参数，并且不返回任何值。

• add_rear(item) 将新项添加到双端队列的后端。此操作需要项作为参数，并且不返回任何值。

• remove_front() 从双端队列的前端移除一个项。此操作不需要参数，并返回被移除的项。双端队列会被修改。

• remove_rear() 从双端队列的后端移除一个项。此操作不需要参数，并返回被移除的项。双端队列会被修改。

• is_empty() 测试双端队列是否为空。此操作不需要参数，并返回一个布尔值。

• size() 返回双端队列中项的数量。此操作不需要参数，并返回一个整数。

例如，如果假设 d 是一个已经创建并且当前为空的双端队列，那么 表6 显示了一系列双端队列操作的结果。注意，前端的内容列在右侧。跟踪前端和后端是非常重要的，因为在往双端队列中添加和移除项时，情况可能会变得有些混乱。

表6：双端队列操作示例

双端队列操作	双端队列内容	返回值
d.is_empty()	[]	True
d.add_rear(4)	[4]
d.add_rear("dog")	['dog', 4]
d.add_front("cat")	['dog', 4, 'cat']
d.add_front(True)	['dog', 4, 'cat', True]
d.size()	['dog', 4, 'cat', True]	4
d.is_empty()	['dog', 4, 'cat', True]	False
d.add_rear(8.4)	[8.4, 'dog', 4, 'cat', True]
d.remove_rear()	['dog', 4, 'cat', True]	8.4
d.remove_front()	['dog', 4, 'cat']	True

The deque abstract data type is defined by the following structure and operations. A deque is structured, as described above, as an ordered collection of items where items are added and removed from either end, either front or rear. The deque operations are given below.

• Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.

• add_front(item) adds a new item to the front of the deque. It needs the item and returns nothing.

• add_rear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.

• remove_front() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.

• remove_rear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.

• is_empty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.

• size() returns the number of items in the deque. It needs no parameters and returns an integer.

As an example, if we assume that d is a deque that has been created and is currently empty, then Table 6 shows the results of a sequence of deque operations. Note that the contents in front are listed on the right. It is very important to keep track of the front and the rear as you move items in and out of the collection as things can get a bit confusing.

Table 6: Examples of Deque Operations

Deque Operation	Deque Contents	Return Value
d.is_empty()	[]	True
d.add_rear(4)	[4]
d.add_rear("dog")	['dog', 4]
d.add_front("cat")	['dog', 4, 'cat']
d.add_front(True)	['dog', 4, 'cat', True]
d.size()	['dog', 4, 'cat', True]	4
d.is_empty()	['dog', 4, 'cat', True]	False
d.add_rear(8.4)	[8.4,'dog', 4, 'cat', True]
d.remove_rear()	['dog', 4, 'cat', True]	8.4
d.remove_front()	['dog', 4, 'cat']	True

---

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