Implementing a Queue using Stacks in JavaScript
Continuing my series of writing blogs about things in JavaScript that are tricky to me initially, this is a blog explaining a simple way of building a stack using queues in JavaScript. Full disclosure: I was asked to do this in an interview, and am clearing some things up for myself and hopefully you as well.
We should start with the difference between a stack and a queue. They really aren’t all that different, both are data structures in which we only append elements, which is to say, we add them to the end. With stacks, we add items to the end and remove them from the end, but with queues we add to the end but remove from the beginning. This is often described by using the acronyms FIFO (First In, First Out) and LIFO (Last In, Last Out). This is why when implementing a stack in JavaScript, we can simply use an array. The pop and push methods are built in and have a time complexity of O(1). Queues are better suited for linked lists, but it’s a fairly common interview question to implement a queue using a stack.
This isn’t that hard if we remember that stacks in JavaScript are basically just arrays, and that the only big difference between a stack and a queue is the order in which we remove elements. How we get started is with two stacks:
We are going to use these to shuffle around the elements so that we’re only using the push and pop methods to approximate the functionality of a queue. Our “enqueue” method, which just an even fancier way of saying append, which if you recall, is a fancy way of saying “add to the end” will just look like this at the start:
Like a stack, or an array, we’re just adding elements to the end. However, when we want to “dequeue”, or remove elements from the beginning, we need to do the following:
We need to loop through all the elements of our first stack, pop them from the first array, then push them into the second array. Because we’re taking from the end of the first array and adding to the end of the second, when we pop from the second array, it will be like removing the first element of the first array. And like any good pop method it will have a return value of the element that’s being removed. If we want to dequeue sequentially this will also work because we’ll keep popping elements from the second array. However, if we want to enqueue again, our method right now is insufficient. We need to check if our elements are in the second array and if so, put them back in the first:
This for loop will run only if stack2 is populated with our elements (because otherwise its length will be 0) and put them back in stack1 in the same way that we shuffled them around before.
Our final method, called “peek”, is used to check the first element in the queue. This is pretty simple:
We just check if our elements are in stack1 or stack2, and return the first or the last element in the array, respectively.
And that’s all folks!
