栈与队列 || Python || 数据结构与算法

 

栈 – 它是一种存储容器,支持后进先出(LIFO)顺序的检索。当检索顺序完全不重要时,例如在处理批处理作业时,栈可能是合适的容器。

 

例如, 考虑自助餐厅中使用的盘子堆:从堆中取出盘子的顺序与添加盘子的顺序相反,因为只有最上面的盘子是可访问的。

 

在栈上的插入操作通常称为 PUSH,而删除操作(不需要元素参数)通常称为 POP。

 

Push (x,s): 将项 x 插入到栈 s 的顶部。

 

Pop(s) : 返回(并移除)栈 s 的顶部项。

 

放入我冰箱的食物通常以相同的方式退出,尽管有过期日期的激励。从算法的角度来看,在执行递归算法的过程中,LIFO 往往会发生。

 

栈的应用 –

 

    1. 函数调用: 用于管理函数执行和递归。

 

    1. 撤销操作: 跟踪编辑器中的更改以实现“撤销/重做”。

 

    1. 浏览器历史: 存储访问过的页面以便回溯。

 

表达式解析: 评估并转换数学表达式。

  • 语法验证: 匹配代码中的括号或标签。
  • 内存管理: 在程序执行期间管理调用栈。
  • 深度优先搜索(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的前端项。

队列有一个头和一个尾。

  • 当一个元素入队时,它会在队列的尾部占据一个位置,就像新到达的顾客在队伍的末尾排队一样。
  • 出队的元素总是队列头部的元素,就像排队的顾客中等待时间最长的那位。

队列的应用 –

  1. 任务调度: 按顺序管理CPU进程和作业。
  2. BFS: 在图中实现广度优先搜索。
  3. 打印队列: 顺序处理打印作业。
  4. 网络路由: 缓冲数据包以进行传输。
  5. 呼叫中心: 按等待顺序管理客户电话。
  6. 流媒体: 实时缓冲视频或音频流。
  7. 输入事件: 在图形用户界面系统中处理键盘和鼠标输入。

使用数组实现队列 –

  • 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

更多