Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Implement Queue Using Two Stacks

DZone's Guide to

Implement Queue Using Two Stacks

Learn how to use two stacks to implement a queue

· Java Zone
Free Resource

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

In code corner, we take a real interview programming challenge and solve it in code. Whilst these questions may be likely be asked as a whiteboarding exercise, as a developer you will learn much more by actually coding the solution and getting your hands on the APIs, collections and algorithms in discussion

You can download this exercise from the CJIQ Github athttps://github.com/corejavainterviewquestions/queuefromtwostacks. Each stage is a commit; rollback to the initial check out and code along on a branch. You can then compare your answer to mine. Results are developed using TDD.

Creating a queue from two stacks is one of those questions that seems to have lingered around for years and still gets asked. It’s a good one to know just in case it gets asked, but more importantly it’s a nice opportunity to look more into stacks, queues and calculating Big O.

The task is simple. Replicate the functionality of a queue using two stacks.

A Queue is a First-in-first-out (FIFO) data structure. If you push item A, B and C in that order, then pop three times, you will get A, B and C. Conversely, a stack is a Last-in-first-out (LIFO) structure; In the same example you would get C, B then A.

You can read more about these data structures in this previous post on interviews and data structures.

Queue has 2 methods we’re interested in: add and remove. Stack has push and pop.
Let’s start with our first failing test.

 @Test
 public void addingOneItemAndRemovingFromQueueWillReturnThatItem() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
 
     assertThat(queue.remove(), is(“Item 1”));
 }

To write this test, I’ve created an add method- I’ve chosen to use Strings. We could generecise it very easily but let’s keep it simple. We add a remove method, which we expect to return the object we’ve added.
To implement is very simple; the functionality would be identical for a Stack, so we’re effectively just delegating.

 Stack stackOne = new Stack();
 public void add(String item) {
     stackOne.push(item);
 }
 public String remove() {
     return stackOne.pop();
 }

First test pass! Feel the serotonin.

commit

Ok, time for a more realistic test, adding multiple items.

 @Test
 public void
 addingMultipleItemsThenRemovingOneWillReturnFirstItem() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 1”));
 }

This gives a nice test fail; We’re getting item 3 back incorrectly. Now we need to actually think of an implementation.
Imagine our stack like a bucket.

stacks
We need to get to the bottom of the bucket to remove the item that was first in. The only way to do this is to pop all of the items in the way.
This test is really simple, so we don’t actually care about the other items. Let’s just pop everything out the way. It’s crude, but in TDD we aim to do the minimum work to make the test pass.

 public String remove() {
     String result = null;
     while(!stackOne.isEmpty())
         result = stackOne.pop();
     return result;
 }

Pretty basic. Let’s write a harder test.

commit

I’ve renamed the last test and expanded it to include an extra pop.

@Test
 public void
 addingThreeItemsThenRemovingTwoWillReturnItemOneThenTwo() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 1”));
     assertThat(queue.remove(), is(“Item 2”));
 }

Now we need to handle the storage when popping items from stack one. The obvious location is to put onto the second stack we’re allowed. By putting each popped item on the stack we reverse the collection so it’s in the right order for a queue. The top item can then be returned.

stacks (1)

We must then return all items back to the first stack so that we can add more items to the stack.

public String remove() {
     while(!stackOne.isEmpty()) {
         stackTwo.push(stackOne.pop());
     }
     String result = stackTwo.pop();
     while(!stackTwo.isEmpty()) {
         stackOne.push(stackTwo.pop());
     }
     return result;
 }

This makes the test pass, and is a an accurate albeit crude solution to the problem.

commit

There is some duplication in the code above. The TDD Mantra is Red, Green, Refactor. So let’s clean the code up a little.

 public String remove() {
     swapStacks(stackOne, stackTwo);
     String result = stackTwo.pop();
     swapStacks(stackTwo, stackOne);
     return result;
 }
 private void swapStacks(Stack stackOne, Stack stackTwo) {
     while(!stackOne.isEmpty())
         stackTwo.push(stackOne.pop());
 }

Not only is this cleaner code, but it’s much easier to understand what’s going on.

commit

What about missing tests? It’s important to think of edge cases in these scenarios. What about the empty case? Particularly in an interview it’s important you decide what is the correct behaviour. Should the queue return null or throw an Exception? Either could be argued quite reasonably. I have chosen to throw an exception, as passing null around can result in fragile and error prone code.

@Test(expected = NoSuchElementException.class)
 public void throwsErrorIfRemoveCalledOnEmptyQueue(){
     Queue queue = new Queue();
     queue.remove();
 }

This test fails; we get an EmptyStackException. This should be an easy fix.

public String remove() {
     if(stackOne.isEmpty())
         throw new NoSuchElementException(“The Queue Is Empty”);
     swapStacks(stackOne, stackTwo);
     String result = stackTwo.pop();
     swapStacks(stackTwo, stackOne);
     return result;
 }

Easy!

commit

Just for safety, lets throw in a more complex test, of multiple adds and removes.

 @Test
 public void multipleAddsAndRemovesInCorrectOrder() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     assertThat(queue.remove(), is(“Item 1”));
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 2”));
     queue.add(“Item 4”);
     queue.add(“Item 5”);
     queue.add(“Item 6”);
     assertThat(queue.remove(), is(“Item 3”));
     assertThat(queue.remove(), is(“Item 4”));
 }

As expected, this test passes. We now have a complete Queue solution.
However, this is a very slow solution. Let’s analyse the Big O. First, we have to go through every item on the stack and pop it; that’s n. Then we have to push every
item, which is n again. We then pop all the items, another full iteration of n. We then add all bar one item back, n–1. That’s O(4n). Pretty poor! Can we come up with a better solution?
Let’s consider the first time we perform a remove operation. We push every item and pop it onto the secondary stack. At this point the secondary stack is in correct queue order. If we do not move back to first stack then we can just pop from the secondary queue until it is empty. If a remove request happens and stack 2 is empty, we simply swap the stacks then.

public String remove() {
     if(stackOne.isEmpty() && stackTwo.isEmpty())
         throw new NoSuchElementException(“The Queue Is Empty”);
     if(stackTwo.isEmpty())
     while(!stackOne.isEmpty())
         stackTwo.push(stackOne.pop());
     return stackTwo.pop();
 }

Every pop is from stack two. We check if there are elements (we now must check both stacks). If there are, we check whether we need to do a stack swap (i.e. stack two is empty). We can then pop from the top of stack 2.
As we now have a test suite we can run to check the solution, we know we haven’t broken anything.
But what is the complexity of this algorithm? When stack two becomes empty we have to do a full pop from stack one and push onto stack two; which is O(2n), simplified to O(n). However, this should not happen often (dependent on the usage of the stack). Most calls to remove will just execute stackTwo.pop(), which is a constant time operation.
We can therefore say that, whilst the worst case is O(n) it will give constant amortised time, e.g., if you run a million operations through the queue most of them will be constant time.

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:
java ,java stacks ,queue

Published at DZone with permission of Sam Atkinson, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}