   # Implementing a Queue Using a Stack Sven Woltmann
Last update: June 8, 2022

In this part of the tutorial series, I'll show you how to implement a queue using a stack (more precisely, using two stacks).

This variant has no practical use but is primarily an exercise task. As such, it is the counterpart to implementing a stack with a queue.

As a reminder, a stack is a data structure where elements are retrieved in the reverse order of insertion, i.e., a last-in-first-out (LIFO) data structure.

How can we use it to implement a queue, that is, a first-in-first-out (FIFO) data structure?

## The Solution – Step by Step

We put the first element that we insert into the queue on a stack (in the example: "banana"). To remove it from the queue, we take it from the stack again:

That will no longer work with the second element since the stack works according to the LIFO principle. If, for example, "banana" and "cherry" are on the stack, we would have to take "cherry" first:

In a queue, however, we want the first element inserted (i.e., "banana") to be the first to be removed.

With a stack alone, this is not possible.

Instead, we proceed as follows when inserting an element into the queue:

1. We create a temporary stack (shown in orange in the image below) and move all the elements of the original stack to the temporary stack.
2. We put the new element on the original stack.
3. We move all elements back from the temporary stack to the original stack. The temporary stack is then no longer needed.

The following illustration shows these three steps:

After that, the elements are on the stack in such a way that we can take the first inserted element, "banana", first and then the second inserted element, "cherry".

That works not only with two elements but with any number of elements. The following image shows how we insert the third element, "grape", into the queue:

After that, we can take the elements out of the queue in first-in-first-out order, so first, the "banana", which we inserted first, then the "cherry", and finally the "grape" inserted last.

## Source Code for the Queue with Stacks

The source code for this algorithm requires only a few lines of code.

As a stack, I use the ArrayStack class presented in the Stack tutorial. You could just as well use the JDK class `Stack` or any `Deque` implementation, e.g., an ArrayDeque.

You can find the code in the StackQueue class in the tutorial's GitHub repository.

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```public class StackQueue<E> implements Queue<E> {

private final Stack<E> stack = new ArrayStack<>();

@Override
public void enqueue(E element) {
// 1. Move elements from main stack to a temporary stack
Stack<E> temporaryStack = new ArrayStack<>();
while (!stack.isEmpty()) {
temporaryStack.push(stack.pop());
}

// 2. Push new element on the main stack
stack.push(element);

// 3. Move elements back from temporary stack to main stack
while (!temporaryStack.isEmpty()) {
stack.push(temporaryStack.pop());
}
}

@Override
public E dequeue() {
return stack.pop();
}

@Override
public E peek() {
return stack.peek();
}

@Override
public boolean isEmpty() {
return stack.isEmpty();
}
}```Code language: Java (java)```

Note that we do not implement the `java.util.Queue` interface here. That interface inherits from `java.util.Collection`, so we would have to implement many more methods.

Instead, I wrote a custom Queue interface for this tutorial that defines only the `enqueue()`, `dequeue()`, `peek()`, and `isEmpty()` methods:

``````public interface Queue<E> {
void enqueue(E element);
E dequeue();
E peek();
boolean isEmpty();
}```Code language: Java (java)```

## Outlook

In the next part of the tutorial, you will learn how to implement a queue with a linked list.