The Stack data structure implementation is studied in most Computer Science courses on Data Structure and Algorithms. In this post, you will learn one implementation of this important data structure.
Table of Contents
- What is a Stack?
- Stack operations
- Stack data structure implementation using linked lists
- Example of usage of the Stack data structure
- Summary
What is a Stack?
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last object going into the stack is the first one going out of the stack.
Because of this principle, the operations on a stack are limited. So, however you use a Stack data structure, the LIFO principle is enforced through its operations.
Stack operations
A stack data structure has only 4 operations. Some programming languages have implementations with more operations. However, if you use them, you probably are violating the LIFO principle.
The operations are the following:
- push: add an element to the stack. There is no need to specify the position of the new element because it will be added to the top of the stack.
- pop: removes an element from the stack. There is no need to specify what element you want to remove. This operation will always remove the element at the top of the stack.
- top: this operation will return the element at the top of the stack.
- isEmpty: returns true if the stack is empty, otherwise, it returns false.
You need only the operations above to use the Stack data structure to solve problems. Extra operations like size, or get an element at a certain position, usually don’t make sense in this data structure.
To implement the Stack data structure, we can use arrays or linked lists.
I won’t show here the implementation with arrays because it has a fixed number of elements.
Stack data structure implementation using linked lists
When you study data structures, the first data structure you implement is the list data structure.
A list can be implemented using arrays or linked lists.
Here we are going to use the Java linked list implementation.
public class Stack <T> {
LinkedList<T> info;
Stack(){
info = new LinkedList<>();
}
public void push (T elem){
info.add(elem);
}
public T pop(){
return info.removeLast();
}
public T top(){
return info.getLast();
}
public boolean isEmpty(){
return info.isEmpty();
}
}
In this case, we are reusing the operations implemented in a linked list. Doing that, we are following one of the principles of Object-Oriented Programming: reusability. You can read more about OOP principles in this post.
Anytime you want to use the Stack data structure to solve a certain problem, you can do it by using only the four methods implemented above. Let’s see an example.
Example of usage of the Stack data structure
The usual way to use the Stack data structure is by using a while loop and the operation isEmpty.
Search operations are not common in a stack, but you can implement them using an auxiliary stack as in the example below.
class StackUsageExample{
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("John");
stack.push("Jane");
stack.push("Jude");
stack.push("Josh");
//Print all the elements in the stack and
//the stack must keep its initial state
Stack<String> aux = new Stack<>();
String elem;
while (!stack.isEmpty()){
elem = stack.pop();
System.out.println(elem);
// Add the element to an auxiliary queue
aux.push(elem);
}
// Put back the elements into the original queue
// using the auxiliary queue
while (!aux.isEmpty()){
stack.push(aux.pop());
}
}
}
You can see another example of the Stack data structure usage in this post.
If you execute the code above, you will get the following result.
As you can see, the names are in the inverse order that we add them. This effect is caused by the LIFO principle. It is one of the many ways we can use the stack data structure implementation: to invert a collection of elements.
Summary
You can use the Stack data structure to model situations that follow the LIFO principle.
To solve problems using stacks you only need four operations: push, pop, top and isEmpty.
H@ppy coding!
Related posts:
