堆栈是一种后进先出 (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
使用队列实现堆栈:
同样，可以使用两个队列来模拟堆栈的行为。 （代码略，原理与上面类似，只是入队和出队的操作顺序不同）
这些代码示例提供了堆栈和队列的基本实现，以及如何使用它们来模拟彼此的功能。 实际应用中可能需要考虑更高级的特性，例如容量限制和异常处理。
