Data Structure Series: Stack & Queue
Tags: javascript, programming, stack, queue
Published: 2021-08-11 14:39:26

## Introduction

![data-structure-series-intro](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5xpt6in1hml7m89611hj.png)

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?](#first)**
**2. [Implementation in JavaScript](#second)**
**3. [Implementation Using Linked List](#third)**
**4. [Big O](#fourth)**
**5. [Helpful Resources](#fifth)**

***

## 1. What are Stacks and Queues? <a name="first"></a>
> 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

![stack-image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wfhctzpx93cx1xlrpzof.png)

**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**.

![rock-a-stack](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rqxo0tn2txybwehpujkp.jpg)

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
![queue-image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8j65qlit4tnkjs97ixja.png)

**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.

![queue](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tycfp7jhs8jh8ik1x37o.png)

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 <a name="second"></a>

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
```javascript
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
```javascript
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 <a name="third"></a>

**Stack**
``` javascript
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**
``` javascript
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](https://dev.to/chuckchoiboi/data-structure-series-linked-list-3eb2) 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 <a name="fourth"></a>
![big-o](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hxvr5q5ggul1czucmkh9.png)

- **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](https://youtu.be/1AJ4ldcH2t4?t=236) video on this implementation if you are interested, but as you can see, there are many ways to create Stack/Queue.

***

## 5. Helpful Resources <a name="fifth"></a>
[**Online Course**](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/) **(Udemy Course)**
Check out this Udemy course named JavaScript Algorithms and Data Structures Masterclass! It is created by [Colt Steele](https://www.youtube.com/c/ColtSteeleCode), 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**](https://visualgo.net/en) **(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**](https://www.interviewcake.com/data-structures-reference) **(Interview Cake)**
Also, here's a really well-summarized cheat sheet/visualizations on data structures.