使用两个队列实现栈

1. Introduction

In this tutorial, we’re going to implement a stack data structure using two queues.

2. Stack and Queue Basics

Before proceeding to the algorithm, let’s first take a glance at these two data structures.

2.1. Stack

In a stack, we add elements in LIFO (Last In, First Out) order. This means that the last element inserted in the stack will be the first one removed. The basic operations of a stack are:

• push — insert an element at the top
• pop — remove an element from the top

2.2. Queue

In a queue, we add elements in FIFO (First In, First Out) order, meaning that the first element inserted is the first one to be removed. The basic operations of the queue are:

• enqueue — insert an element at the rear
• dequeue — remove an element from the front

3. Algorithm

To construct a stack using two queues (q1, q2), we need to simulate the stack operations by using queue operations:

• push (E element)
  • if q1 is empty, enqueue E to q1
  • if q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1
• pop
  • dequeue an element from q1

As we see, q1 acts as the main source for the stack, while q2 is just a helper queue that we use to preserve the order expected by the stack.

The pseudocode of the push is:

algorithm Push(q1, q2, E):
    // INPUT
    //   q1, q2 = two queues
    //   E = element to push to stack
    // OUTPUT
    //   element E is now at the head of queue q1
    if q1 is empty:
        q1.enqueue(E)
    else:
        q1Size <- q1.size()
        for i <- 1, 2, ..., q1Size:
            q2.enqueue(q1.dequeue())
        q1.enqueue(E)
        for j <- 1, 2, ..., q1Size:
            q1.enqueue(q2.dequeue())

Here’s the pseudocode of the pop operation:

algorithm Pop(q1):
    // INPUT
    //   q1, q2 = two queues
    // OUTPUT
    //   the head element of the queue q1 (which is removed from q1)
    element <- q1.dequeue()
    return element

The time complexity of the pop operation is O(1). For the push operation, we have a time complexity of O(n) because we have to transfer n-1 elements from q1 to q2 and back from q2 to q1.

4. Conclusion

In this tutorial, we presented the algorithm of constructing a stack using two queues.

Note that even if there’s no real advantage in doing this, it teaches us practical programming experience and shows us that we can combine and reuse data structures to achieve our goals. Stacks and queues are covered in greater detail in our article on common and useful data structures.