DS with JS — Stacks & Queues

Stacks and Queues — DS with JS (Made with draw.io)

Imagine you are at a party and in the queue for getting the food. The person ahead of you is about to take a plate from the very bottom of the stack. Seeing this you try to stop him because he is going to topple all the plates! But you are late, the plates have scattered on the floor. You wait patiently while the new plates are stacked back. Once the plates are back and as you are about to reach for the plate a guy from the end of the queue pops up, in front of you and takes the plate and moves on! We can be sure of one thing — you are having a bit of a rough time.

Stacks and queues are the most simple data structures. They have a few operations but their usage is ubiquitous — both in programming and real life. We will be implementing these data structures in JavaScript after we know what they are made for. We will look at their implementation with JavaScript using other data structures.

Stacks

Consider the stack as the plates stacked on top of each other vertically and we can only access the top plate. We cannot access anything from the bottom. To access data from a stack is to grab the first plate, then the second plate, then the third, and we keep going until we have gone through all the plates.

This is called LIFO — Last in, first out. We can also describe it as FILO — First in, last out.

Use Cases for Stacks

Stacks are very important in language-specific engines. You might have heard of stack overflow when you write bad code.

Fibonacci Series with Recursion — Stack Overflow in JavaScript

Most programming languages are modelled with the stack architecture in mind and when functions get called in a programming language usually they follow this model of last in first out. A function within a function within a function gets called and then we start popping those functions until we get to the very beginning.

Another useful way that we might use stacks is as browser history.

Browser History | Stack of visited pages

We go back and forth from one website to another by keeping a stack of web pages visited. The last visited web page will be at the top of the stack. When we hit the back button or the forward button we can leverage the top of the stack.

Or maybe you’re writing a piece of text and you want to undo something so you can click the undo option to go back or forward to redo. The idea comes from stacks. We store the previous state of the work in the memory in such an order that the last one appears first.

Operations in Stack

When we talked about the use cases for stacks, we focused on the top of the stack. The operations are limited to the top of the stack as well. We can look, push and pop an item on top of the stack. Each of these operations will have constant time complexity.

Operations in Stack — Peek, Push, and Pop

1. Pop (item at the top of the stack)— O(1)
2. Push (item at the top of the stack)— O(1)
3. Peek (view the top) — O(1)

We usually don’t want to use the stack for lookup still, the Big-O for lookup in the stack would be O(N), where N is the length of the stack.

Implement Stack in JavaScript

Stacks are not there in JavaScript. Since we know the operations performed on them, we can implement them using other data structures.

But what data structure do we use? Considering we have arrays and linked lists which one will you choose for implementing stacks?

Which data structure do you think is a better choice here for the stack?

In the case of stacks, both arrays and linked lists are going to work well.

One major thing is that arrays allow cache locality, making them technically faster when accessing its items in memory because they’re right next to each other versus linked lists that are scattered all over memory. Also, linked lists have extra memory associated with them because we have to hold on to those pointers.

But on the other hand, linked lists have more dynamic memory. We can keep adding things to the list versus an array where you have either a static array or a dynamic array that has a certain amount of memory. And as soon as it’s about to reach its limit it’s going to have to double up its memory and create new space for it somewhere in memory.

These are tradeoffs while choosing between arrays and linked lists. But both of them will provide a constant time complexity for operations on stacks and queues. Let us see that in action.

Implementing a Stack using Linked List in JavaScript

We know that for the linked list contain nodes — each node has a value this.value and a reference to the next node this.next. We have a reference to the start of the linked list this.top and to the end of the list this.bottom.

For each operation, we will leverage the linked lists operations — prepend for push and remove at index 0 for pop.

1. Peek: Return the value of the node pointed by this.top.
2. Push: Create the new node and add it at the top of the linked list.
3. Pop: Remove the first element in the linked list.

Implementing Stack using Linked List In JavaScript — Try it!

Implementing a Stack using Array in JavaScript

For implementing a stack using an array we can leverage the push and pop operations of the array. We will push at the end of the array and pop the last item to use the array as a stack.

Implementing a Stack using Array in JavaScript — Try it!

Queues

Think of a queue in a cafeteria or at a bus stand. The first person in the queue goes first, then second, and so on. The last person goes last.

This is called FIFO — First in, first out. We can also say it as LILO — Last in, last out.

Use Cases for Queues

First Come First Service | Form a Line!

We can use the queue in

• waitlist application to buy tickets
• booking seats for a restaurant application
• something like Uber, where we book rides
• printer — the first request will get printed first

In all these use cases the first request will be addressed first. All new requests will come and sit at the end of the queue.

Operations in Queue

We can see that with the queue we want to peek and pop the first item. But we want to push the item to the end of the queue. These operations will have constant time complexity.

Operations in Queue — Peek, Enqueue, and Dequeue

1. Enqueue (push item at the end of the queue) — O(1)
2. Dequeue (pop the first item in the queue) — O(1)
3. Peek (first item) — O(1)

We usually don’t do the lookup in the queue still, the Big-O for lookup in the queue would be O(N), where N is the length of the queue.

Implement Queue in JavaScript

Again let us consider we have arrays and linked lists and since we do not have queues implemented directly in JavaScript which data structure do you think is a better choice here for the queue?

For queues, we need the first item for both enqueue and dequeue. If we use linked lists then the time complexity for adding and deleting the first item will be O(1). Let us consider the following linked list A --> B --> C.

Head                    Tail
 A    ----   B    ----   C

If we want to remove A or add at the start we change the pointer for the head and next node.

While in arrays we will have to shift the remaining items in the array which is O(N) operation.

0  1  2       Remove A       0  1 
A  B  C   -----------------  B  C

Hence, in the case of queues, a linked list seems to be the preferred choice. Let us implement it.

Implementing a Queue using Linked List in JavaScript

For each element, we create a new node and have two references this.first and this.last as a reference to the start and end of the linked list.

1. Peek: Return the value of the node pointed by this.first.
2. Enqueue: Create the new node and add it at the end of the linked list.
3. Dequeue: Remove the first element in the linked list.

Why & When — Stacks or Queues

Unlike an array in stacks in queues, there’s no random access operation. All operations deal exclusively with the element at the top/first item of the data structure. We built stacks and queues using arrays or linked lists though unlike arrays and linked lists we have few methods or fewer actions that we can perform on them.

Sometimes it is good to have high-level data structures that are built on top of low-level ones like linked lists and arrays to limit the operations we can do on them. That’s actually a benefit of computer science, having this limited ability in a data structure is an advantage because we can control the users to perform only efficient operations. If we give somebody all the tools in the world it’s a lot harder for them to operate than if we just give them two or three so that they know exactly what they need to do.

Hence next time looking for stacks or queues do look for the following checklist.

✅ Fast Access (Top of the stack or first in the queue)

✅ Fast Peek (Top of the stack or first in the queue)

✅ Ordered (Top of the stack or end of the queue)

❌ Slow Lookup

References and Further Reading

1. Data Structure with JavaScript
2. DS With JS — Arrays
3. DS with JS — Linked Lists