Stacks.


Introduction to stacks:-

The stack is a linear data structure in which order of the operations is important.That is to say, all the operations are performed on a single point or same end called head node or top node.

For example, assume that a cleaner is cleaning serving plates in a hotel. As he/she cleans them, the cleaner will keep on putting on top of each other. Meanwhile, for any order, the server will come and pick a serving plate from the top of the stack of cleaned plates. If you observe in this process adding and removing a plate happening at the same place i.e top.

Some of the real life examples include

  • Stack of chairs
  • Stack of books in library, etc.

In stacks, the last element that gets in will be the first element to be removed. Hense the stacks are also called as Last In First Out(LIFO) or First In Last Out(FILO) data structure.

Stacks are just a concept built using other data structures. Even arrays can be used to implement the stacks. But In the case of implementing with arrays, we lose the advantages of dynamic size and heterogeneous data processing. Since we insert and remove the data from the same end, a singly linked list is best suitable for the implementation of stacks. 

The possible operations on a stack are:- 

  1. Push.
  2. Pop.
Here, we will use a singly linked list to implement the stack.Meanwhile, If you are not aware of the singly linked list, I have written it here. Please do check it. If you understand singly linked lists, implementation of stacks is nothing. 

1. Push:-

Push operation adds a new element to the stack. The element is added to the top or head node. The newly added node will become the new head or top. 
stack push illustration.
The Pseudocode for the push operation is as shown below.
stacks push pseudocode.
Please do find the implementations in java and javascript below.

 

public StacksWithSinglyLinedList push(Object value) {
        Node newNode = new Node(value);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
            this.length += 1;
        }
        else {
            Node currentHead = this.head;
            newNode.next = currentHead;
            this.head = newNode;
            this.length += 1;
        }
        return this;
    }
push(value) {
        var newNode = new Node(value);
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
            this.length += 1;
        }
        else {
            var currentHead = this.head;
            newNode.next = currentHead;
            this.head = newNode;
            this.length += 1;
        }
        return this;
    }

The time complexity of push operation involves adding new node the current head which available under the variable head. As a result, the time complexity of push operation is O(1).

2. Pop:-

Pop operation removes the element at the current node. 

stack pop illustration.
The pseudocode is as shown below.
stack pop pseudocode.
public Object pop() {
        if (this.length == 0) {
            return null;
        }
        if (this.length == 1) {
            Node currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        Node currentHead = this.head;
        Node newHead = currentHead.next;
        this.head = newHead;
        return currentHead.value;
    }
pop() {
        if (this.length === 0) {
            return null;
        }
        if (this.length === 1) {
            var currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        var currentHead = this.head;
        var newHead = currentHead.next;
        this.head = newHead;
        return currentHead.valuel
    }

The time complexity of pop operation involves removing the current head which available under the variable head. Therefore the time complexity of pop operation is O(1).

To sum up the stack data structure, let’s see some of the real-time applications of the stack.

  • The function call stack maintained in memory using the stack data structure.
  • Evaluating parenthesis in mathematical expressions.
  • Managing the history of the browser.
  • Undo and redo action while editing a document.