堆栈 (Stack)
堆栈是一种后进先出 (LIFO) 的数据结构。 想象一下一叠盘子：你只能从顶部添加或移除盘子。
- 压栈 (push): 将元素添加到堆栈顶部。
- 出栈 (pop): 从堆栈顶部移除并返回元素。
堆栈的应用场景包括函数调用、撤销操作、浏览器历史记录、表达式求值、语法分析和深度优先搜索 (DFS) 等。
使用数组实现堆栈:
以下 Python 代码演示了使用数组实现堆栈：
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
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
队列 (Queue)
队列是一种先进先出 (FIFO) 的数据结构。 就像排队一样，先进入队列的元素先被处理。
- 入队 (enqueue): 将元素添加到队列尾部。
- 出队 (dequeue): 从队列头部移除并返回元素。
队列的应用场景包括任务调度、广度优先搜索 (BFS)、打印队列、网络路由、呼叫中心、流媒体和事件处理等。
使用数组实现队列:
以下 Python 代码演示了使用数组实现队列：
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
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
使用堆栈实现队列:
可以使用两个堆栈来模拟队列的行为。
class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, item):
self.stack1.append(item)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2.pop()
return None
def peek(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2[-1]
return None
def is_empty(self):
return not self.stack1 and not self.stack2
使用队列实现堆栈:
同样，可以使用两个队列来模拟堆栈的行为。 （代码略，原理与上面类似，只是入队和出队的操作顺序不同）
这些代码示例提供了堆栈和队列的基本实现，以及如何使用它们来模拟彼此的功能。 实际应用中可能需要考虑更高级的特性，例如容量限制和异常处理。
