Creating a Queue with Limited Data Structures

Learn how to create a queue when the only data structure you have access to is a stack.

Create a Queue Using Two Stacks

This is a fairly common interview question.

Instructions

Write a function that creates a queue using two stacks. Besides these two stacks, you may not use any additional data structures in your implementation. It should have the methods enqueue, dequeue, and size.

Feel free to change the code provided below when you start. It’s meant to be a guide.

class Queue {
    constructor() {
        this._stack1 = [];
        this._stack2 = [];
      
        // Your code here
    }
    
    enqueue(item) {
        // Your code here
    }
    
    dequeue() {
        // Your code here
    }
    
    get size() {
        // Your code here
    }
}

Solution

class Queue {
    constructor() {
        this._enqueueStorage = [];
        this._dequeueStorage = [];
    }
    
    enqueue(item) {
        this._enqueueStorage.push(item);
    }
    
    dequeue() {
        if(this._dequeueStorage.length) {
            return this._dequeueStorage.pop();
        }
        
        if(this._enqueueStorage.length) {
            while(this._enqueueStorage.length) {
                this._dequeueStorage.push(this._enqueueStorage.pop());
            }
            
            return this._dequeueStorage.pop();
        }
        
        console.warn('Attempting to dequeue from an empty queue');
        return undefined;
    }
    
    get size() {
        return this._enqueueStorage.length + this._dequeueStorage.length;
    }
}

How it Works

We have two storage stacks, this._enqueueStorage and this._dequeueStorage. To see how they interact, let’s go through an example.

Enqueuing

We want to put 5 elements onto the queue: 1, 2, 3, 4, and 5. We enqueue all of these, and they all go into enqueueStorage.

enqueueStorage: [1, 2, 3, 4, 5]
dequeueStorage: []

We now want to dequeue an item. Let’s dive into our dequeue function.

Dequeuing

We skip the if-statement on line 12 since dequeueStorage is empty. We move on to line 16.

Inside that if-statement (line 16), we pop every item off of enqueueStorage and put them into dequeueStorage. When the while-loop (lines 17 - 19) is finished, enqueueStorage is empty and dequeueStorage has the five items, but in reverse.

enqueueStorage: []
dequeueStorage: [5, 4, 3, 2, 1]

On line 21, we pop dequeueStorage and return the item, 1.

enqueueStorage: []
dequeueStorage: [5, 4, 3, 2]

If we want to dequeue again, we can enter the dequeue method once more. This time we go into the first if-statement and pop an item off of dequeueStorage and return it.

enqueueStorage: []
dequeueStorage: [5, 4, 3]

We can keep dequeuing if we like. As long as dequeueStorage has items in it, the last item will be popped off and returned to us.

Summary

These steps together make it so our queue functions properly. Enqueuing pushes items onto one stack. Dequeuing pops them from the second stack. When the second stack is empty and we want to dequeue, we empty the first stack onto the second, reversing the order of items.

Enqueue Time

Every enqueue event is a simple push onto a stack. This means that each enqueue has a time complexity of:

O(1).

Dequeue Time

This gets a little more complicated. If we have items in our dequeueStorage stack, we simply pop one off and return it, so we have O(1) complexity. However, if that stack is empty, we have to transfer every item from enqueueStorage to dequeueStorage - an O(n) operation - and then return an item.

So, for most cases, we have O(1), and for a few rare cases, we have O(n). We can merge these into a single time complexity.

Queue Lifecycle

Let’s track the life of three items in our queue. Starting with an empty queue, let’s enqueue 1, 2, and 3. This puts them on our first stack.

enqueueStorage: [1, 2, 3]
dequeueStorage: []

So far, we’ve performed 3 operations: inserting each of those items onto the stack.

Let’s dequeue all three items. First, all items from enqueueStorage get transferred to dequeueStorage.

enqueueStorage: []
dequeueStorage: [1, 2, 3]

We’ll say that a transference is 1 operation. This is another 3 operations total, bringing us up to 6.

After this, all 3 items are popped off and returned to us. This is another 3 operations, bringing us up to 9.

So, for the insertion and removal of 3 items, we perform 9 operations. Repeating this exercise, we can see that for 4 items, we would perform 12 operations. For 5, we would perform 15. See the pattern?

The entire lifecycle of a single item in a queue always requires the same 3 operations: a push onto a stack, transference to another stack, and then a pop from that stack.

Amortized Time

Using this logic, the average time complexity of a dequeue operation must be O(1). It’s entirely possible that a single dequeue operation can require 100 operations, or even over 1000, depending on the length of the queue.

Averaged over every item, we can still say that the average dequeue is an O(1) operation. This is known as an amortized constant time complexity.

Amortized time refers to the average time taken per operation. So, our dequeue function has an amortized time complexity of

O(1).

Creating a Queue Using One Stack

We’re going to go even further and restrict ourselves even more. Recently, Google revealed that they have asked applicants to construct a queue using only a single stack.

This might seem impossible, but it’s doable, using some trickery.

Feel free to try it yourself.

Hints

  • This won’t have nice time complexities.
  • Think about how you might be able to store information without using an array or an object.
class Queue {
    constructor() {
        this._storage = [];
      
        // Your code here
    }
    
    enqueue(item) {
        // Your code here
    }
    
    dequeue() {
        // Your code here
    }
    
    get size() {
        // Your code here
    }
}

Solution

class Queue { 
    constructor() {
        this._storage = [];
    }
    
    enqueue(...items) {
        this._storage.push(...items);
    }
    
    dequeue() {
        if(this._storage.length > 1) {
            const lastItem = this._storage.pop();
            const firstItem = this.dequeue();
            this.enqueue(lastItem);
            return firstItem;
        } else if (this._storage.length === 1) {
            return this._storage.pop();
        } else {
            console.warn('Attempting to dequeue from an empty queue');
        }
    }
}

Note that in the constructor, we create only a single array. This will be our stack.

The enqueue() function passes the items it receives into storage.

How dequeue() Works

This recursive method is the fun part. We’ll start by discussing the base cases. Lines 16 onward state that if the queue is empty, print a warning and do nothing. If there’s a single item, pop it off and return it.

For the cases where there is more than one item present in storage, we can look at lines 11 - 15.

Assume that our storage stack has values 1, 2, 3, in that order, present inside.

[1, 2, 3]

Since 1 was entered first, when we dequeue, we need to return 1. We also need to preserve the order of 2 and 3.

Currently, we’re on the first call of this recursive function.

In the First Call

Once we hit line 12, lastItem is equal to 3 and our queue has had 3 removed:

[1, 2]

Since we know more items are present (since this is the case in which there were multiple items in storage), we recursively call the dequeue() method.

Entering the Second Call

We enter the function again. Length is now 2, so we enter the same case, lines 11 - 15. Again, we dequeue. In this call, lastItem is equal to 2. Our queue loses another value:

[1]

We again call the function.

Entering the Third Call

This time, there is only one item, 1. We pop it off and return it, ending up back in the second call. Our queue is empty.

[]

Back to the Second Call

We go back to the 2nd call, now on line 14. lastItem is 2 and firstItem is 1.

On line 14, we enqueue lastItem, or 2.

[2]

We return 1 and go back to the first call.

Back to the First Call

We’re back at the beginning. lastItem is 3 and firstItem is 1. We enqueue 3:

[2, 3]

and return 1.

Dequeue Time

The time complexity of dequeue() is:

O(n)

because we need to pop and re-insert every item except one.

Dequeue Space

The space complexity of dequeue() is:

O(n)

because we need to call the function one more time for every item.

Conclusion

Think about how challenging this problem is. On the surface, it truly seems impossible. How are we supposed to return the first item in a stack, but also preserve the remaining items, without any additional data structures? Don’t we at least need a second stack?

The Second Stack

A recursive function gives us access to that second stack. Rather than creating it ourselves in our function, we’re using the JavaScript engine’s call stack.

The Algorithm

Each recursive function call independently maintains its own piece of data in one single variable. We simply call the function over and over, each time giving it an item off of the stack.

Once we get to the end of the stack we’re at the very last function call. This one takes the last item out of the stack and returns it to the 2nd-to-last function call.

The 2nd to last call puts the value it popped back onto the stack. It passes the value it received upwards.

All previous function calls put back the value they popped off. Afterwards, they all return the same value up the chain, the one they received from the previous call.

The Call Stack

The call stack’s normal purpose is to maintain a record of the order in which functions are called. It also maintains function state, including all variables, until the functions finish their work.

We’re highjacking the call stack to store values we want, and then getting them back out when we need them. It’s essentially an abuse of the call stack, but it’s a beautiful hack that works.