The Stack data structure has many applications in programming. In this post, you will learn what are the Stack operations and how to use them to solve real-life problems.
Table of Contents
Stacks in the real world
Programming is about modelling real-life situations. The use of stacks is not the exception.
The Tower of Hanoi is a game “consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:
- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No disk may be placed on top of a disk that is smaller than it.
“. Source Wikipedia.
The rules of the game, states that you can only move one disk at a time, and it must be the disc on top of any of three rods.
That behaviour, of removing only the element at the top each time, and adding a new element only to the top, is known as a stack in Computer Science. Also known as the Last In, First Out (LIFO) principle.
Notice that if you remove more than a disc at a time (something you can do) while playing the game, you will be breaking the rules.
Let’s now see the basic operations of the Stack Abstract Data Type (ADT).
The Stack Abstract Data Type
Find below the basic operations of the Stack ADT and an explanation.
- Push: adds an element to the top of the stack
- Pop: retrieve and removes the element at the top
- Top: retrieve the element at the top without removing it
- isEmpty: return true if the stack is empty, otherwise it returns false.
In different programming languages, you can find extra operations and different names for the operations above. But you will always find an operation that will do the action of each of the four operations mentioned above.
Stack data structure examples
One example is to find the solution to the Tower of Hanoi problem given the number of disks. However, this solution is difficult to understand at a beginner level. So, I’ll show you examples that are easier to understand, so later you can solve the Tower of Hanoi problem on your own.
Problem 1: Invert an array of integers
Let’s create a program that takes an array as input and print the inverted array.
We can use a stack to solve the previous problem. Notice that in a stack, the last in is the first out. So, if we add all the array elements to a stack, when we take them out, they will be in reverse order.
Let’s see the implementation.
public static int [] invertArrray(int arr[]){
Stack<Integer> stack = new Stack<>();
for (int i=0; i<arr.length; i++){
stack.push(arr[i]);
}
int index = 0;
while(!stack.isEmpty()){
arr[index] = stack.pop();
index++;
}
return arr;
}All we did in the previous code was to add the elements of the array to the stack and remove the elements from stacks and add them to the array. That’s it! now the array is inverted.
When working with stacks, we use a while loop to go through all the elements in a similar to the example of the Queue data structure. In this case, we don’t need an additional stack because we are storing the elements in the array.
You can also add a method to print an array so you can test the code below. Such a method can be like this:
public static void printArray(int arr[]){
System.out.println();
for (int i=0; i<arr.length; i++)
System.out.print(arr[i] + ", ");
}
You are just printing all the elements in the array to confirm if the array is inverted or not.
The main method of the console application can look like this:
public static void main(String[] args) {
int array[] = {1,2,3,4,5,6,7};
printArray(array);
//Invert the array
array = invertArrray(array);
// Print the inverted array.
printArray(array);
}
Summary
The Stack data structure follows the LIFO principle. It means that the last element to go in the stack is the first one to go out.
Many problems can be solved using stacks. However, in all cases, you won’t see the word stack as part of the problem description. Like you saw in the example of inverting an array.
The key to know when to use stacks is to think about the process you can follow to give the solution to the problem. If it follows the LIFO principle, then you can use stacks.
Some programming languages implement extra operations in the Stack data structure. As a word of caution, if you have to use more operations than the basic ones, you should evaluate if stacks are the right data structure to use in the solution to that particular problem.
H@ppy coding!
Recommended reading: