DataStructures Series #5 – The Stack ADT

Originally posted on my medium page: https://medium.com/@otarutunde

The Stack ADT

The stack ADT allows operations only at one end, adding or removing elements is usually performed at a single position which is known as the top.

This means new elements are added to the top of a stack and an element is removed from the top of the stack. In a stack, the insertion and deletion operation are performed based on the LIFO (last in, first out) principle.

The Stack

Stack Operations:

  • Push Element
  • Pop Element
  • Peek Element

Push Element — This would insert an element into the stack.

Pop Element — This would remove the element on top of the stack.

Peek Element — This would fetch and not remove the element on top of the stack

Implementation

One way to implement the stack data structure is to use an array.

Below is a pseudocode implementation:

Initialise new array {random size}

set currentIndex = 0;

insert(element) : set array[currentIndex] = element;
                  curentIndex++;

pop() : value = array[currentIndex - 1];
        set array[currentIndex - 1] = null;
        currentIndex--;
        return value;

peek() : if (currentIndex == 0)
            return null;
         otherwise:
            return array[currentIndex - 1];

One thing we didn’t cater for in our implementation is to check if the currentIndex hasn’t exceeded the size of the array, for this case, we have to create another array with a bigger size and then copy all the elements from the previous array into the new one. This can affect the performance of the operations on the Stack from time to time hence why the array is not ideally the best data structure to use in implementing a stack.

Real life Applications

  • Browser tab history management — We can use 2 stacks to navigate the browser history, one for the back button (back-stack) and the other for the forward button (forward-stack). Every url visited in the browser is inserted into the back-stack. Each time the back button is clicked, the url on top of the back-stack is popped and inserted into the forward-stack. The same thing happens when the forward button is clicked, the url in the forward-stack is popped and inserted into the back-stack. At every point in time the url being displayed in the browser is the url peeked from the back-stack. The back button is inaccessible if one element is left in the back-stack and the forward button is inaccessible if no element is present in the forward stack. An assumption here is that the back-stack will always contain at least one element (landing page).

  • Undo/Redo in text editors — We can have a stack each for the undo action (undo-stack) and the redo action (redo-stack). Each time a text change is done in the text editor, a snapshot of the current state is inserted into the redo-stack. , the undo action will pop the snapshot at the top of the redo-stack and insert it into the undo-stack. The redo action will pop the snapshot at the top of the undo-stack into the redo-stack. At every point in time, the text displayed in the text editor is peeked from the redo-stack. The redo action becomes inaccessible when the undo-stack is empty and the undo action becomes inaccessible when the redo-stack is empty.

REFERENCES: