# Queue Implement Stack/Stack implement Queue

**Translator:****walsvid**

**Author:****labuladong**

Queue is a FIFO (first-in-first-out) strategy data structure, while Stack is a FILO (first-in-last-out) data structure. The visual description of these data structures is shown in the figure:

The basics of these two data structures are actually implemented by arrays or linked lists, but the API limits their behavior. So let's take a look at how to use "Stack" to implement a "Queue" and how to use "Queue" to implement a "Stack".

## 1. Using Stack to implement Queue

First, the API of Queue are as follows:

We can use two stacks `s1,s2`

to implement the function of a queue (it may be easier to understand to place the stack horizontally):

When calling `push`

to enqueue an element, we only need to push the element into `s1`

. For example, if we `push`

3 elements into 1,2,3, then the detailed structure is like this:

So what if using `peek`

to get the front element of the queue at this time? Logically speaking, the front element should be 1, but in `s1`

, 1 is pushed to the bottom of the stack. Now we can use `s2`

to transit elements. When `s2`

is empty, all elements of `s1`

can be moved to`s2`

, **at this time the elements in ****s2**** are FIFO (first-in-first-out) order**.

Similarly, for the `pop`

operation, we only need to operate `s2`

.

Finally, how to determine the queue is empty? If both stacks are empty, the queue is empty:

So far, we implement a queue with stacks. The core idea is to use two stacks to cooperate with each other.

It is worth mentioning, what is the time complexity of these operations? What's interesting is that the `peek`

operation may trigger a `while`

loop when it is called. In this case, the time complexity is $O(N)$, but in most cases, the `while`

loop will not be triggered and the time complexity is $O(1)$. Since the `pop`

operation calls `peek`

, its time complexity is the same as peek.

In this case, it can be said that their **worst time complexity** is $O(N)$, because, including a `while`

loop, it may be necessary to move elements from `s1`

to `s2`

.

However, their **average time complexity** is $O(1)$. We can understand it in this way: For an element, it can only be moved at most once, which means that the average time complexity of each element of the `peek`

operation is $O(1)$.

## 2. Using Queue to implement Stack

If it is tricky to use 2 stacks to implement a queue, then using queue to implement stack is much more straightforward, requiring only one queue as the basic data structure.

First, the API of stack are as follows:

Let's talk about the `push`

API first. We can add elements directly to the queue, and record the rear element at the same time. Since the rear element is equivalent to the top element of the stack, if we want to use `top`

to get the top element of the stack, we can directly return it:

Our basic data structure is a FIFO queue, and each `pop`

can only take elements in front of the queue; But the stack is FILO, which means the `pop`

API takes elements from the rear of the queue.

The solution is simple. We can take out the front element of the queue and add it to the rear of the queue, and let the previous rear element line up to the head of the queue, and then we can take it out:

There is still a small problem with this implementation. The original rear element has reached to the head of the queue and has been deleted, but the `top_elem`

variable was not updated. We need a little modification:

In the end, the `empty`

API is easy to implement, just check if the underlying queue is empty:

Obviously, if we implement a stack with a queue, the time complexity of the `pop`

operation is $O(N)$, and all other operations are $O(1)$.

I think that implement a stack with a queue is a trivial problem, but **implement a queue with a dual stack is worth learning**.

After moving elements from stack `s1`

to `s2`

, the elements become the FIFO order of the queue in s2. This feature is similar to "Two negatives make an affirmative.," which is not easy to think.

I hope this article is helpful to you.

"Stick to original high-quality articles, and work hard to make algorithmic problems clear."

Last updated