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

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

article 2025/1/7 13:15:11

栈（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 None

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

    def is_empty(self):
        return len(self.items) == 0

    def 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 None

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

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)