利用Python列表实现栈
在Python中，列表是一种非常灵活的数据结构，可以用来实现多种数据结构，比如栈和队列。今天我们先来看看如何用列表实现栈。
1. 栈的基本概念
栈是一种后进先出（LIFO, Last In First Out）的数据结构。想象一下你把书一本一本地放在桌子上，每次只能拿最上面的一本书，这就是栈的工作方式。
2. 使用列表实现栈
Python列表提供了许多内置方法，可以很方便地用来实现栈的基本操作。我们主要会用到以下方法：
append(x): 将元素x添加到列表的末尾。pop(): 移除列表的最后一个元素并返回它。
示例代码
# 创建一个空的栈
stack = []
# 添加元素到栈中
stack.append(1)
stack.append(2)
stack.append(3)
print("栈的当前状态:", stack) # 输出: [1, 2, 3]
# 弹出栈顶元素
top_element = stack.pop()
print("弹出的元素:", top_element) # 输出: 3
print("栈的当前状态:", stack) # 输出: [1, 2]
3. 栈的常见操作
除了基本的入栈和出栈操作，我们还可以实现一些常见的栈操作，比如检查栈是否为空、获取栈的大小等。
示例代码
# 检查栈是否为空
def is_empty(stack):
return len(stack) == 0
# 获取栈的大小
def size(stack):
return len(stack)
# 示例
stack = []
print("栈是否为空:", is_empty(stack)) # 输出: True
stack.append(1)
print("栈的大小:", size(stack)) # 输出: 1
利用Python列表实现队列
接下来，我们来看看如何用列表实现队列。
1. 队列的基本概念
队列是一种先进先出（FIFO, First In First Out）的数据结构。想象一下你在银行排队，最先来的客户最先被服务，这就是队列的工作方式。
2. 使用列表实现队列
虽然Python列表可以用来实现队列，但直接使用列表的append和pop方法效率不高，因为pop(0)的时间复杂度是O(n)。为了提高效率，我们可以使用collections.deque，它是一个双端队列，支持两端高效的插入和删除操作。
示例代码
from collections import deque
# 创建一个空的队列
queue = deque()
# 添加元素到队列中
queue.append(1)
queue.append(2)
queue.append(3)
print("队列的当前状态:", queue) # 输出: deque([1, 2, 3])
# 弹出队首元素
front_element = queue.popleft()
print("弹出的元素:", front_element) # 输出: 1
print("队列的当前状态:", queue) # 输出: deque([2, 3])
3. 队列的常见操作
除了基本的入队和出队操作，我们还可以实现一些常见的队列操作，比如检查队列是否为空、获取队列的大小等。
示例代码
# 检查队列是否为空
def is_empty(queue):
return len(queue) == 0
# 获取队列的大小
def size(queue):
return len(queue)
# 示例
queue = deque()
print("队列是否为空:", is_empty(queue)) # 输出: True
queue.append(1)
print("队列的大小:", size(queue)) # 输出: 1
实战案例：使用栈和队列解决括号匹配问题
假设我们需要编写一个程序来检查一个字符串中的括号是否匹配。例如，输入字符串 "((()))" 应该返回 True，而输入字符串 "(())(" 应该返回 False。
1. 使用栈实现括号匹配
我们可以使用栈来解决这个问题。每当遇到左括号时，将其压入栈中；每当遇到右括号时，检查栈顶是否有对应的左括号。如果没有，说明括号不匹配。
示例代码
def is_parentheses_matched(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
# 测试
input_str = "((()))"
print(f"输入: {input_str}, 是否匹配: {is_parentheses_matched(input_str)}") # 输出: True
input_str = "(())("
print(f"输入: {input_str}, 是否匹配: {is_parentheses_matched(input_str)}") # 输出: False
2. 使用队列实现括号匹配
虽然使用栈是解决括号匹配问题的常用方法，但也可以尝试使用队列来实现。每当遇到左括号时，将其加入队列；每当遇到右括号时，检查队首是否有对应的左括号。如果没有，说明括号不匹配。
示例代码
from collections import deque
def is_parentheses_matched_with_queue(s):
queue = deque()
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping.values():
queue.append(char)
elif char in mapping.keys():
if not queue or queue.popleft() != mapping[char]:
return False
else:
continue
return not queue
# 测试
input_str = "((()))"
print(f"输入: {input_str}, 是否匹配: {is_parentheses_matched_with_queue(input_str)}") # 输出: True
input_str = "(())("
print(f"输入: {input_str}, 是否匹配: {is_parentheses_matched_with_queue(input_str)}") # 输出: False
总结
本文介绍了如何使用Python列表实现栈和队列，并通过具体的代码示例展示了栈和队列的基本操作。我们还通过一个实战案例，使用栈和队列解决了括号匹配问题。
好了，今天的分享就到这里了，我们下期见。如果本文对你有帮助，请动动你可爱的小手指点赞、转发、在看吧！
文末福利
公众号消息窗口回复“编程资料”，获取Python编程、人工智能、爬虫等100+本精品电子书。
