Data Structures: Stacks And Queues II

#javascript #webdev #beginners #tutorial

Hey guys, I am back with the second and last part of the Stacks and Queues series. In the First part of this series we looked at what data structures are, the different types of data structures, analogies for Stacks and Queues; some real-life applications of Stacks and Queues, and their use cases. In this part, we are going to look at how to implement Stacks and Queues in JavaScript.

Stacks

The most common operations that are performed on a stack are:

Push (Add an element to the top of the stack)
Pop (Remove top element from the stack)
Peek (Show the Top Element)
IsEmpty (Return true or false if the stack is empty or not)

A relatively simple way to implement a stack in JavaScript is with arrays. JavaScript arrays have built-in push and pop methods that operate similarly to their stack counterparts. Remember, stacks operate on a LIFO basis (Last In First Out) meaning the newest element is always at the top and the first to be removed. Now let's see how to implement a stack and its operations with an array.


const sports = [];



// Push operations
sports.push("Soccer"); // ['Soccer']
sports.push("Basketball"); // ['Soccer', 'Basketball']
sports.push("Golf"); // ['Soccer', 'Basketball', 'Golf']

console.log(sports); // expected return ['Soccer', 'Basketball', 'Golf']

//Pop operations 
sports.pop() // removes and returns 'Golf'
console.log(sports); // expected return ['Soccer', 'Basketball']
sports.pop() // removes and returns 'Basketball'
console.log(sports); // expected return ['Soccer']

//Peek operation
console.log(sports[sports.length - 1])

// isEmpty operation
console.log(sports.length === 0) // returns true if array is empty and false if not

This method of stack implementation is very simple but is not very structured and scalable, so let's make a more structured version of a stack using JavaScript Classes. Classes are a template for creating objects. They encapsulate data with code to work on that data.


class Stack { // declare the class of name Stack
      constructor (){
        this.data = {} // this is where we shall be storing our data you can use an array but am using an object
        this.top = 0;
      }
}

let names = new Stack()

Running the above code will set the names variable to an object with 2 properties data and top, which are an object and a number 0. The data object will be used to store our elements and top will keep track of the current top of the stack and the number of elements in the stack. Now let's make our various stack operations as methods in the Stack class.

// INSIDE THE STACK CLASS

  push(element) {
    this.top++ // increase top by 1
    this.data[this.top] = element; // set current top element
  }

First is the push operation. When we add a new element to the stack; we increment the this.top by 1, and set it to the new element the data object.

//INSIDE STACK CLASS
  pop() {
    if(this.top === 0) return "stack is empty";
    let element = this.data[this.top]; // store current top element to return later
    delete this.data[this.top]; // delete current head from stack
    this.top-- // decrease top by 1
    return element
  }

In the pop operation, we first check if the stack is empty; if empty we return a string letting the user know, if not empty, we store the current top element in a variable, delete it from the data object, decrease this.top by 1, and then return the variable.

//INSIDE THE STACK CLASS
  peek() {
    if (this.top === 0) return "stack is empty";
    return this.data[this.top];
  }

All we are doing in the peek operation is checking if the stack is empty and returning the top element in the stack if it's not empty.

//INSIDE THE STACK CLASS

  isEmpty() {
    return this.top === 0; // returns true or false

  }

The isEmpty operation returns true if the this.top is 0, which means the stack is empty and false if the this.top is greater than 0. Our Stack class now looks like this:

class Stack {

  // declare the class of name Stack

  constructor() {
    this.data = {}; // this is where we shall be storing our data you can use an object or an array but am using an object
    this.top = 0;
  }

  push(element) {
    this.top++; // increase top by 1
    this.data[this.top] = element; // set current top element
  }

  pop() {
    if (this.top === 0) return "stack is empty";
    let element = this.data[this.top]; // store current top element to return later
    delete this.data[this.top]; // delete current head from stack
    this.top--; // decrease top by 1
    return element;
  }

  peek() {
    if (this.top === 0) return "stack is empty";
    return this.data[this.top];
  }

  isEmpty() {
    return this.top === 0;
  }
}

That's it for Stack implementation with Javascript classes. You can test and tinker with the code here

Queues

Queues operate on a FIFO basis (First In First Out) this means the head of the queue will always be the oldest element, while the tail will be the newest element. Some of the most common operations that are performed on a stack are:

Enqueue (Add an element to the queue)
Dequeue (Remove the oldest element from the queue)
Front (Shows the oldest element in the queue)
Rear (Shows the newest element in the queue)
IsEmpty (Return true or false if the queue is empty or not)

Just like Stacks, we can implement Queues in Javascript using arrays like so.


const queue = [];

// Enqueue operation 
queue.push("Toyota") // adds an element to the array ["Toyota"]
queue.push("Kia") // adds an element to the array ["Toyota", "Kia"]
queue.push("BMW") // adds an element to the array ["Toyota", "Kia", "BMW"]
queue.push("Tesla") // adds an element to the array ["Toyota", "Kia", "BMW", "Tesla"]

console.log(queue) // expected return ["Toyota", "Kia", "BMW", Tesla]


// Dequeue operation
queue.shift() // removes and returns first element "Toyota" from array ["Kia", "BMW", Tesla]
console.log(queue) // expected return ["Kia", "BMW", Tesla]
queue.shift() // removes and returns first element "Kia" from array [ "BMW", "Tesla"]
console.log(queue) // expected return ["BMW", "Tesla"]

// Front operation 
console.log(queue[0]); // shows the oldest element in the array or undefined if the array is empty

//Rear operation
console.log(queue[queue.length - 1]); // shows the newest element in the array or undefined if the array is empty


// isEmpty operation
console.log(queue.length === 0); // returns true or false if the array is empty or not.

This is cool, but let's make it cleaner using Javascript classes.


class Queue { // declare the class of name Queue
      constructor (){
        this.data = {} // this is where we shall be storing our data you can use an array but am using an object
        this.head = 0; // keeps track of the head element (oldest)
        this.tail = 0;// keeps track of the tail element (newest)
      }
}

In the queue constructor, we are keeping track of both the head and tail elements using this.head and this.tail. The difference between tail and head is the number of elements in the queue. Now for the operations.


// INSIDE QUEUE CLASS

  enqueue(element) {
    this.data[this.tail] = element; // set element to tail 
    this.tail++ //Increse tail by 1
  }

When the enqueue method is called we will set the new element to the current value of this.tail in the data object and increment this.tail by 1.

// INSIDE QUEUE CLASS

  dequeue() {
    if(this.tail - this.head === 0) return "Queue is empty";
    let element = this.data[this.head] // set variable to current head
    delete this.data[this.head] // delete current head
    this.head++ //Increse head by 1
    return element // return previous head element
  }

The dequeue method is a bit more complex compared to the enqueue method. when the dequeue method is called we first check if the queue is empty, if it is empty, we return a string letting the user know, if it is not empty, we store the current this.head in a variable and delete it from the data object, then we increment the this.head by 1 so it points to the next element and then returns the variable containing the previous head.

// INSIDE QUEUE CLASS

  front() {
    if(this.tail - this.head === 0) return "Queue is empty"; // if tail minus head equals 0, the queue is empty
    return this.data[this.head] // if queue not empty, return current head
  }

The front method returns the oldest element in the queue after checking that it is not empty.


// INSIDE QUEUE CLASS

  rear() {
    if(this.tail - this.head === 0) return "Queue is empty"; // if tail minus head equals 0, the queue is empty
    return this.data[this.tail - 1] // if queue not empty return current tail - 1 which is the last element in the queue
  }

Similar to the front method, the rear method returns the last element on the queue if the queue is not empty.

// INSIDE QUEUE CLASS

  isEmpty() {
    return this.tail - this.head === 0; // if tail minus head equals 0 queue is empty returns true else returns false
  }

Lastly, the isEmpty method simply returns true or false if the queue is empty or not. So our complete Queue class looks like this


class Queue { // declare the class of name Queue
  constructor (){
    this.data = {} // this is where we shall be storing our data you can use an array but am using an object
    this.head = 0;
    this.tail = 0;
  }

  enqueue(element) {
    this.data[this.tail] = element; // set element to tail 
    this.tail++ //Increse tail by 1
  }

  dequeue() {
    if(this.tail - this.head === 0) return "Queue is empty";
    let element = this.data[this.head] // set variable to current head
    delete this.data[this.head] // delete current head
    this.head++ //Increse head by 1
    return element // return previous head element
  }

  front() {
    if(this.tail - this.head === 0) return "Queue is empty";// if tail minus head equals 0 queue is empty
    return this.data[this.head] // if queue not empty return current head
  }

  rear() {
    if(this.tail - this.head === 0) return "Queue is empty"; // if tail minus head equals 0 queue is empty
    return this.data[this.tail - 1] // if queue not empty return current tail
  }

  isEmpty() {
    return this.tail - this.head === 0; // if tail minus head equals 0, the queue is empty returns true else returns false
  }
}

You can test the code here.

That brings us to the end of this 2-part series on Stacks and Queues. Please leave a like if you learned something, Thanks and I'll see you in my next post.