Last Updated on January 9, 2023 by Prepbytes
In this article, we will write a Stack program in Java. We will learn about the stack class in Java, how to create a stack, different methods of a stack in Java, and how to iterate over a stack in Java. So, let’s get started.
What is Stack Data structure?
The Stack data structure is a linear data structure based on the FILO (First in Last out) or LIFO (Last in First out) principle. The word stack can be easily imagined as a pile of objects, one above the another. For instance, in a stack of books, the book kept at the top was the last element to enter the stack and if we want to empty the stack by removing the elements one by one, the book at the top of the stack will be the first element we will choose to remove from the stack as it is the most convenient one to be removed.
So, a “stack” of real-world objects in general also follows the Last in First out (LIFO) principle. A stack data structure is shown below.
So, the above image shows an empty stack.
Push Operation in Stack:
To put an element inside a stack is generally referred to as a push operation. For instance, when we push 10 in the stack, the stack will now contain 10.
So, let us push some more elements in the stack as shown below.
So, we can see that the element that is pushed last into the stack is at the top of the stack. This is the general behavior of the stack data structure.
Pop Operation in Stack:
Now, let us try to remove some elements from the stack. Removing an element from the stack is referred to as a pop operation.
So, we can see that when we pop from the stack, the topmost element of the stack gets removed. The stack after popping once is shown below.
So, 40 is now the top of the stack. If we pop once again, then 40 will be removed from the stack as shown below.
So, this is what stack data structure is and the push and pop are the 2 main operations on a stack.
Peek Operation in Stack
Let us also understand the third very main operation called the top or peek of the stack. The top or peek simply means giving the topmost element of the stack. For instance, the top/peek of the stack is shown below for different stacks.
So, at any moment, the element that is the topmost element of the stack is called the peek of the stack.
Let us now also understand the working of push, pop, and top operations in a stack.
Stack Program in Java – Working of Push, Pop, and Peek Operations
So, we have studied and understood the different operations of a Stack data structure. However, let us now understand how these operations work. Consider an empty stack shown below.
A stack data structure can be created using an array or a list when it comes to its implementation. An empty stack is a stack whose top = -1. Since the top pointer points to the topmost element of the stack and -1 is an invalid index, we can say that the stack is empty.
What happens when we push an element into the stack? This is shown below.
So, when we push an element into the stack, the top pointer first increments its value and brings it to the position where the upcoming element (i.e. upcoming top) would be inserted.Then, at that position in the array or the list, we insert the element. This is shown both diagramatically and with the help of pseudo-code in the image above.
Now, let us learn how the pop operation works. Consider the stack filled with some values as shown below.
Now, let us pop an element from this stack.
So, the image above shows what happens when we pop an element from the stack both diagrammatically and by pseudo-code. The element at which the top pointer is pointing is first removed from the underlying array or list and then the value of the top pointer is decremented.
What happens when we perform the operation peek()? Well, we simply return the element at the top i.e. we return the element to which the top pointer is pointing.
Now, just one more question left. We have seen what happens when the stack is empty. However, is a stack ever full? What happens if a stack is full?
So, if we implement a stack using an array, we know when it will be full i.e. when top = array.length as the array has a fixed size i.e. we are restricting the number of elements that can be pushed into the stack.
However, if we are using a list to implement a stack, we can’t say when it will be full. We can just say that if the memory limit exceeds, the stack will be full.
Now that we have understood all the operations of a stack, let us create our own stack class and write a stack program in Java.
Stack Program in Java – Implementing our own Stack
class MyStack {
private int arr[];
private int top;
private int capacity;
// Creating a stack
MyStack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
public void push(int x) {
if (isFull()) {
System.out.println("Stack OverFlow");
System.exit(1);
}
System.out.println("Inserting " + x);
arr[++top] = x;
}
public int pop() {
if (isEmpty()) {
System.out.println("STACK EMPTY");
System.exit(1);
}
return arr[top--];
}
public int getSize() {
return top + 1;
}
public Boolean isEmpty() {
return top == -1;
}
public Boolean isFull() {
return top == capacity - 1;
}
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.print(arr[i] + ", ");
}
}
}
public class Main {
public static void main(String[] args) {
MyStack stack = new MyStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.print("Stack: ");
stack.printStack();
stack.pop();
System.out.println("\nAfter popping out");
stack.printStack();
}
} Time and Space Complexities
Push: The time complexity of push is O(1) as we are just adding an element to the end of the array/list. The auxiliary space is also O(1) as we are using any extra space.
Pop: The time complexity of pop is also O(1) as we are just removing the last element from the array/list. The auxiliary space is also O(1) as we are not using any extra space.
Peek(): The time complexity of peek is also O(1) as we are just getting the last element from the array/list. The auxiliary space is also O(1) as we are not using any extra space.
So, we have seen how to create our own stack class in Java. However, every time we need a stack, we need not do this because Java provides us with its own Stack class that we can use. So, let’s have a look at the Stack class provided by Java.
Stack Class in Java
Stack class is a part of the Java Collections Framework. It extends the Vector class and implements List, Collection, Iterable, Serializable, and Cloneable interfaces. It is a part of java.util package. Just like we create our own stack, we have predefined methods in the Stack class to push, pop, peek an element from the stack and methods to check whether the stack is empty or not, to iterate the stack, etc. The Stack program in Java using the Java Stack class is shown below.
Stack Program in Java – Using Java’s Stack Class
import java.util.*;
public class Main {
public static void main(String[] args) {
Stack<Integer> stk = new Stack<>();
System.out.println("Pushing some elements in the stack");
//pushing an element into the stack -> push()
stk.push(10);
stk.push(20);
stk.push(30);
stk.push(40);
stk.push(50);
//display the stack
System.out.println("Stack: " + stk);
//pop() -> removes the element
int x = stk.pop();
System.out.println(x);
//top of the stack -> peek()
System.out.println("The element at the top of the stack is: " + stk.peek());
//size of the stack -> number of elements
System.out.println("Number of elements in the stack: " + stk.size());
//empty() -> return true if the stack is empty, false otherwise
System.out.println("Is the stack empty: " + stk.empty());
//Iterating the stack using iterator
Iterator it = stk.iterator();
while(it.hasNext()) {
Object value = it.next();
System.out.println(value);
}
}
} Explanation: We have created an Integer stack in Java. We can create other stacks also like Character stack, String stack, etc. The push() function is used to push the element passed as a parameter inside the stack. The pop method removes the topmost element from the stack and also returns its value. The peek() method just returns the topmost value of the stack. The size() methods returns the number of elements in the stack. The empty() method returns a boolean value. It returns true if the stack is empty and false otherwise. Finally, we have created an iterator and have traversed the stack using it.
So, this is how we can write a stack program in Java using the Java’s stack class i.e. Java’s inbuilt stack. We hope that you liked the discussion and have understood the concepts taught in this article. We hope to see you again soon at PrepBytes.
Other Java Programs
Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java
Binary Search Program in Java
Linear Search Program in Java
Menu Driven Program in Java
Package Program in Java
Leap Year Program in Java
Array Programs in Java
Linked List Program in Java
String Programs in Java
Star Program in Java
Number Pattern Program in Java
For Loop Program In Java
Pattern Program in Java
String Palindrome Program in Java
Thread Program in JAVA
Java Scanner Program
While Loop Program in Java
Bubble Sort Program in Java
Fibonacci Series Program in Java
Calculator Program in Java
Fizzbuzz Program in Java
Matrix Program in Java