An optimal approach to stacks and queues in JavaScript

An optimal approach to stacks and queues in JavaScript

Thu, Feb 6th, 2020

• Stacks(LIFO) and queues(FIFO) are essential data structures for software engineering.
• JavaScript arrays are not guaranteed to be efficient for emulating stacks or queues because ECMAScript specification does not set restrictions on amortized time complexities.
• Linked lists are very efficient for implementing stacks or queues.
• Using linked lists will guarantee O(1) time complexity for 'add', 'remove', 'peek', 'pop' and 'push' methods in stacks and queues.

Motivation

Stack and queue data structures are an essential part of a software engineers toolbox. The stack is a LIFO data structure i.e., the items that are last to be added are the first ones to be removed. Queue, on the other hand, is a FIFO data structure i.e., the items that are added earliest are the first ones to be removed. Programming languages like Java, C#, and Python have a native stack and queue implementation that can guarantee O(1) time complexity for 'add', 'remove', 'push', 'pop' and 'peek' methods. In JavaScript, there are no native stack or queue data structures. So arrays can be misused to emulate stacks and queues using the 'shift ', 'push' and 'pop' methods. An array is not the ideal data structure to emulate stack or queue at least in JavaScript because it entirely depends on the JavaScript engine(list of js engines). For an array, the 'push', 'pop' and 'shift' methods could take O(n) amortized time, where 'n' is the array length. Consequently, we need an implementation of stack and queue which will guarantee O(1) time complexity for 'add', 'remove', 'push', 'pop' and 'peek' methods.

Approach

Stacks and queues can be modeled using the linked list data structure. A linked list is simply a chain of object nodes where each node holds a value and reference to the next node. It turns out that using a linked list to build stacks and queues guarantees O(1) time complexity for 'add', 'remove', 'push', 'pop' and 'peek' methods. Additionally, the stack or queue implemented using a linked list can be dynamically resized. A list of numbers 7, 3, 4 and 5 added sequentially to a linked list can be visualized as following:

The last node in a linked list always points to null.

Stack Implementation

The stack is a LIFO data structure, this means that the last item added to the stack is the first one to be removed. A good analogy for the stack would be a burger🍔 that has layers of edible items assembled from the bottommost item to the topmost item. The stack can use 'push' and 'pop' methods to add and remove items respectively. This is a sample sequence of 'push' and 'pop' operations:

1. push(7)
2. push(3)
3. push(4)
4. push(1)
5. pop()
6. push(5)

This sequence of operations can be visualized as follows:

A linked list can emulate the stack very efficiently. The 'head' pointer in the linked list represents the top of the stack. So each time a new element is pushed onto the stack the linked list adds a new node and points the 'head' to the new node. The newly created node will point to the node which previously the 'head'. For the case of popping an item from the stack, the linked list will point the 'head' to the next node, this way the stack will follow the LIFO scheme.

The sample push and pop operations which were visualized earlier can be further rendered by comparing to it the linked list:

In this visualization, one can observe that each time when an item is pushed onto the stack the linked list points the 'Head' to the newly created node. The newly added item in the stack has a green background for better clarity. Finally, the newly created linked list node points to the previous 'Head' pointer. This mechanism encapsulates the 'push' method in the stack. Similarly, the item having a red background in the stack represents it being popped. When an item is popped the 'Head' pointer in the linked list points to the next node.

The stack can be implemented using ES6 classes. In this implementation there is a class called 'LinkedListNode', this represents a single node in the linked list. In the 'LinkedListNode' class, the 'val' property represents the node value and 'next' property points to the next node in the linked list. The last node will always have 'next' as null.

class LinkedListNode { constructor(val) { this.val = val; this.next = null; } } 

The 'Stack' class uses the 'LinkedListNode' class to implement the different methods of the stack. The 'Stack' class has two class-level variables 'head' and 'stackSize' which are used to track the head node and the current stack size respectively.

class Stack { constructor() { this.head = null; this.stackSize = 0; } push(val) { if (this.head === null) { this.head = new LinkedListNode(val); } else { const newNode = new LinkedListNode(val); newNode.next = this.head; this.head = newNode; } this.stackSize++; } peek() { if (this.head !== null) return this.head.val; return null; } pop() { if (this.head !== null) { const result = this.head; this.head = this.head.next; this.stackSize--; return result.val; } } empty() { return this.stackSize === 0; } } 

When adding an item to the stack the 'push' method is invoked with an argument, this argument will be pushed onto the stack. Then it checks if the 'head' pointer is null, if it is null then this must be the first item of the stack. So it sets the 'head' pointer to a new 'LinkedListNode' object. Where the value of the 'LinkedListNode' is the argument passed to 'push' method. If the 'head' pointer is not null then it creates a new node from the 'push' method argument and then it points 'next' to the previous 'head' pointer. Finally, it sets the 'head' pointer to the newly created node and the 'stackSize' variable is incremented.

When the pop method is invoked it checks if 'head' pointer is not null. If it is not null then the stack is not empty and it gets the reference to the 'head' pointer. It then points 'head' pointer to the next node of 'head' itself. Finally, it decrements the 'stackSize' variable and returns the value of the popped element.

The 'peek' method checks if the 'head' pointer is not null, then it returns the value of the node pointed to by 'head'. If 'head' pointer is null then it returns null. The 'isEmpty' method returns the boolean value of testing the 'stackSize' variable being equal to 0.

This is an example for using the 'Stack' class:

const stack = new Stack(); stack.push(7); stack.push(3); stack.push(4); stack.push(1); stack.pop();//1 stack.push(5); stack.peek();//5 stack.isEmpty();//false 

The time and space complexities for different methods are as follows:

• pop: Time: O(1), because the linked list is not iterated, Space: O(1), as no extra data structure is needed for pop functionality.
• push: Time: O(1), because the linked list is not iterated, Space: O(1), as the extra space required is only for 1 new item.
• peek: Time: O(1), because only the 'head' node needs to be accessed, Space: O(1), because no extra data structures are used.
• isEmpty: Time: O(1), because it has only a single executable statement, Space: O(1) because no extra data structures are used.

Note: The space complexity for the overall 'Stack' class will be O(n) because the linked list will grow proportional to the number of items in the stack.

Queue Implementation

The queue is a FIFO data structure. A queue has a front side where items are enqueued and it also has a back side from where items can be dequeued. The 'add' and 'remove' methods can be used to enqueue and dequeue items respectively. This is a sample sequence of 'add' and 'remove' operations:

1. add(7)
2. add(3)
3. add(4)
4. add(1)
5. remove()
6. add(5)

This sequence of operations can be visualized as follows:

A linked list can cleverly be used to emulate a queue data structure. In the implementation of the queue, the 'head' pointer points to the back of the linked list and another pointer called 'tail' keeps track of the front of the linked list. When an item is added onto the queue the 'tail' pointer will point to the newly created node at the front of the linked list. Similarly, the 'head' pointer always keeps pointing to the back of the linked list. When an item is dequeued then the 'head' pointer will point to the next node in the linked list.

The sample add and remove operations which were visualized earlier can be further rendered by comparing to it the linked list:

In this visualization, the role of the linked list in implementing a queue can be further understood. When a new item is added to the queue, represented by a green background, the 'Tail' pointer in the linked list points to the newly created node. And the node to which the 'Tail' was pointing earlier also starts pointing to the newly created node. For the case when an item is removed from the queue, represented by a red background, the 'Head' pointer will start pointing to the next node in the sequence.

JavaScript classes can be used for implementing the queue. The two classes that will be a part of the implementation are 'LinkedListNode' class and 'Queue' class. The 'LinkedListNode' class will be used to represent a single node in the linked list. And the 'Queue' class will use 'LinkedListNode' to implement different methods for the queue.

In the 'LinkedListNode' class, the 'val' property represents the node value and 'next' property points to the next node in the linked list. The last node will always have 'next' as null.

class LinkedListNode { constructor(val) { this.val = val; this.next = null; } } 

In the 'Queue' class there are three class-level variables namely 'head', 'tail' and 'queueSize' which are used to keep track of the back of the linked list, keep track of the front of the linked list and track the size of the queue respectively.

class Queue { constructor() { this.head = null; this.tail = null; this.queueSize = 0; } add(val) { if (this.tail === null && this.head === null) { this.head = new LinkedListNode(val); this.tail = this.head; } else { const newNode = new LinkedListNode(val); this.tail.next = newNode; this.tail = this.tail.next; } this.queueSize++; } remove() { if (this.head !== null) { const result = this.head.val; this.head = this.head.next; if (this.head === null) { this.tail = this.head; } this.queueSize--; return result; } return null; } size() { return this.queueSize; } peek() { if (this.head !== null) { return this.head.val; } return null; } empty() { return this.queueSize === 0; } } 

When adding an item to the queue the 'add' method is invoked with an argument. In the 'add' method it checks if 'tail' and 'head' pointers are null. If they are null it means that the queue is empty and it will create a new linked list then point 'head' and 'tail' to this newly created node. If 'head' and 'tail' are not null then it means that the queue is not empty. In this case, it creates a new linked list node and sets the next pointer of the 'tail' node to this newly created node and then points the 'tail' itself node to the newly created node. Finally, it increments the 'queueSize' variable.

When removing an item from the queue the 'remove' method is invoked. In the 'remove' method it checks if the 'head' pointer is null. If it is, then it returns null. If 'head' is not null then it stores the value of the 'head' pointer in a 'result' variable. It then points 'head' to the next node. If 'head' becomes null then it must mean that it went past the 'tail' pointer and then 'tail' is also set to null. Because if 'head' becomes null then it must be the end of the linked list. Finally, 'queueSize' variable is decremented and the value in the 'result' variable is returned.

The 'size' method just returns the 'queueSize' variable value. The 'isEmpty' method returns the boolean result of the condition check that 'queueSize' equals to 0. The 'peek' method checks if the 'head' pointer is null if it is not then the 'head' node value is returned. But if 'head' is null then it returns null.

This is an example for using the 'Queue' class:

const queue= new Queue(); queue.add(7); queue.add(3); queue.add(4); queue.add(1); queue.remove();//7 queue.add(5); queue.peek();//3 queue.isEmpty();//false 

The time and space complexities for different methods are as follows:

• remove: Time: O(1), because the linked list is not iterated, Space: O(1), as no extra data structure is needed.
• add: Time: O(1), because the linked list is not iterated, Space: O(1), as the extra space required is only for 1 new item.
• peek: Time: O(1), because only the 'head' node needs to be accessed, Space: O(1), because no extra data structures are used.
• isEmpty: Time: O(1), because it has only a single executable statement, Space: O(1), because no extra data structures are used.
• size: Time: O(1), because it has only a single executable statement, Space: O(1), because no extra data structures are used.

Note: The space complexity for the overall 'Queue' class will be O(n) because the linked list will grow proportional to the number of items in the queue.

Applications

Some of the useful applications of stacks and queues in front-end development are:

• Depth-first search and breath-first search use stacks and queues respectively.
• Stacks can be used for implementing the undo mechanism in online text-editors.
• Queues can be used for scheduling async tasks.
• Stacks can be used for expression evaluation in online calculators.

Final Thoughts

Stacks and queues allow developers to build dynamic and useful applications. Even though JavaScript is quite expressive the ECMAScript specification doesn't put restrictions on amortized time which can allow a sub-optimal array implementation in various JavaScript engines. Linked lists allow flexibility and enable better performance for implementing stacks and queues in JavaScript. So until and unless all browsers can guarantee O(1) time complexities for 'peek', 'add', 'push', 'remove' and 'pop' methods it is desirable to use linked lists under the hood.

💡 Practice Coding

Practice coding questions that involve stacks, queues and other data structures from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.