3.4. 栈的抽象数据类型¶

3.4. The Stack Abstract Data Type

中文英文

栈的抽象数据类型由以下结构和操作定义。栈如前所述，是一个有序的项目集合，其中项目被添加到并从称为顶部的端移除。栈的顺序是后进先出（LIFO）。栈的操作如下所示。

Stack() 创建一个新的空栈。它不需要参数并返回一个空栈。
push(item) 将一个新项目添加到栈的顶部。它需要一个项目作为参数，并且不返回任何值。
pop() 从栈中移除顶部的项目。它不需要参数，并返回被移除的项目。栈会被修改。
peek() 返回栈中的顶部项目，但不将其移除。它不需要参数。栈不会被修改。
is_empty() 测试栈是否为空。它不需要参数，并返回一个布尔值。
size() 返回栈中项目的数量。它不需要参数，并返回一个整数。

例如，如果s是一个已创建并开始时为空的栈，那么表 1显示了一系列栈操作的结果。在栈内容下，顶部项目在最右侧列出。

表 1: 示例栈操作

栈操作	栈内容	返回值
`s.is_empty()`	`[]`	`True`
`s.push(4)`	`[4]`
`s.push('dog')`	`[4, 'dog']`
`s.peek()`	`[4, 'dog']`	`'dog'`
`s.push(True)`	`[4, 'dog', True]`
`s.size()`	`[4, 'dog', True]`	`3`
`s.is_empty()`	`[4, 'dog', True]`	`False`
`s.push(8.4)`	`[4, 'dog', True, 8.4]`
`s.pop()`	`[4, 'dog', True]`	`8.4`
`s.pop()`	`[4, 'dog']`	`True`
`s.size()`	`[4, 'dog']`	`2`

The stack abstract data type is defined by the following structure and operations. A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the top. Stacks are ordered LIFO. The stack operations are given below.

Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
is_empty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
size() returns the number of items on the stack. It needs no parameters and returns an integer.

For example, if s is a stack that has been created and starts out empty, then Table 1 shows the results of a sequence of stack operations. Under Stack Contents, the top item is listed at the far right.

Table 1: Sample Stack Operations

Stack Operation	Stack Contents	Return Value
`s.is_empty()`	`[]`	`True`
`s.push(4)`	`[4]`
`s.push('dog')`	`[4, 'dog']`
`s.peek()`	`[4, 'dog']`	`'dog'`
`s.push(True)`	`[4, 'dog', True]`
`s.size()`	`[4, 'dog', True]`	`3`
`s.is_empty()`	`[4, 'dog', True]`	`False`
`s.push(8.4)`	`[4, 'dog', True, 8.4]`
`s.pop()`	`[4, 'dog', True]`	`8.4`
`s.pop()`	`[4, 'dog']`	`True`
`s.size()`	`[4, 'dog']`	`2`

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