使用两个栈来实现队列

Question

使用两个栈来实现队列的思路如下：

1. 创建两个栈 stack1 和 stack2 ， stack1 用来存储入队的元素， stack2 用来存储出队的元素。
2. 入队操作：将元素依次压入 stack1 中。
3. 出队操作：先判断 stack2 是否为空，若不为空，则直接从 stack2 弹出栈顶元素；若为空，则依次将 stack1 中的元素弹出并压入 stack2 中，再从 stack2 弹出栈顶元素。
4. 先判断 stack2 是否为空，若不为空，则栈顶元素即为队首元素；若为空，则需要将 stack1 中的元素依次弹出并压入 stack2 中，再弹出 stack2 的栈顶元素。

这样就能通过两个栈来实现队列的功能。

这是使用两个栈来实现队列的示例代码，示例代码使用 Python 语言实现：

class MyQueue:
    def __init__(self):
        self.stack1 = []  # 用于入队操作
        self.stack2 = []  # 用于出队操作

    def push(self, element):
        self.stack1.append(element)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        if self.stack2:
            return self.stack2.pop()
        else:
            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]
        else:
            return None

    def is_empty(self):
        return len(self.stack1) == 0 and len(self.stack2) == 0

在这个示例代码中，我们定义了一个 MyQueue 类，其中包含了 push 、 pop 、 peek 和 is_empty 四个方法来模拟队列的入队、出队、查看队首元素以及判断队列是否为空的操作。

使用两个栈 stack1 和 stack2 来实现队列的操作：

1. 入队操作：将元素依次压入 stack1 中，时间复杂度为 O(1)。
2. 出队操作：先判断 stack2 是否为空，若不为空，则直接从 stack2 弹出栈顶元素；若为空，则将 stack1 中的元素依次弹出并压入 stack2 中，再从 stack2 弹出栈顶元素。时间复杂度为 O(n)。
3. 查看队首元素操作：先判断 stack2 是否为空，若不为空，则栈顶元素即为队首元素；若为空，则需要将 stack1 中的元素依次弹出并压入 stack2 中，再返回 stack2 的栈顶元素。时间复杂度为 O(n)。
4. 判断队列是否为空操作：只需要判断 stack1 和 stack2 是否都为空即可。时间复杂度为 O(1)。

因此，使用两个栈来实现队列的操作，时间复杂度主要取决于出队和查看队首元素操作，均为 O(n)。