A stack is a linear data structure that works on the principle of LIFO. LIFO stands for Last In First Out. This means that the last elements which is going to get inserted is going to be the first element to get removed. We can imagine a stack as a pile of cloths or a pile of plates. The last item we keep on the pile is the first item we remove from the pile.
Stacks are one of the most useful data structures which are used frequently in computer science. Let us look at the operations that are done on a stack.
- Push: The operation which inserts an element into a stack is called push. It inserts an item at the last.
- Pop: This operation which removes an element from a stack is called pop. It removed an items from the end of the stack.
- Empty? : This operation return a boolean true or false. It return true if the stack is empty else it gives false.
- Full? : This operation as well returns a boolean true or false. It returns true if the stack is full else returns a false.
- Peek: This operation gives out the element at a given position.
Implementation of Stack using Java
We start by creating the main class StackArray and declare three global variables arr[], top with the initial value of -1 and size (here we keep it as 5). This size will define the size of the stack.
public class StackArray {
static int top = -1;
static int size = 5;
static int arr[] = new int[5];
}Push an element in stack
private static void push(int item) {
if(top == size - 1) {
System.out.println("Stack overflow");
} else {
top++;
arr[top] = item;
}
}Here, in the above method we start by checking if the top pointer is equal to that of the size. This will signify that the stack is full and will print Stack Overflow which is condition when a stack is full. If this condition is not met, we increase the top pointer by 1 and insert an element in the stack at the top position.
Pop an element from stack
private static void pop() {
if(top == -1) {
System.out.println("Stack is empty");
} else {
top--;
}
}In the pop method first we check if the top pointer is empty or not. If it is empty we print that the stack is empty. This is known as the Stack Underflow condition. If that is not the case, we simply decrease the top pointer by 1. As a result, the top pointer starts to point in the second last element.
Check if stack is empty or full
We check if the stack is empty or full by checking the value of the top pointer. If the top pointer is equal to -1 i.e it’s starting value we consider the stack to be empty else if the value is equal to the predefined size of stack – 1 (we subtract 1 as index of array starts from 0), we consider it full.
Print the values of a stack
private static void showStack() {
if(top == -1) {
System.out.println("Stack is empty");
} else {
for(int i=top; i>=0; i--) {
System.out.println(arr[i]);
}
}
}The above method prints the elements of the stack. For this we start to loop the array from the top position and go till 0th index. This prints the elements of the stack.
Final Java Program
public class StackArray {
static int top = -1;
static int size = 5;
static int arr[] = new int[5];
public static void main(String[] args) {
System.out.println("Printing Stack");
showStack();
System.out.println("Pushing elements");
push(1);
push(2);
push(3);
push(4);
System.out.println("Printing Stack");
showStack();
System.out.println("Popping elements");
pop();
pop();
System.out.println("Printing Stack");
showStack();
}
private static void pop() {
if(top == -1) {
System.out.println("Stack is empty");
} else {
top--;
}
}
private static void push(int item) {
if(top == size - 1) {
System.out.println("Stack overflow");
} else {
top++;
arr[top] = item;
}
}
private static void showStack() {
if(top == -1) {
System.out.println("Stack is empty");
} else {
for(int i=top; i>=0; i--) {
System.out.println(arr[i]);
}
}
}
}
Output
Printing Stack
Stack is empty
Pushing elements
Printing Stack
4
3
2
1
Popping elements
Printing Stack
2
1
In the above code we introduce the main method to run and execute the stack operation methods. We start the printing the empty stack first, then we push some elements and again print the stack. Again we pop the elements and again print the stack.
Time Complexity of Stack
The time complexity of the stack operations (push and pop) has the complexity of O(1). This is since accessing array elements by index takes constant time. Read more about time complexity and Asymptotic notations here.