Basic Interview Data Structures in JavaScript: Stacks and Queues

Johannes Baum

Welcome to my follow up article to Basic Interview Data Structures in JavaScript, where I describe the JavaScript implementations of arrays, array lists / vectors, hash maps and hash sets for the use in coding interviews. This article focuses on stacks and queues.

Stacks and queues are commonly used in interview questions and certain problems can be solved very efficiently by using them. Two very famous algorithms that rely on stacks and queues are depth-first search and breadth-first search, both used to traverse a graph.

Stacks

A stack is a so called last in first out (lifo) data structure that works like a pile of plates. You can easily take the plate on top of the pile but if you want to take a plate from the bottom you first have to remove all plates on top of it.

As in my previous article, I will give you the runtime complexity for the following operations:

  • Insertion (push): O(1)
  • Random access (access any element): O(n)*
  • Access first (peek — access most recently added element): O(1)
  • Find (find a specific element): O(n)
  • Random removal (remove any element): O(n)
  • Remove first (pop — remove most recently added element): O(1)

*If you use JavaScript arrays as a stack, random access can be done in O(1).

The important operations for a stack are insert (push), remove first (pop) and access first (peek). These are the efficient operations of a stack. If you find yourself using different operations a lot, a stack is probably the wrong data structure for your purpose.

Stacks in JavaScript

JavaScript comes with dynamic arrays out of the box. These can be used as a stack very easily:

const stack = [];// insert elements (push)
stack.push('one');
stack.push('two');
console.log(stack); // ['one', 'two']// access first (peek)
console.log(stack[stack.length-1]); // "two"
// remove first (pop)
stack.pop();
console.log(stack); // ['one']

Note that since we are using a JS array, we can access any element within O(1) and not only the last one.

Queues

A queue is a so called first in first out (fifo) data structure that works like a queue in front of a cinema. The person that arrives at the cinema first will be the first one to get a ticket. On the other hand the person last arriving will also be the last person to receive a ticket.

As in my previous article, I will give you the runtime complexity for the following operations:

  • Insertion (enqueue): O(1)
  • Random access (access any element): O(n)
  • Access last (access least recently added element): O(1)
  • Find (find a specific element): O(n)
  • Random removal (remove any element): O(n)
  • Remove last (dequeue — remove least recently added element): O(1)

The essential and efficient operations for a queue are insert (enqueue), remove last (dequeue) and access last (peek). Similar to stacks you should not use this data structure if you don’t need the mentioned operations.

Queues in JavaScript

You could implement a queue with a JavaScript array as follows:

const queue = [];// insert elements (enqueue)
queue.push('one');
queue.push('two');
console.log(queue); // ['one', 'two']// access last
console.log(queue[0]); // "one"
// remove last (dequeue)
queue.shift();
console.log(queue); // ['two']

However, there is one downside to this solution: shift takes O(n) in the worst case, because all array elements have to be copied over by one position.

There are several third-party solutions implementing a queue in an efficient way. However, you can’t use them during an interview. You should tell your interviewer that you know about this limitation in JavaScript and clarify if you can simply use arrays as a queue, pretending that shift takes only O(1). If that is not an option you can implement a queue (and also a stack) efficiently using a linked list.

However, you can also implement a queue right from scratch. You need the following data structure for this:

const Node = data => ({ data, next: null, prev: null });

As you see this looks similar to a doubly linked list (see my previous article about linked lists).

We embed this in a queue factory function:

const Queue = () => {
const Node = data => ({ data, next: null, prev: null });
let head = null;
let tail = null;
... return {
enqueue,
dequeue,
peek,
};
};

We need this factory function in order to have a closure that holds head and tail of the queue.

Insertion (enqueue)

To insert a new element to the queue you simply need to attach it as the new head of our list-like data structure:

const enqueue = data => {
if (head == null) {
head = Node(data);
tail = head;
return head;
}
const newNode = Node(data);
newNode.next = head;
head.prev = newNode;
head = newNode;
return head;
};

Remove last (dequeue)

Removing the least recently added element from a queue can be done by returning and removing the tail of the list:

const dequeue = () => {
if (tail === null) return null;
const tailData = tail.data;
if (tail.prev === null) {
tail = null;
head = null;
return tailData;
}
tail.prev.next = null;
tail = tail.prev;
return tailData;
};

It is fairly straight forward but we have to be careful with null-pointers.

Access last (peek)

To access the least recently used element of the queue we need to simply return the tail of our list. We only need to account for tail being null:

const peek = () => tail ? tail.data : null;

Conclusion

Stacks and queues are very common and useful data structures in coding interviews. Whenever you need to heavily access and drop the most / least recently added elements you should consider using a stack / queue.

Many languages like Java contain linked list implementations in their standard libraries. Therefore you can use a LinkedList in Java as a stack and a queue. For this reason you should ask your interviewer if you can just use JavaScript arrays as a queue and ignore the runtime of the shift operation for the sake of simplicity. In most cases your interviewer will allow this as long as the interview is language agnostic.

I hope this helps you to land your next job. Good luck with your interviews!

References

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade