利用Python列表实现栈和队列：数据结构基础实战

包含编程籽料、学习路线图、爬虫代码、安装包等！【点击这里】领取！

前言
在编程中，栈(Stack)和队列(Queue)是两种最基础且重要的数据结构。Python的内置列表(list)提供了灵活的操作方法，可以轻松实现这两种数据结构。本文将详细介绍如何使用Python列表来模拟栈和队列的操作，并分析它们的应用场景。

一、栈(Stack)的实现

1. 栈的基本概念
   栈是一种后进先出(LIFO, Last In First Out)的数据结构，可以想象成一摞盘子，你只能从最上面取放盘子。

栈主要有两种基本操作：

push：将元素压入栈顶

pop：从栈顶弹出元素

2. 使用Python列表实现栈

# 创建一个空栈
stack = []

# 压栈操作(push)
stack.append(1)  # 栈: [1]
stack.append(2)  # 栈: [1, 2]
stack.append(3)  # 栈: [1, 2, 3]

# 弹栈操作(pop)
print(stack.pop())  # 输出: 3, 栈: [1, 2]
print(stack.pop())  # 输出: 2, 栈: [1]
print(stack.pop())  # 输出: 1, 栈: []

3. 栈的其他常用操作

# 查看栈顶元素(不弹出)
if stack:
    print(stack[-1])  # 栈顶元素

# 判断栈是否为空
print(len(stack) == 0)  # 或者 not stack

# 获取栈的大小
print(len(stack))

4. 栈的应用场景
   函数调用栈

表达式求值

括号匹配检查

浏览器前进后退功能

深度优先搜索(DFS)

二、队列(Queue)的实现

1. 队列的基本概念
   队列是一种先进先出(FIFO, First In First Out)的数据结构，就像排队买票，先来的人先得到服务。

队列主要有两种基本操作：

enqueue：将元素加入队尾

dequeue：从队首取出元素

2. 使用Python列表实现简单队列

# 创建一个空队列
queue = []

# 入队操作(enqueue)
queue.append(1)  # 队列: [1]
queue.append(2)  # 队列: [1, 2]
queue.append(3)  # 队列: [1, 2, 3]

# 出队操作(dequeue)
print(queue.pop(0))  # 输出: 1, 队列: [2, 3]
print(queue.pop(0))  # 输出: 2, 队列: [3]
print(queue.pop(0))  # 输出: 3, 队列: []

3. 列表实现队列的效率问题
   虽然上述方法简单，但使用pop(0)操作的时间复杂度是O(n)，因为需要移动所有剩余元素。对于频繁的队列操作，推荐使用collections.deque：

from collections import deque

# 使用deque创建队列
queue = deque()

# 入队
queue.append(1)
queue.append(2)
queue.append(3)

# 出队
print(queue.popleft())  # 输出: 1
print(queue.popleft())  # 输出: 2
print(queue.popleft())  # 输出: 3

deque的popleft()操作时间复杂度是O(1)，效率更高。

4. 队列的其他常用操作

# 查看队首元素(不取出)
if queue:
    print(queue[0])

# 判断队列是否为空
print(len(queue) == 0)  # 或者 not queue

# 获取队列大小
print(len(queue))

5. 队列的应用场景
   任务调度

消息队列

广度优先搜索(BFS)

打印机任务队列

客服系统排队

三、双端队列(Deque)的实现
双端队列是一种两端都可以进行插入和删除操作的数据结构，可以看作是栈和队列的结合。

使用collections.deque实现：

from collections import deque

d = deque()

# 从右侧添加
d.append(1)    # deque([1])
d.append(2)    # deque([1, 2])

# 从左侧添加
d.appendleft(3) # deque([3, 1, 2])

# 从右侧弹出
print(d.pop())  # 输出: 2, deque([3, 1])

# 从左侧弹出
print(d.popleft())  # 输出: 3, deque([1])

四、性能比较

从表中可以看出，对于队列实现，deque在删除元素时性能更优。

五、实际应用示例

1. 使用栈实现括号匹配检查

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping.keys():
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            continue
    
    return not stack

print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("([)]"))    # False

2. 使用队列实现简单的消息处理系统

from collections import deque

class MessageQueue:
    def __init__(self):
        self.queue = deque()
    
    def enqueue(self, message):
        self.queue.append(message)
        print(f"消息 '{message}' 已加入队列")
    
    def dequeue(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"处理消息: '{message}'")
            return message
        else:
            print("队列为空")
            return None

mq = MessageQueue()
mq.enqueue("任务1")
mq.enqueue("任务2")
mq.dequeue()
mq.dequeue()
mq.dequeue()

六、总结
Python列表可以方便地实现栈和队列的基本功能

对于栈操作，使用列表的append()和pop()方法非常高效

对于队列操作，建议使用collections.deque以获得更好的性能

栈和队列是许多算法的基础，理解它们的实现和应用非常重要

最后：
希望你编程学习上不急不躁,按照计划有条不紊推进,把任何一件事做到极致,都是不容易的,加油,努力！相信自己！

文末福利
最后这里免费分享给大家一份Python全套学习资料，希望能帮到那些不满现状，想提升自己却又没有方向的朋友，也可以和我一起来学习交流呀。

包含编程资料、学习路线图、源代码、软件安装包等！【点击这里】领取！
① Python所有方向的学习路线图，清楚各个方向要学什么东西
② 100多节Python课程视频，涵盖必备基础、爬虫和数据分析
③ 100多个Python实战案例，学习不再是只会理论
④ 华为出品独家Python漫画教程，手机也能学习