Stack

Prerequisite: Linked List

In computer science, a stack is an abstract data type that serves as a collection of elements, with two main principal operations:

• Push, which adds an element to the collection, and

• Pop, which removes the most recently added element that was not yet removed.

The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack.

Let's take the example of an push operation. This operation adds an element to the top of the stack.

User pushes '10' in an empty stack.

Then user pushes '20' in the stack. Stack becomes '10', '20' where '20' is on the top.

Here's the code for push operation:

push(item) {
  // Here this.list is an object of LinkedList.
  // this.list = new LinkedList();
  this.list.append(item);
}

Now. Let's take an example of peek operation. This operation returns the top element of stack without removing it from the stack.

After Peek the stack remains unchanged and the top most element is returned:

Here's the code for peek operation:

peek() {
  if (this.isEmpty()) {
    return null;
  }
  const lastIndex = this.list.length() - 1;
  const returnValue = this.list.getItemAtIndex(lastIndex);
  return returnValue;
}

Now. Let's take an example of pop operation. This operation returns the top element of the stack and removes it from the stack.

After pop the top most element is removed from the stack and returned.

Here's the code for pop operation:

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const lastIndex = this.list.length() - 1;
  const returnValue = this.list.getItemAtIndex(lastIndex);
  this.list.deleteItemAtIndex(lastIndex);
  return returnValue;
}

Real Life Example:

Let's take the example of a notepad application where user can add/edit/remove text on different lines. We need to provide a feature where user can 'undo' the last operation performed.

Let's say user performs the following operations:

1. User Types "My Name is Roy" on line 1.

2. User Types "My age is 28" on line 2.

3. User Types "I live in New York" on line 3.

After the last operation the stack becomes:

User presses the undo button so we need to reverse the last operation performed by user i.e. "User Types 'I Live in New York' on line 3". So we pop the operation from the stack and reverse it.

Check out this link for implementation of this data structure using JavaScript.

Follow me on Twitter, Linkedin

Check out my portfolio at https://tejender-singh.github.io/