Hello There, I hope all is well ?

Today is another day to talk about DSA. I will be discussing Stacks and Queues Data Structures, Stacks and Queues Data structures are very important in the programming world as they are used in most operations in programming.

Let’s talk about them and find out why they are that much needed.

Stacks: Stacks are also another type of Linear data structures which also have their own ways of operations that differs from the others, a stack structure uses a principle of LIFO – Last In First Out. in this principle any value or node added last in the list is the first to be deleted, this is because there is no other exit except the top of the stack and this is exactly what makes it special. a popular concept of this is a stack of plates placed on top of each other or books stacked on one another, a decent way to get to a particular plate is to take the topmost off one by one until we reach the preferred plate, so in a stack  the only way to get to a particular element is to take the previously added out before getting access. this is the LIFO Principle. Stacks can be implemented for instance in a case of reversing a word by taking the last one out subsequently to combine the popped items list. Again a stack can be used in a browser to go back from a URL history because every visited link is just placed on top of each other so to revisit the previous one the current URL needs to pave way for the previous to appear. now that we have seen the logics on which a stack works why don’t we take a look how it works with codes. because of the nature of a stack the focus is mostly placed on it’s push() and pop() Methods. The best way to implement a stack is using a linked list approach, arrays can be used but it comes with some short falls because of the iterative nature of arrays that may result into some time factors so the best way to implement a stack for a quick operation is to use a linked list.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  push(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      var temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }
  pop() {
    if (!this.first) return null;
    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }
}

There we go with the simple creation of a stack and its important methods, the only difference here is instead of using a head and a tail we opted to use first and last just to best match the definition of a stack. use the same processes we implemented during the Linked-List section to test the Stack implementation.

Queues: Queues in the other hand use the principle of FIFO – First In First Out.  In a queue elements are added to the list from the back and wait for their turn before they exit the list. let’s think of it as people queuing for a bus ticket when the last person comes He / She positions at the back and this what we call Enqueuing and when the front person gets served and drops from the list is referred to as Dequeuing. In a queue we refer to two pointers as Front and Rear The front keeps track of the first element added to the list as the rear holds the information of the last element added to the list. there are several use cases of queues in computing ie. a CPU running a schedule command, it takes care of the first or early schedules and chains it with the next inline to be executed, another use case of a queue could also be Handling of interrupts in real-time systems.

Let’s take a look at the Queue in action based on it’s nature, here there is no push() or pop() method but rather a queue() and dequeue() method to facilitate adding and removing since pushing will require some modification to the indexes.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  enqueue(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

  dequeue() {
    if (!this.first) return null;

    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }
}

similar to stacks we defined the node and queue and made provision for the important methods that run on the queues. these methods on both the Stacks and Queues have the best time complexity of O(1) Constant by their standards because there is no iteration going on when adding or removing elements in and out of their lists.

In later Data Structures the use of Stacks and Queues will become more clearer as we use them to achieve some other implementations.

I think that should be enough for today let’s continue our discussion in the next section. Stay Blessed 🙂