A Stack is a data structure that follows the LIFO (Last In First Out) principle. In other words : a data structure in which the element inserted at the last is the first element to come out.

Conversely, this also means that the first element put into the stack will always end up being the last one that goes out.


This limiting concept is extremely useful and makes it easy to manipulate structures representing those of our real world. For example, a stack may represent a stack of plates or books in which we can only remove / add each element to the top.

This structure is used all throughout programming. Here are some examples:


Operate a stack.
Have a better understanding of recursion.
Build our own stack structures.
Put into practice arrays and linked lists.
Understand the advantages / disadvantages of each implementation.

What is next?

If we have not seen the queues yet, this is the opportunity: they are implemented according to the FIFO principle (First-In-First-Out) inversely to the stacks.

We can now play with advanced algorithms such as the maze generation using a Deep Search (DFS). We may also continue with more advanced data structures such as: binary trees or hash tables.

We use C++ for code illustration, but no worries, other languages use the same logic and most often a similar syntax.

A stack is used for the following two main operations:


  void push(const T& data);  // Add new element on the top of the stack
  void pop();                // Remove element from the top of the stack



The following features are added to properly use a stack:


  bool empty() const;        // Check if stack is empty
  const T& top() const;      // Seek the element on the top of the stack.
 

Example


  stack< string > history; // Initialize stack
  history.push("paste");   // ["paste"]
  history.push("turn");    // ["paste", "turn"]
  history.pop();           // ["paste"]
  history.top();           // --> "paste"
  history.push("color");   // ["paste", "color"]
  history.push("clean");   // ["paste", "color", "clean"]

  // Get drawing history from the last action
  while (!history.empty()) {
    auto current = history.top();
    history.pop();
  }
 

Cool, now that we know what a stack is, the question remains: how to build one? Good news! The answer is: pretty easy. Below we will look at implementations based upon arrays and linked lists in order to decide which best suits our case.

Note: the Stack is an abstract data structure. The definition of their structure is solely based on their behaviour and not the underlying implementation. This is in contrast to more fundamental data structures, such as arrays and linked lists, which have strict requirements for how the storage of their data is implemented.

Linked List implementation

The basic linked list implementation is one of the easiest stack implementations we can do. Let's take back the skeleton of our structure seen in the 'linked list' course.


  template < typename T >
  class Stack
  {
  public:
    Stack() : head(nullptr) {}  // Construct as an empty stack
    ~Stack() { ... }            // Destructor (same as linked list)

  private:
    // Node structure declaration
    struct Node
    {
        // Constructor
        Node(const T& data) : data(data), next(nullptr) {}
        T data;     // Value
        Node* next; // Pointer to the next node
    };

    Node* head; // Pointer on the first element (also the top of the stack)
  }


When we want to add something to the stack (Push), we just need to add it to the beginning of the list (the top of our stack).

But wait... that's exactly what PushFront does, doesn't it?


  void Push(const T& data)
  {
    Node* newNode = new Node(data); // Allocate memory
    newNode->next = head;           // Set the next node to be the head
    head = newNode;                 // Set head to the new node
  }
  

For the Pop operation, nothing is easier:   just delete the first item in the list.


  void Pop()
  {
    if (!head) // Empty stack error
      return;

    auto tmp = head;      // Get the current top
    head = head->next;    // Set the head to point to the next node
    delete tmp;           // Delete the node
  }
  

The Empty and Top functions are also trivial.


  bool Empty() const { return (head) ? false : true; }

  const T& Top() const
  {
    if (!head); // Throw Exception
    return *head;
  }

  
The above implementation gives you the ideas involved, and any optimization may be accomplished by modifiying the linked list code.

Array implementation

Using a table implementation for a stack is a simple approach and only involves keeping the count.


  template < typename T >
  class Stack
  {
  public:
    // Allocate/Deallocate stack memory
    Stack(const int size) : count(0), max_size(size) {  stack = new T[max_size]; }
    ~Stack() { delete[] stack; }

  private:
    int count;          // Keep track of current stack size (and therefore the top index)
    const int max_size; // Keep track of the max size to check if full
    T* stack;           // Pointer on the array

    Stack(); // Forbid default constructor
  }


To add something to the stack (Push), we just have to put it at the count index and increment the count.


  void Push(const T new_data) {
    if (count == max_size) // Stack overflow exception

    stack[count] = new_data; // Set data
    ++count;                 // Update count
  }
  

For the Pop function, nothing is easier: we just decrement the index.


  void Pop()
  {
    if (count == 0) // Empty stack error
      return;

    --count;  // Change top index
  }
  

The Empty and Top functions are also still trivial.


  bool Empty() const { return count == 0; }
  const T& Top() const { return stack[count]; }
  

Stack Overflow !

That's what happens if we try to add an item to a full stack.

A stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program.

In the case of the call stack this will happen if we have an infinite loop / recursion. (a fairly common bug!)

Dynamique Array (Vector) implementation

If we were using a dynamic implementation then when our top index reaches the capacity index, we simply double the size of the stack. This implies a loss of performance because it requires memory allocation as well as a copy of all the elements.

In short

Linked List
Insert and delete operations in O(1).
Can grow dynamically.
Memory allocation/deallocation required for Insert and Delete operations.
Slightly more memory usage due to additional storage of pointers.
Array
Insert and delete operations in O(1).
Can not grow dynamically: it requires a maximum size at initialization.
An oversized table causes amount of wasted memory.
Possible stack overflow problem.
Dynamique Array (Vector)
Insert and delete operations in O(1) (except on resize).
Can grow dynamically.
Resize operation in O(n).
An oversized table causes amount of wasted memory.