Stacks
Reading time15 minIn brief
Article summary
In this article, we present you a data structure called the “stack”. With a stack, elements are removed in the opposite order in which they were added. This is particularly useful in many applications, and is omnipresent in computer science. In particular, calling functions uses a stack.
Below, we also propoe two possible implmentations for a stack, and show that they can be used independendly if the primitives abstract the details.
Main takeaways
-
Stacks are data structures where the first element to be added is the last element to be removed.
-
Depending on 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 method, where the last element added is the first to be removed, 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:
- initialize – Initializes 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.
These primitives manage the stack in the form of “arrays” or “linked lists”.
3 — Implementation of stacks
Let’s have a look as possible implementations. In practice, each programming language offers a proper implementation of a stack. Here, we show possible implementations for pedagogical purpose.
3.1 — Use of arrays
The simplest representation of a stack is an array. If the maximum number of elements contained in the stack is known in advance, it is easy to define the size of the array. Otherwise, you need to define a sufficiently large array, or use a dynamic array.
Each new element in the stack is added to an empty cell in the array. Popping removes this element. An integer variable indicating the number of elements controls the state of the array.
Here is a possible implementation of a stack, using a dynamic size array (list) to store information.
# Needed imports
from typing import Any
from typing_extensions import Self
class Stack:
"""
This is a possible implementation of a stack.
Here, the stack manipulates a list.
Therefore, it is of dynamic size.
"""
def __init__ (self) -> Self:
"""
This is the constructor of the class.
It initializes the stack.
In:
* None.
Out:
* A new stack.
"""
# Initialize data
self.data = []
def __str__ (self) -> str:
"""
This method returns a string representation of the stack.
In:
* None.
Out:
* A string representation of the stack.
"""
# Create string
return str(self.data)
def push (self, item: Any) -> None:
"""
This method adds an element to the stack.
The element is added at the end.
In:
* item: Element to add.
Out:
* None.
"""
# Add element
self.data.append(item)
def pop (self) -> Any:
"""
This method removes the last element of the stack.
The element is removed from the end.
In:
* None.
Out:
* The last element of the stack.
"""
# Remove element
return self.data.pop()
def is_empty (self) -> bool:
"""
This method checks if the stack is empty.
In:
* None.
Out:
* True if the stack is empty, False otherwise.
"""
# Check contents
return len(self.data) == 0
# A few tests
stack = Stack()
stack.push(1)
print(stack)
stack.push(2)
print(stack)
stack.push(3)
print(stack)
element = stack.pop()
print(element, stack)
element = stack.pop()
print(element, stack)
element = stack.pop()
print(element, stack)/**
* To run this code, you need to have Java installed on your computer, then:
* - Create a file named `Stack.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 Stack.java` to compile the code.
* - Run the command `java -ea Stack` to execute the compiled code.
* Note: '-ea' is an option to enable assertions in Java.
*/
// Needed imports
import java.util.ArrayList;
import java.util.List;
/**
* This is a possible implementation of a stack.
* Here, the stack manipulates a dynamically sized ArrayList.
* This class should be put in a file named 'Stack.java'.
*/
public class Stack<T> {
/**
* Here is the attribute we need to define for data.
*/
private List<T> data;
/**
* This is the constructor of the class.
* It initializes the empty stack.
*/
public Stack() {
// Initialize data
this.data = new ArrayList<>();
}
/**
* This method returns a string representation of the stack.
*
* @return A string representation of the stack.
*/
public String toString() {
// Create string
StringBuilder string = new StringBuilder("[");
for (T d : data) {
string.append(d).append(", ");
}
if (!data.isEmpty()) {
string.setLength(string.length() - 2);
}
string.append("]");
return string.toString();
}
/**
* This method adds an element to the stack.
* The element is added at the end.
*
* @param item Element to add.
*/
public void push(T item) {
// Add element
data.add(item);
}
/**
* This method removes the last element of the stack.
*
* @return The last element of the stack.
*/
public T pop() {
// Make sure the stack is not empty
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
// Remove element
return data.remove(data.size() - 1);
}
/**
* This method checks if the stack is empty.
*
* @return True if the stack is empty, False otherwise.
*/
public boolean isEmpty() {
// Check data size
return data.isEmpty();
}
/**
* 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) {
// A few tests
Stack<Integer> stack = new Stack<>();
stack.push(1);
System.out.println(stack);
stack.push(2);
System.out.println(stack);
stack.push(3);
System.out.println(stack);
int element = stack.pop();
System.out.println(element + " " + stack);
element = stack.pop();
System.out.println(element + " " + stack);
element = stack.pop();
System.out.println(element + " " + stack);
}
}3.2 — Use of linked lists
Linked lists are more appropriate when the maximum number of elements to be stored is unknown. They define dynamic stacks that grow as they are filled. Like dynamic arrays, they ensure a good functionality regardless of the number of elements stored, which is not the case with static arrays.
With this organization, the stack becomes a node pointer. Each element is stored in a node which contains a pointer to the next node. The stack corresponds to the head pointer of the linked list. A second pointer indicating the end of the list makes it easier to manage, as it avoids having to systematically traverse the list to add an element at the end. This is known as a doubly linked list (see figure below). The stack and the end-of-list pointer must be accessible and modifiable by all subroutines or methods.
Here is a possible implementation:
# Needed imports
from typing import Any
from typing_extensions import Self
class Node:
"""
This class represents a node in a doubly linked list.
Each node contains data, a reference to the next node, and a reference to the previous node.
"""
def __init__(self, data: Any):
"""
This is the constructor of the class.
It initializes a node with the given data.
In:
* data: Data to store in the node.
Out:
* None.
"""
# Here we initialize the node with the given data
self.data = data
self.next = None
self.prev = None
class Stack:
"""
This is a possible implementation of a stack using a doubly linked list.
The stack can grow dynamically as elements are added.
"""
def __init__ (self) -> Self:
"""
This is the constructor of the class.
It initializes an empty stack using a doubly linked list.
In:
* None.
Out:
* A new stack.
"""
# Here we initialize the stack with no elements
self.top = None
self.nb_elements = 0
def __str__ (self) -> str:
"""
This method returns a string representation of the stack.
In:
* None.
Out:
* A string representation of the stack.
"""
# Create string
string = "["
current = self.top
while current:
string += str(current.data) + ", "
current = current.prev
if self.nb_elements > 0:
string = string[:-2]
string += "]"
return string
def push (self, item: Any) -> None:
"""
This method adds an element to the stack.
The element is added at the top, and the counter is incremented.
In:
* item: Element to add.
Out:
* None.
"""
# Create a new node with the item
new_node = Node(item)
# Link the new node with the current top node
new_node.prev = self.top
# Set the new node as the top node
if self.top:
self.top.next = new_node
self.top = new_node
# Increment the number of elements
self.nb_elements += 1
def pop (self) -> Any:
"""
This method removes the last element of the stack.
The element is removed and the counter is decremented.
In:
* None.
Out:
* The last element of the stack.
"""
# Make sure the stack is not empty
assert not self.is_empty()
# Remove the top element
element = self.top.data
self.top = self.top.prev
if self.top:
self.top.next = None
# Decrement the number of elements
self.nb_elements -= 1
return element
def is_empty(self) -> bool:
"""
This method checks if the stack is empty.
In:
* None.
Out:
* True if the stack is empty, False otherwise.
"""
# Check if the stack is empty
return self.nb_elements == 0
# A few tests
stack = Stack()
stack.push(1)
print(stack)
stack.push(2)
print(stack)
stack.push(3)
print(stack)
element = stack.pop()
print(element, stack)
element = stack.pop()
print(element, stack)
element = stack.pop()
print(element, stack)/**
* To run this code, you need to have Java installed on your computer, then:
* - Create a file named `Stack.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 Stack.java` to compile the code.
* - Run the command `java -ea Stack` to execute the compiled code.
* Note: '-ea' is an option to enable assertions in Java.
*/
/**
* This class represents a node in a doubly linked list.
* Each node contains data, a reference to the next node, and a reference to the previous node.
* This class should be put in a file named 'Node.java'.
*/
class Node<T> {
/**
* Here are the attributes we need to define for data and the number of elements.
*/
T data;
Node<T> next;
Node<T> prev;
/**
* This is the constructor of the class.
* It initializes a node with the given data.
*
* @param data Data to store in the node.
*/
public Node(T data) {
// Here we initialize the node with the given data
this.data = data;
this.next = null;
this.prev = null;
}
}
/**
* This is a possible implementation of a stack using a doubly linked list.
* The stack can grow dynamically as elements are added.
* This class should be put in a file named 'Stack.java'.
*/
public class Stack<T> {
/**
* Here are the attributes we need to define for data and the number of elements.
*/
private Node<T> top;
private int nbElements;
/**
* This is the constructor of the class.
* It initializes an empty stack using a doubly linked list.
*/
public Stack() {
// Here we initialize the stack with no elements
this.top = null;
this.nbElements = 0;
}
/**
* This method returns a string representation of the stack.
*
* @return A string representation of the stack.
*/
public String toString() {
StringBuilder string = new StringBuilder("[");
Node<T> current = top;
while (current != null) {
string.append(current.data).append(", ");
current = current.prev;
}
if (nbElements > 0) {
string.setLength(string.length() - 2);
}
string.append("]");
return string.toString();
}
/**
* This method adds an element to the stack.
* The element is added at the top, and the counter is incremented.
*
* @param item Element to add.
*/
public void push(T item) {
// Create a new node with the item
Node<T> newNode = new Node<>(item);
// Link the new node with the current top node
newNode.prev = top;
// Set the new node as the top node
if (top != null) {
top.next = newNode;
}
top = newNode;
// Increment the number of elements
nbElements++;
}
/**
* This method removes the last element of the stack.
* The element is removed and the counter is decremented.
*
* @return The last element of the stack.
*/
public T pop() {
// Make sure the stack is not empty
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
// Remove the top element
T element = top.data;
top = top.prev;
if (top != null) {
top.next = null;
}
// Decrement the number of elements
nbElements--;
return element;
}
/**
* This method checks if the stack is empty.
*
* @return True if the stack is empty, False otherwise.
*/
public boolean isEmpty() {
// Check if the stack is empty
return nbElements == 0;
}
/**
* 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) {
// A few tests
Stack<Integer> stack = new Stack<>();
stack.push(1);
System.out.println(stack);
stack.push(2);
System.out.println(stack);
stack.push(3);
System.out.println(stack);
int element = stack.pop();
System.out.println(element + " " + stack);
element = stack.pop();
System.out.println(element + " " + stack);
element = stack.pop();
System.out.println(element + " " + stack);
}
}4 — A practical use
The following python program reverses a chain of characters. The algorithm stores character by character and then removes them until the stack is empty.
# Initialize
s = Stack()
# Fill stack
sentence = input("Enter a sentence:")
for c in sentence :
s.push(c)
# Pop stack to reverse sentence
reversed_sentence = ""
while not s.is_empty():
reversed_sentence += s.pop()
print("Reversed sentence:", reversed_sentence)/**
* 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) {
// Initialize the stack
Stack<Character> s = new Stack<>();
// Read input from user
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a sentence: ");
String sentence = scanner.nextLine();
// Fill the stack with characters from the sentence
for (char 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());
}
}Note that the program may use one implementation of the stack or the other, as the primitives hide the implementation details.
To go further
The content of this section is optional. It contains additional material for you to consolidate your understanding of the current topic.
To go beyond
The content of this section is very optional. We suggest you directions to explore if you wish to go deeper in the current topic.
- name.
Short description.