The post shows you all about the stack data structure in Java. The stack is a classic data structure in programming. It’s really powerful and is implemented widely in many cases. Let’s learn and grow together.
Stack Data Structure in Java
Stack Data Structure Specification
In programming terms, putting an item on top of the stack which is called “push” and removing an item is called “pop”. A stack is an object or an abstract data structure(ADT) that allows the following operations:
- Push: Add an element to the top of a stack
- Pop: Remove an element from the top of a stack
- IsEmpty: Check if a stack is empty
- IsFull: Check if a stack is full
- Peek: Get the value of the top element without removing it
It follows the Last In First Out(LIFO) principle that means the element stored last then it was removed first, see the below image.
How a stack data structure works
Mainly the following three basic operations are performed in the stack:
- A pointer called TOP is used to keep track of the top element in the stack. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing
TOP == -1. - On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP. Before pushing again, we check if stack is already full
- On popping an element, we return the element pointed to by TOP and reduce its value. Before popping again, we check if stack is already empty
Time Complexities of operations on stack
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.
Applications of stack
To reverse a word: Put all the letters in a stack and pop them out. Because of LIFO order of stack, you will get the letters in reverse order.
In compilers: Compilers use a stack to calculate the value of expressions like 1+3/5*(6-9) by converting the expression to prefix or postfix form.
Redo-undo: features at many places like editors, photoshop. Forward and backward feature in web browsers.
In Graph Algorithms: like Topological Sorting and Strongly Connected Components
Implementing Stack Data Structure in Java
a) Implementing Stack using Arrays.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class StackDS { static final int MAX = 3000; int top; int a[] = new int[MAX]; // Maximum size of Stack boolean isEmpty() { return (top < 0); } StackDS() { top = -1; } boolean push(int x) { if (top >= (MAX - 1)) { System.out.println("Stack is already full or overflow"); return false; } else { a[++top] = x; System.out.println(x + " pushed into stack"); return true; } } int pop() { if (top < 0) { System.out.println("Stack Underflow"); return 0; } else { int x = a[top--]; return x; } } int peek() { if (top < 0) { System.out.println("Stack is already empty or underflow"); return 0; } else { int x = a[top]; return x; } } } // How stack running class Main { public static void main(String args[]) { StackDS s = new StackDS(); s.push(5); s.push(10); s.push(20); System.out.println(s.pop() + " Popped from stack"); } } |
Here is the output of the stack program.
Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.
b) Implementing Stack using LinkedList.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
public class StackAsLinkedList { StackElement top; static class StackElement { int data; StackElement next; StackElement(int data) { this.data = data; } } public boolean isEmpty() { if (top == null) { return true; } else return false; } public void push(int data) { StackElement newElement = new StackElement(data); if (top == null) { top = newElement; } else { StackElement temp = top; top = newElement; newElement.next = temp; } System.out.println(data + " pushed to stack"); } public int pop() { int popped = Integer.MIN_VALUE; if (top == null) { System.out.println("Stack is Empty"); } else { popped = top.data; top = top.next; } return popped; } public int peek() { if (top == null) { System.out.println("Stack is empty"); return Integer.MIN_VALUE; } else { return top.data; } } public static void main(String[] args) { StackAsLinkedList stack = new StackAsLinkedList(); stack.push(5); stack.push(10); stack.push(20); System.out.println(stack.pop() + " popped from stack"); } } |
Here is the output of the stack program.
Pros: The linked list implementation of a stack can grow and shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.
That’s all about the Stack data structure in Java.
References
Stack data structure in Java
Data Structures and Algorithms Tutorial in Java
