Stack Data Structure

A stack is an abstract data structure which is used to store a collection of elements with the ability to add or remove elements at only one endpoint (often called the top). Due to this property of a stack which allows addition or removal of elements only from one endpoint, a stack is also known as a Last In First Out (LIFO) data structure. It means that the last element which is added to the stack will be the first one to come out of the stack during removals.

Visualizing a Stack Data Structure

A stack can be visualized as a vertical space into which objects can be added or removed from the top. Also the last added element will be at the top of stack. The image below depicts how a stack looks if it were to exist in real world (Image Source).

The spring makes sure that the element which is added last will be at the top of stack thereby making the top element easily accessible. Any element added to the stack will move the existing top element down and the newly added element will be at the top. While removing elements, the topmost element is removed and after removal, the next top element will move to the top.

Basic Operations Supported by a Stack

Below are all the operations supported by a stack abstract data structure:

Let us now go through each operation in detail.

Push an element to the Stack

This operation allows us to push an element into open end of stack. The animation below pushing of 4 elements into a stack.

Note that we show the stack data structure as a vertical space with storage slots from top to bottom. But in theory a stack can be visualized in any orientation as long as insertion and removal of elements happen only from one end.

Pop an element from the Stack

This operation allows us to remove the element present at the top of stack. The animation below depicts popping out all the elements present in a stack.

Access the element present at the top of Stack

This operation allows us to access the “top” element of the stack. It can be used in cases where we just need temporary access to the top element in the stack and removal/popping of the top most element is not necessary.

Check if the Stack is Empty

This operation is useful for finding out if a stack is empty. This is helpful especially to prevent popping an element from an empty stack. Or to prevent accessing the top most element in an empty stack etc.

Implementing Stack Abstract Data Structure

Array implementation of Stack

/******************************************************************************
C++ Implementation of Stack ADT using Vector/List
*******************************************************************************/

#include <iostream>
#include <vector>

// Using template with generic type T
// So that we can decide the type of elements stored
// when we use the stack
template <typename T> class Stack {
private:
  std::vector<T> array;
  int top_idx = -1;

public:
  Stack(size_t size) : array(size) {}

  void push(T element) {
    // Increment the current top position
    // and add the element at new top position
    top_idx = top_idx + 1;
    array[top_idx] = element;
  }
  
  T pop() {
    // Store the top element for returning and
    // Move the top pointer to the next element
    T result = array[top_idx];
    top_idx = top_idx - 1;
    return result;
  }
  
  bool is_empty() const { return top_idx < 0; }
  
  T &top() const { return array[top_idx]; }
};

// Let us now test the Stack ADT!
int main() {
  Stack<int> stk(5);
  stk.push(1);
  stk.push(2);
  stk.push(3);
  while (stk.is_empty() != true) {
    std::cout << stk.pop() << " ";
  }
  return 0;
}

TODO: Linked list implementation of Stack along with explanation.

When to use a Stack data structure?

Stack is a natural choice for handling undo and redo operations on a document. Let’s say we we have typed the word “a w e s o m e” character by character in a text editor. What should happen when we do undo or ctrl+z the first time? The last character which is typed should be deleted i.e, ‘e’. So the remaining text is “a w e s o m”. The next time we perform the undo operation, the last typed character among the remaining characters should be removed. The text then becomes “a w e s o”. This is similar to what a stack does i.e., while removing/reversing an operation, it removes/undoes the last operation (the last character typed in this case). Similarly if we store all the undo operations performed in another stack, it can be used as a reference while redoing any undo operation.

Stack is also used for managing execution of nested function calls. For example if function A calls function B which in turn calls function C, at the time function A calls B, function A is added to the stack. Similarly function B is added to the stack when function C is called. Now when function C finishes it’s work, the top most / latest function in the stack - function B regains control. After function B finishes, the next top most function - function A regains control. This mechanism is performed by the operation system using a stack.

In any scenario where the last/latest element added to a collection has to be retrieved first (Last in First out - LIFO), stack is a natural choice. Eg: Backtracking.

References

• Wikipedia
• Stack using an Array
• Stacks - usfca.edu