Home / Development / Java / Implement Queue Using 2 Stacks in Java
Implement Queue Using 2 Stacks in Java

Implement Queue Using 2 Stacks in Java

Today, we will look at how we can implement a Queue by using 2 Stacks in Java. Note that a Queue is an interface in Java and to correctly implement it fully according to the documentation, all of its method signatures must be overridden. In this case however, we are implementing a Queue using our own custom methods and as such, we have omitted the “implements Queue” keyword from the class name. Feel free to add on your own methods as well if you require!

To begin, we will initialise 2 Stacks and name them “s1” and “s2”.

Add
Adds an element to the front of the queue. This is done simply by pushing the element onto “s1”.

Size
Returns the number of elements currently in the queue. Adding the number of elements in “s1” and “s2” will give the total number of elements in the queue.

Empty
Returns true if the queue is empty and false if it is not. We know the queue is empty if both “s1” and “s2” are empty as well.

Peek
Returns element at the front of the queue without removing it from the queue. This can be achieved by first checking if the queue is empty and returning a null if it is. Otherwise, we will then proceed to check if there are any elements in “s2”. If there is an element in “s2”, we will simply return that element from the top of “s2” without removing it. If there aren’t any elements in “s2”, we will move all elements from “s1” to “s2” afterwhich we will return that element from the top of “s2” without removing it.

Remove
Removes and returns element at the front of the queue. This can be achieved by first checking if the queue is empty and returning a null if it is. Otherwise, we will then proceed to check if there are any elements in “s2”.If there is an element in “s2”, we will simply remove and return that element from the top of “s2”. If there aren’t any elements in “s2”, we will move all elements from “s1” to “s2” afterwhich we will remove and return that element from the top of “s2”.

How It Works

We can see how it works by looking at the following diagram. If we add 3 elements to the queue, they will be pushed onto “s1” as such:

stack1

Now, if we wanted to remove elements from the queue, we would first move them over to “s2” since “s2” is empty and then we would pop them out. Notice that the order of the elements has been reversed thus conforming to the First-In-First-Out (FIFO) requirements of a Queue structure.

stack2

Try out the code for yourself and see how it goes!

About Clinton De Silva

Clinton De Silva

One comment

  1. Hey There.. I looked at your code and how I am working something related to that. I need help creating a java program that Reverse’s the Sentence. For Example “My Name is Jainam Patel”.. it should Print ” Patel Jainam is Name My”. I Have to Use all the Methods that U Have used in ur code but in two different Classes. One Class is where I ask the user for the Sentence and then use the other methods from other classes to reverse the order. Please Help me Make It.
    Thank You.

Leave a Reply

Your email address will not be published. Required fields are marked *