Data Structure Series: Stack & Queue

Introduction

We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. Feel free to leave a comment if you have any questions!

Table of Contents

1. What are Stacks and Queues?
2. Implementation in JavaScript
3. Implementation Using Linked List
4. Big O
5. Helpful Resources

1. What are Stacks and Queues?

Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.

Stack

A Stack is a linear data structure that follows LIFO (Last-In, First-Out) principle. With LIFO principle, whatever the data came in last would be the first to be taken out. An example you'd be familiar with would be the Undo functionality in a text editor like Word Processor. In a Word document, the Undo command undoes any last action you do, which includes formatting text, moving blocks, typing and deleting text, formatting, and etc. Using the Undo command until the end will eventually take you to a blank page where you started like a Stack.

I remember I used to play with this plastic toy named "Rock-A-Stack". This toy comes with with a base with a center cone on top, and multiple colorful plastic rings in different sizes. Your goal is to stack the rings on top of the base in the order of the size from biggest to smallest to form a pyramid shape. The ring cannot be taken out from the bottom because of the base, you will have to take out the whatever the ring is at the topmost position of the stack in order to re-arrange the order. A Stack in the programming world is fundamentally no different than the toy Rock-A-Stack.

Queue

A Queue is also a linear data structure, but follows FIFO (First-In, First-Out) principle. With FIFO principle, whatever the data came in first would be the first to be taken out. A printer queue is a good example of a Queue data structure. In an office setting where one or few printers are shared by multiple people, queue makes sure that the printing tasks are executed in the chronological order they came in. Even if you were to use a printer at home and print multiple instances of document pages, it pushes the tasks in a queue. Let's say you forgot to turn on the printer, the queue will make sure that the printing tasks are not lost, but will execute each tasks as a queue so that first printing task will be executed first once the printer is turned on.

A real life example would be a security scanning line at the TSA, or any other lines like at an amusement park, restaurant, and etc. Nobody likes it when someone cuts the line. You have to wait until your turn comes. If you are the first one to arrive at the TSA line, you will go through the security scanning first. That's a Queue right there, First-In, First-Out.

In Summary, Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.

2. Implementation Using Array

Stacks and Queues can simply be implemented using a built in Array in JavaScript. For Stacks, you just need to use Array's push() and pop() methods to add and element at the end of an array, and remove the element at the end. For Queues, you will have to use push() method to add an element at the end, but use shift() to take out the first element that was pushed in. They will look something like this:

Stack

const stack = [];
stack.push('Baseball')
stack.push('Soccer')
stack.push('Football')
stack.push('Basketball')

return stack // ["Baseball", "Soccer", "Football", "Basketball"]

stack.pop() // returns "Basketball"

return stack // ["Baseball", "Soccer", "Football"]

Queue

const queue= [];
queue.push('Peanut Butter')
queue.push('Milk')
queue.push('Apple')
queue.push('Cheese')

return queue // ["Peanut Butter", "Milk", "Apple", "Cheese"]

queue.shift() // returns "Peanut Butter"

return queue // ["Milk", "Apple", "Cheese"]

This is totally easy and convenient for Stacks. But there is a downside of implementing a Queue using Array. Can you guess what it is? push() and pop() methods have time complexity of O(1) while shift() and unshift() methods have time complexity of O(N). This is because when you are adding or removing an element of an array, all the elements to the right side of that element has to rearrange their position, thus indices of those get reassigned.

Since shift() and unshift() are pretty costly in Array, let's see if there's a way to optimize Stacks and Queues. Aha! Linked Lists are great at inserting/deleting the first and the last element! If you remember how Linked List works, a Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its head to the tail. For us to visualize it better using Stacks & Queues, we will call the pointers first and last instead of head and tail.

Singly Linked Lists' nodes reference their next node but not their previous. Adding a new first node to a Singly Linked List is quick, we just need to replace the new first, and set its next node to the old first node. Removing the current first node is quick as well, we just need to remove the current first node, and set its next node as the new first node. This makes Singly Linked List a perfect candidate for Stacks to follow LIFO (Last-In, First-Out) principle. However, if we were to add a new node to a queue (enqueue) and remove the last node (dequeue) using Singly Linked List, it will not be efficient to dequeue the last node. This is because a Singly Linked List's node does not reference its previous node, so we will have to traverse the entire list to find out what the previous node of last node is. The previous node of last node will need to be reassigned as the new last node. Thus, a Queue will be more optimized to utilize Doubly Linked List over Singly Linked List. Check out the code below:

3. Implementation Using Linked List

Stack

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // push() method adds a new node at the top (first)
    push(value){
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            let oldNode = this.first;
            this.first = newNode;
            this.first.next = oldNode;
        }
        return ++this.size
    }
    // pop() method removes a node at the top (first)
    pop() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value
    }
}

Pseudocode for push():

• The function should accept a value
• Create a new node with that value
• If there are no nodes in the stack, set the first and last property to be the newly created node
• If there is at least one node, create a variable that stores the current first property on the stack
• Reset the first property to be the newly created node
• Set the next property on the node to be the previously created variable
• Increment the size of the stack by 1, and return it

Pseudocode for pop():

• If there are no nodes in the stack, return null
• Create a temporary variable to store the first property on the stack
• If there is only 1 node, set the first and last property to be null
• If there is more than one node, set the first property to be the next property on the current first
• Decrement the size by 1
• Return the value of the node removed

Queue

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // enqueue() method adds a new node at the end (last)
    enqueue(value) {
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    // dequeue() method removes a node at the beginning (first)
    dequeue() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value;
    }
}

Pseudocode for enqueue():

• This function accepts a value
• Create a new node using the value passed to the function
• If there are no nodes in the queue, set this node to be the first and last property of the queue
• Otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node

Pseudocode for dequeue():

• If there is no first property, just return null
• Store the first property in a variable
• See if the first is the same as the last (check if there is only 1 node). If so, set the first and last to be null
• If there is more than 1 node, set the first property to be the next property of first
• Decrement the size by 1
• Return the value of the node dequeued

A bit more hassle to implement than just using Array, but this will make the data structure more optimized. I definitely recommend you to go check out the Data Structure Series blog post I wrote on Linked List to learn about it if you need a refresher or have a problem comprehending the code above.

4. Big O

• Space Complexity:

  • O(n)
  • Space complexity of this data structure is linear, as the size of the list increase, so does the space

• Push/Pop and Enqueue/Dequeue:

  • O(1) Time Complexity
  • If we were to utilize Linked List over Array, both Push/Pop and Enqueue/Dequeue's time complexity can be optimized to O(1). Furthermore, Linked List is not the only optimized way to implement Stacks and Queues, for example, you can create those classes using an object as its storage. Here's video on this implementation if you are interested, but as you can see, there are many ways to create Stack/Queue.

5. Helpful Resources

Online Course (Udemy Course)
Check out this Udemy course named JavaScript Algorithms and Data Structures Masterclass! It is created by Colt Steele, and I referenced his code for the data structure implementation part of this blog post. Personally, I didn't know where to start with algorithms and data structures especially coming from a non-tech background. This course is very well structured for beginners to build a foundation on these topics.

Visual Animation (VisuAlgo)
Data structures can be difficult to comprehend for some people just by looking at the code/text. The instructor in the course above uses a website named VisuAlgo that has visual representation of algorithms and data structures through animation.

Data Structure Cheat Sheet (Interview Cake)
Also, here's a really well-summarized cheat sheet/visualizations on data structures.