Javascript Data Structures: Stack and Queue
Stacks
Stacks are an elementary data structure, they are the last item in, the first item out (LIFO). The last item added into the stack will be the first one taken out of the stack.
Stacks are basically arrays where the only thing you can do, more or less, is to push and pop.
Let’s go through the interface needed to build a stack. We need a storage variable that holds whatever it is that we are trying to put into our stack. It’s basically a reference to our stack. Regarding the methods, as we mentioned before, we need a method that allows us to add an element into the stack (push), one that allows as to remove and return the last element from the stack (pop), and it would also be nice to have a method that returns the actual size of the stack. In addition to this, we are going to add the last method called peek, that returns the last element from the stack.
For the following implementation, we are going to store the elements in an object, therefore our storage variable will hold a reference to an object of key-value pairs. As keys, we are using integers from 0 to the maximum capacity of the stack.
Here is how it looks like:
Queues
Queues are, the first item added to the queue will be the first one taken out of the queue (FIFO). When adding an item into the queue that operation is called enqueuing and when we take out an item from the queue the operation is called dequeuing.
Let’s go through the interface of building a Queue.
Here is how the implementation looks like:
Exercise 1
Problem: Implement a MinStack. A stack with a min() method that returns the minimum value of the stack in O(1);
Exercise 2
Problem: Implement a Queue with two stacks.
The solution to this common problem relies on having one stack to enqueue elements and the other stack to only dequeue elements.
We know for the definition of the stack, that the last item in has to be the first out, so our dequeue stack has to have the elements in reverse order so that when we want to dequeue one, we are actually pulling out the first element in, therefore following the queue specification.
Let’s see how the implementation of this looks like:
