Stacks

In brief

Article summary

Suppose you want to store the history of visited websites in your program. An appropriate structure to store the timeline of visited web sites is a stack, like a stack of plates in your cupboard. An important peculiarity of this data structure is that the most recently visited site appears at the top of the structure. A second one, is that when it comes to remove an element, as e.g. to get a plate, the most recently added is removed. This data structure is omnipresent in computer science, for example to store the sequence of function calls when a program is executed.

Two possible implementations of a stack are proposed. It is shown that they can be used independendly if the primitives abstract the details.

Main takeaways

• Stacks are data structures where the first element added is the last element removed.

• Depending on the implementation of the stack, some operations may take longer than others.

• Using primitives allows to hide implementation details.

Article contents

1 — What is a stack?

A stack is a data structure with restricted access, which means that its processing is limited to a few manipulations, called “primitives”. This type of data is managed in such a way that each new element is added to the top of the stack and the last element added is the first to be removed. This access strategy is called LIFO (Last In, First Out).

Stacks are particularly useful for processes that require data to wait for later processing. This is the case when calculating an arithmetic expression in postfixed notation, where the data (operands) appear before the operator, for example, 3 2 + to perform the sum of 3 and 2.

Stacks are also ideal for making recursive processing iterative. The values corresponding to the recursive calls are pushed, and popping them simulates the return of the calls.

2 — Primitives

In a program using a stack, the implementation details of the data are abstracted away. The program simply pushes or pops elements from the stack using sub-programs known as “management primitives”. The main primitives for stack operations are:

• initialise – Initialises the stack.
• push – Adds an element to the top of the stack.
• pop – Removes the top element from the stack.
• is_empty – Returns true if the stack is empty, and false otherwise.

3 — Implementation of stacks

There are tested and optimised implementations of stacks in almost all, if not all, programming languages. For pedagogical purposes, two possible implementations of the stack management primitives are studied, one of which will be implemented during the practical session.

3.1 — Use of lists

Managing a stack can be done by adding and removing elements ar the beginning of the list.

Here is a possible implementation of a stack, using a list to store information.

"""
This module provides an implementation of the primitives to handle a stack of values. 
The stack is materialized by means of a list with a size limit to simulate an array.

"""
from typing import List,Any

type Stack = List[Any]

def initialise() -> Stack:
    return []

def is_empty(stack: Stack) -> bool:
    """
    This function checks if the stack is empty.
    In:
        * stack: Stack to check.
    Out:
        * True if the stack is empty, False otherwise.
    """
    return len(stack) == 0

def push(stack: Stack, item: Any) -> None:
    """
    This function adds an element to the stack.
    The element is added at the end.
    In:
        * stack: Stack to modify.
        * item: Element to add.
    """
    stack.append(item)

def pop(stack: Stack) -> Any:
    """
    This function removes the last element of the stack.
    In:
        * stack: Stack to modify.
    Out:
        * The last element of the stack.
    """
    return stack.pop()

def display(stack: Stack) -> None:
    """
    This function displays the content of the stack.
    In:
        * stack: Stack to display.
    """
    print(stack)

import java.util.ArrayList;
import java.util.List;

public class ListStack {
    private List<Object> stack;

    public ListStack() {
        this.stack = new ArrayList<>();
    }

    public boolean isEmpty() {
        /**
         * This function checks if the stack is empty.
         * @return True if the stack is empty, False otherwise.
         */
        return this.stack.isEmpty();
    }

    public void push(Object item) {
        /**
         * This function adds an element to the stack.
         * The element is added at the end.
         * @param item Element to add.
         */
        this.stack.add(item);
    }

    public Object pop() {
        /**
         * This function removes the last element of the stack.
         * @return The last element of the stack.
         */
        if (this.stack.isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return this.stack.remove(this.stack.size() - 1);
    }

    public static void main(String[] args) {
        ListStack stack = new ListStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack after pushes: " + stack.stack);
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack after pop: " + stack.stack);
    }
}

3.2 — Use of linked lists

Conceptually, to implement the primitives that define the behaviour of a stack data structure, it is sufficient to access the top element of the stack, and to the successor of each element. A stack is thus reduced to a pointer to its top element, and an element stores a value and a pointer to its successor. A linked list is an appropriate data structure to define the primitives of a stack as illustrated in the following figure:

The implementation of a stack using a linked list, more precisely a doubly-linked list, is left for the practical activity.

4 — A practical use

An example of use of the stack data structure is given below with the objective of reversing a chain of characters (never do it in practice, it is definitely not the optimal way of performing this task). The characters composing an input string are added one by one in a queue. Elements of the stack are then poped one by one to obtain the reversed of the input string.

if __name__ == "__main__":    
    s : str =input("Enter a string: ")
    #initialize stack with the length of the string
    st : Stack = initialise()
    
    for i in range(len(s)):
        push(st, s[i])

    revstr : str = ""
    while not is_empty(st):
        revstr += pop(st)
    print(f"Reverse of {s} is {revstr}")

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports
import java.util.Scanner;

public class Main {
    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Read input from user
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String sentence = scanner.nextLine();
        StackArray<Character> s = new StackArray<>(sentence.length());
        // Fill the stack with characters from the sentence
        for (Character c : sentence.toCharArray()) {
            s.push(c);
        }
        // Pop stack to reverse sentence
        StringBuilder reversedSentence = new StringBuilder();
        while (!s.isEmpty()) {
            reversedSentence.append(s.pop());
        }

        // Print the reversed sentence
        System.out.println("Reversed sentence: " + reversedSentence.toString());
        
        scanner.close();
    }

}

Note that the preceding program may use one implementation of the stack or the other, as the primitives hide the implementation details.

To go further

Remember that all examples above are pedagogical, and made to understand how to create structures. For such simple structures, you should use default implementations. For instance, it is more appropriate to use the Python deque class in package collections, which provides the optimal operations for manipulating stacks. An exercice in the pratical activity will illustrate the efficiency gain when appropriate and optimised data structures are used.

To go beyond