LogicLab

Appearance

用双栈模拟队列 ​

题目描述 ​

  1. 利用两个顺序栈S1和S2模拟一个队列。请使用栈的基本操作实现队列的入队和出队操作，并阐述实现的基本思路。

答案与详解 ​

🧠 基本思路 ​

通过两个栈的互补协作实现队列的FIFO特性：

  • S1（入队栈）：负责处理入队操作
  • S2（出队栈）：负责处理出队操作
操作类型实现方式
入队直接将元素压入S1
出队分情况处理：
1. S2非空时直接弹出
2. S2空但S1非空时转移元素
3. 双栈皆空时报错

⚙️ 算法步骤 ​

python
# 入队操作
def enqueue(x):
    S1.push(x)

# 出队操作
def dequeue():
    if not S2.is_empty():
        return S2.pop()
    elif not S1.is_empty():
        while not S1.is_empty():
            S2.push(S1.pop())
        return S2.pop()
    else:
        raise Exception("Queue is empty")