# Basic Interview Data Structures in JavaScript: Stacks and Queues

## LIFO versus FIFO

Welcome to my follow-up article to “Basic Interview Data Structures in JavaScript”, where I described 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 of the plates on top of it.

As in my previous article, I will give you the run-time 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)

**Note:** 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 run-time 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 shouldn’t 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 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’s 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 last 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 straightforward, but we have to be careful with null pointers.

**Access last (peek)**

To access the last recently used element of the queue, we need to simply return the tail of our list. We only need to account for the 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 linked list 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 run time 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!