Imagine you are at a restaurant with a buffet. As you get to the buffet, you have to grab a plate from a stack of clean plates. Which plate do you take?
Now, imagine you are the dishwasher at this restaurant. As you wash each plate, you place it in the plate stack for customers to use. Where do you put each clean plate?
When you are taking a plate, you usually take the plate from the top of the stack of plates. As the dishwasher, you place each clean plate at the top of the stack of plates as well.
What is a Stack
In computer science, a stack is an abstract data structure that mimics a stack of plates at the buffet. You add new data (for example, a clean plate) to the top of the stack. Similarly, you remove data from the stack (for example, a plate for the buffet) from the top as well.
The behavior of a stack is sometimes called LIFO, which stands for "Last In, First Out". This reflects how the structure works -- the last piece of data added to the stack is the first piece of data removed from it.
Why use a Stack
Stacks allow you to keep track of data in a sequential manner and then retrieve that data in reverse order. For example, if you are solving a maze, you want to backtrack when you hit a dead end. By storing your path in a stack, you can follow it backward to get to another turning point.
Use Cases for a Stack
If you've ever run a program on your computer, you've used a stack. Whenever a program runs, the operating system stores the current state of the system in a stack. When your program ends, the operating system restores that state from the top of the stack.
Stacks are also used within your program. Function calls push data onto a program-specific stack, including parameters and where the function should return. When the function ends, this data is removed from the stack, and your program continues where the function call left it.
Benefits of a Stack
Stacks make certain concepts and algorithms possible.
Recursive functions would be impossible without stacks. If each function call didn't save its own state and return location, then the first return would end the entire set of calls.
Trip routing programs use stacks to find the best route by saving previous route steps on a stack and comparing new steps to them. Without stacks, you would still be finding your own routes with paper maps.
Stack Implementation
Before implementing a stack, you need to learn some terminology:
- The location where data is added to and removed from a stack is called the top of the stack.
- Adding data to a stack is called pushing data onto the stack.
- Removing data from the stack is called popping data off the stack.
- Inspecting the data at the top of the stack without removing it is called peeking.
- A stack with no data in it is said to be empty.
Note that all stack activity happens at the top of the stack -- nothing else in the stack changes.
Stacks are purely abstract types and are built using other data structures. The two most common structures used to implement stacks are linked lists and arrays.
Java Stack Implementation with Linked Lists
A linked list is a great base structure for implementing a stack. The dynamic nature of the list allows the stack to grow as big as necessary.
Assume you already have a LinkedList class that implements .addHead() and .removeHead() methods to add and remove data from the head of the list. Your Stack class might look like this:
// java
public class StackLL<T extends Comparable<T>> {
// Used to store the data in the stack
LinkedList<T> stack;
public StackLL(){
if (this.stack == null)
this.stack = new LinkedList<>();
}
public void push(T data){
this.stack.addHead(data);
}
public T pop(){
return this.stack.removeHead();
}
}
That's it. Since stack operations always work on the top of the stack, you define .push() and .pop() the head of the LinkedList as the top. This means all your operations are $`O(1)`$. Plus, since the linked list already checks for valid head references, you don't need to do that with the stack. However, you may want to add a special case in the .pop() method when the underlying linked list is empty.
Python Stack Implementation with Lists
A Python list is a great base structure for implementing a stack. The dynamic nature of the list allows the stack to grow as big as necessary.
A basic implementation of a Stack class might look like this:
# python
class Stack:
def __init__(self, data=None):
self.__stack = []
if data:
self.__stack.append(data)
def push(self, data):
self.__stack.append(data)
def pop(self):
return self.__stack.pop()
Java Stack Implementation with Arrays
A stack implementation using an array imposes some limits that need to be checked as you work with the stack. Primarily, you need to ensure you don't add more data to the stack than can be stored in the underlying array and that you don't try to remove data from the stack when it's empty.
Here's what a stack implemented using an array might look like:
// java
public class StackArray<T extends Comparable<T>> {
// Used to store the data in the stack
T[] stack;
// Where is the top of the stack?
int top;
// Create a stack with a given size
public StackArray(int size){
this.stack = (T[]) new Comparable[size];
this.top = 0;
}
// Create a stack with a fixed size
public StackArray(){
this.stack = (T[]) new Comparable[10];
this.top = 0;
}
public void push(T data) throws Exception {
if (top < this.stack.length){
this.stack[top++] = data;
} else {
throw new Exception("Stack overflow");
}
}
public T pop() throws Exception {
if (top > 0){
return this.stack[--top];
} else {
throw new Exception("Stack empty");
}
}
}
This implementation is a bit more complicated than the previous example. You need a variable to track where the top of the stack is at all times so you know where each new piece of data will be stored. Since this is an index into the underlying array, you also need to ensure it's valid -- not too big or too small. If the .top value is out of range, then throwing an exception allows this to be handled gracefully.
Uses for Stacks
Stacks are used every time you write and run a program. It's time to take a look at a simple Python "Hello, World" program to see how it works:
# python
print("Hello World")
print("Goodbye")
When the Python interpreter runs this, it calls the first print() function, passing in the string "Hello World" as a parameter. When that print() function ends, it returns to the program, and execution continues at the second line. But how does print() know what gets run next?
Every time a function or method is called, information is pushed onto a stack maintained by the runtime environment. This includes things like the parameters being passed into the function and the next thing to be run after the function ends.
When the first print() function is done, it pops all that data back off the stack, finds the next thing to be run, and jumps to that place to keep running everything.
You'll also use stacks for our own purposes later.
If you'd like to continue learning about Stacks in Java, check out the following resources in the Java 301 course:
- Stacks in Java
- Using Java's built-in Stack class
- Video: Using Java's built-in Stack
- Custom Stack implementation in Java
If you'd like to continue learning about Stacks in Python, check out the following resource in the Python 301 course:
Summary: Java Stack & Python Stack
Stacks allow you to store data in a specific order and then retrieve it in the reverse order. This Last In First Out characteristic makes stacks ideal for use in backtracking algorithms, programming language compilers and interpreters, and implementing recursive code.