一、栈和队列的基本介绍
栈（Stack）和队列（Queue）是两种经典的数据结构，用于在计算机程序中存储和管理数据。栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。队列是一种先进先出（FIFO）的数据结构，只允许在队列尾部进行插入操作，在队列头部进行删除操作。
下面是栈和队列的简单Python代码实现：
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
二、基本操作的差异
栈和队列的主要区别在于它们的基本操作。在栈中，元素的插入和删除只能在栈顶进行，而队列中元素的插入只能在队列尾部进行，删除操作则只能在队列头部进行。这意味着在栈中最后插入的元素会被最先删除，而在队列中最先插入的元素会被最先删除。
下面是分别实现了栈和队列的基本操作代码：
# 栈
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
# 队列
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
三、性能差异
栈和队列的另一个主要区别是它们的性能差异。在栈中，插入和删除操作的时间复杂度都是O(1)，因为只需要操作栈顶的元素。而在队列中，插入操作的时间复杂度也是O(1)，但删除操作的时间复杂度为O(n)，因为需要将所有的元素向前移动一位。
下面是分别实现了栈和队列的性能比较代码：
import time
# 栈
s = Stack()
start = time.time()
for i in range(1000000):
s.push(i)
while not s.is_empty():
s.pop()
end = time.time()
print("Time used for Stack:", end-start)
# 队列
q = Queue()
start = time.time()
for i in range(1000000):
q.enqueue(i)
while not q.is_empty():
q.dequeue()
end = time.time()
print("Time used for Queue:", end-start)
四、应用场景的不同
栈和队列在不同的应用场景中有不同的用途。栈通常用于处理递归和回溯问题，以及表达式的计算和括号匹配。队列则常用于解决如广度优先搜索（BFS）等问题。同时，队列还常被用于实现具有缓冲区的数据传输。
下面是栈和队列分别应用于表达式括号匹配的代码实现：
# 栈应用：表达式括号匹配
def is_balanced(expr):
s = Stack()
for char in expr:
if char in ['(', '[', '{']:
s.push(char)
elif char in [')', ']', '}']:
if s.is_empty():
return False
top = s.pop()
if not is_match(top, char):
return False
return s.is_empty()
def is_match(p1, p2):
return (p1 == '(' and p2 == ')') or (p1 == '[' and p2 == ']') or (p1 == '{' and p2 == '}')
print(is_balanced("(Pangolin)[Python]")) # True
print(is_balanced("{Python(Jupyter)}[Java]")) # True
print(is_balanced("({Python][Jupyter)}")) # False
# 队列应用：BFS实现图的遍历
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
bfs(graph, 'A')
# 输出：A B C D E F
