当前位置：首页 > news >正文

Python 数据结构揭秘：栈与队列

news 2025/7/10 20:17:30

栈（Stack）

定义

栈是一种后进先出（Last In First Out, LIFO）的数据结构。它类似于一个容器，只能在一端进行插入和删除操作。栈有两个主要的操作：push（入栈）和 pop（出栈）.

基本操作

push（入栈）：将一个元素添加到栈顶.
```
def push(self, item):self.items.append(item)
```

pop（出栈）：移除栈顶的元素，并返回该元素.

def pop(self):if not self.is_empty():return self.items.pop()return None

peek（查看栈顶元素）：查看栈顶的元素，但不移除它.

def peek(self):if not self.is_empty():return self.items[-1]return None

is_empty（检查栈是否为空）：判断栈是否为空.
```
def is_empty(self):return len(self.items) == 0
```
size（获取栈的大小）：返回栈中元素的数量.
```
def size(self):return len(self.items)
```

实现方式

栈可以用数组或链表来实现。以下是使用 Python 列表实现栈的完整示例：

class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()return Nonedef peek(self):if not self.is_empty():return self.items[-1]return Nonedef is_empty(self):return len(self.items) == 0def size(self):return len(self.items)

应用场景

函数调用栈：在编程语言中，函数调用时会使用栈来存储函数的局部变量和返回地址等信息.
表达式求值：用于计算算术表达式，如逆波兰表达式（后缀表达式）的求值.
回溯算法：如迷宫求解、八皇后问题等，使用栈来保存回溯过程中的状态.
页面浏览历史：浏览器的前进和后退功能可以使用栈来实现.

队列（Queue）

定义

队列是一种先进先出（First In First Out, FIFO）的数据结构。它类似于一个队列，元素从一端进入，从另一端出去。队列有两个主要的操作：enqueue（入队）和 dequeue（出队）.

基本操作

enqueue（入队）：将一个元素添加到队列的尾部.
```
def enqueue(self, item):self.items.append(item)
```

dequeue（出队）：移除队列头部的元素，并返回该元素.

def dequeue(self):if not self.is_empty():return self.items.pop(0)return None

peek（查看队首元素）：查看队列头部的元素，但不移除它.
```
def peek(self):if not self.is_empty():return self.items[0]return None
```
is_empty（检查队列是否为空）：判断队列是否为空.
```
def is_empty(self):return len(self.items) == 0
```
size（获取队列的大小）：返回队列中元素的数量.
```
def size(self):return len(self.items)
```

实现方式

队列可以用数组或链表来实现。以下是使用 Python 列表实现队列的完整示例：

class Queue:def __init__(self):self.items = []def enqueue(self, item):self.items.append(item)def dequeue(self):if not self.is_empty():return self.items.pop(0)return Nonedef peek(self):if not self.is_empty():return self.items[0]return Nonedef is_empty(self):return len(self.items) == 0def size(self):return len(self.items)