栈
栈 – 它是一种存储容器,支持后进先出(LIFO)顺序的检索。当检索顺序完全不重要时,例如在处理批处理作业时,栈可能是合适的容器。
例如, 考虑自助餐厅中使用的盘子堆:从堆中取出盘子的顺序与添加盘子的顺序相反,因为只有最上面的盘子是可访问的。
在栈上的插入操作通常称为 PUSH,而删除操作(不需要元素参数)通常称为 POP。
Push (x,s): 将项 x 插入到栈 s 的顶部。
Pop(s) : 返回(并移除)栈 s 的顶部项。
放入我冰箱的食物通常以相同的方式退出,尽管有过期日期的激励。从算法的角度来看,在执行递归算法的过程中,LIFO 往往会发生。
栈的应用 –
-
- 函数调用: 用于管理函数执行和递归。
-
- 撤销操作: 跟踪编辑器中的更改以实现“撤销/重做”。
-
- 浏览器历史: 存储访问过的页面以便回溯。
表达式解析: 评估并转换数学表达式。
- 语法验证: 匹配代码中的括号或标签。
- 内存管理: 在程序执行期间管理调用栈。
- 深度优先搜索(DFS): 在图算法中实现深度优先搜索。
使用数组实现栈 –
- push() – 将元素插入栈中。
- pop() – 从栈中移除元素。
- top() – 返回栈顶元素。
- isEmpty() – 如果栈为空则返回真,否则返回假。
class Stack:
def __init__(self):
# 初始化一个空栈
self.stack = []
def isEmpty(self) -> bool:
# 如果栈为空则返回 True,否则返回 False。
return len(self.stack) == 0
def push(self, item) -> None:
# 将一个项目推入栈中。
self.stack.append(item)
def pop(self):
# 移除并返回栈顶项目。
if self.isEmpty():
return None
return self.stack.pop()
def peek(self):
# 返回栈顶项目而不移除它。
if self.isEmpty():
return None
return self.stack[-1]
队列
队列 – 它是一种存储容器,支持按先进先出(FIFO)顺序检索。我们将队列上的插入操作称为入队(ENQUEUE),将删除操作称为出队(DEQUEUE)。与栈操作POP类似,出队操作不需要元素参数。栈和队列都是动态集合,其中通过删除操作从集合中移除的元素是预定义的。
Enqueue(x,q): 将项x插入到队列q的末尾。
Dequeue(q): 返回(并移除)队列q的前端项。
队列有一个头和一个尾。
- 当一个元素入队时,它会在队列的尾部占据一个位置,就像新到达的顾客在队伍的末尾排队一样。
- 出队的元素总是队列头部的元素,就像排队的顾客中等待时间最长的那位。
队列的应用 –
- 任务调度: 按顺序管理CPU进程和作业。
- BFS: 在图中实现广度优先搜索。
- 打印队列: 顺序处理打印作业。
- 网络路由: 缓冲数据包以进行传输。
- 呼叫中心: 按等待顺序管理客户电话。
- 流媒体: 实时缓冲视频或音频流。
- 输入事件: 在图形用户界面系统中处理键盘和鼠标输入。
使用数组实现队列 –
- enqueue() – 向队列中插入元素。
- dequeue() – 从队列中移除元素。
- peek() 或 front() – 获取队列前端节点的可用数据元素而不删除它。
- isEmpty() – 检查队列是否为空。
class MyQueue:
def __init__(self):
# 存储元素
self.queue = []
# 指示起始位置的指针
self.p_start = 0
def enQueue(self, x):
# 将元素插入队列。
self.queue.append(x)
return True # 如果操作成功,返回 True
def deQueue(self):
# 从队列中删除一个元素。
if self.isEmpty():
return False
self.p_start += 1
return True # 如果操作成功,返回 True
def Front(self):
# 获取队列中的前一个元素。
if not self.isEmpty():
return self.queue[self.p_start]
return None # 如果队列为空,返回 None
def isEmpty(self):
# 检查队列是否为空
return self.p_start >= len(self.queue)
使用栈实现队列 –
-
-
push(x) - 将所有元素从栈1移动到栈2,以反转它们的顺序,然后再将所有元素从栈2移动回栈1。
-
-
- pop() – 从队列的前端移除元素并返回该元素
-
- peek() – 返回队列前端的元素
-
- empty() – 如果队列为空则返回true,否则返回false
class MyQueue:
def __init__(self):
self.stack_1 = [] # 主栈用于入队操作
self.stack_2 = [] # 临时栈用于出队操作
self.front = None
# 将元素 x 推入队列的末尾。
def push(self, x):
# 将所有元素从栈1移动到栈2以反转它们的顺序
while self.stack_1:
self.stack_2.append(self.stack_1.pop())
self.stack_2.append(x)
# 将所有元素从栈2移动回栈1作为队列
while self.stack_2:
self.stack_1.append(self.stack_2.pop())
# 从队列的前端移除元素并返回该元素
def pop(self):
return self.stack_1.pop()
# 返回队列前端的元素
def peek(self):
return self.stack_1[-1]
# 如果队列为空则返回true,否则返回false
def empty(self):
return not self.stack_1
使用队列实现栈 –
- push(x) – 将新元素添加到第二个队列,然后将队列1中的所有元素移动到队列2,以保持栈的顺序(后进先出),并交换两个队列。
- pop() – 移除栈顶元素并返回该元素
- peek 或 top() – 返回队列前面的元素
- empty() – 如果队列为空则返回真,否则返回假
class MyStack:
def __init__(self):
# 初始化两个队列以进行栈操作
self.queue1 = [] # 主队列用于存放元素
self.queue2 = [] # 在推送过程中使用的临时队列
# 将元素 x 推送到栈顶
python
def push(self, x: int) -> None:
# 将新元素添加到第二个队列
self.queue2.append(x)
# 将所有元素从队列1移动到队列2,以保持栈的顺序(后进先出)
while len(self.queue1) > 0:
self.queue2.append(self.queue1.pop(0))
# 交换队列
self.queue1, self.queue2 = self.queue2, self.queue1
# 移除栈顶元素并返回它
def pop(self) -> int:
return self.queue1.pop(0)
# 返回栈顶元素
def top(self) -> int:
return self.queue1[0]
# 如果栈为空则返回真,否则返回假
def empty(self) -> bool:
return len(self.queue1) == 0