Introduction to Stack Data Structure in Java
3
Stack is an abstract data type. Stack can be implemented using Linked List or Array. It follows LIFO principle (Last In First Out) and supports push(), pop() and peek() operations.
Stack operations
For this explanation, let’s consider that we implement the stack using LinkedList.
push()
In stack, the push operation will always insert a new item as the top node of the LinkedList. The complexity is O(1) and it is very fast.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Push new item to the top of Stack // O(1) Complexity public void push(T data) { if(root == null) { root = new StackNode<>(); root.setData(data); root.setNextNode(null); } else { StackNode<T> newNode = new StackNode<>(); newNode.setNextNode(root); newNode.setData(data); this.root = newNode; } size++; } |
pop()
The pop operation always removes the item from the top most node of the LinkedList. This operation is also O(1) complexity.
|
1 2 3 4 5 6 7 8 9 10 11 |
// Pop the top most item from Stack // O(1) Complexity public T pop() { if(root == null) { return null; } T data = root.getData(); this.root = this.root.getNextNode(); size--; return data; } |
peek()
The peek operation is same as pop, except that it doesn’t removes the item. The peek returns the value of the top most node which the stack is currently pointing to and the complexity is O(1).
|
1 2 3 4 5 6 7 8 9 |
// Peek the top most item from Stack; This won't reduce the size of the Stack // O(1) Complexity public T peek() { if(root == null) { return null; } T data = root.getData(); return data; } |
Stack Applications
1. Stack is used most importantly in Call Stack
- Stack is used in many programming languages to store information about methods, functions of a computer program.
- The local variables of a function are stored in Stack.
- After the function call returns, the local variables are freed up from the stack memory.
- Stack memory is part of RAM and is limited in size. It is very fast for accessing the value.
2. In Graph algorithms, for example in depth-first search
Stack implementation using LinkedList
First let’s define the Stack Node which have two attributes – data and a reference to next node.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
package com.rayfocus.datastructures.stack; public class StackNode<T> { private T data; private StackNode<T> nextNode; public T getData() { return data; } public StackNode<T> getNextNode() { return nextNode; } public void setData(T data) { this.data = data; } public void setNextNode(StackNode<T> nextNode) { this.nextNode = nextNode; } } |
Then, the implementation of Stack to support push, pop, peek, size and isEmpty operations. All the operations are very fast and is O(1) complexity.
|
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 |
package com.rayfocus.datastructures.stack; public class Stack<T extends Comparable<T>> { private int size; private StackNode<T> root; // Push new item to the top of Stack // O(1) Complexity public void push(T data) { if(root == null) { root = new StackNode<>(); root.setData(data); root.setNextNode(null); } else { StackNode<T> newNode = new StackNode<>(); newNode.setNextNode(root); newNode.setData(data); this.root = newNode; } size++; } // Pop the top most item from Stack // O(1) Complexity public T pop() { if(root == null) { return null; } T data = root.getData(); this.root = this.root.getNextNode(); size--; return data; } // Peek the top most item from Stack; This won't reduce the size of the Stack // O(1) Complexity public T peek() { if(root == null) { return null; } T data = root.getData(); return data; } // Returns the size of the Stack // O(1) Complexity public int size() { return this.size; } // Checks if the Stack is Empty // O(1) Complexity public boolean isEmpty() { return (this.root==null); } } |
Finally, test the Stack implementation.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package com.rayfocus.datastructures.stack; public class StackTest { public static void main(String[] args) { Stack<String> stack = new Stack<>(); stack.push("A"); stack.push("B"); stack.push("C"); System.out.println("Stack size : "+stack.size()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println("Peek at Stack value : "+stack.peek()); System.out.println(stack.pop()); System.out.println("Stack isEmpty? : "+stack.isEmpty()); } } |
Summary
- Stack is an abstract data type and can be implemented using LinkedList or Array in Java.
- It is used in many programming languages to keep information of the active subroutines, function and method calls.
- There is always a trade-off between memory and run-time when choosing a data structure for Stack implementation. So, use LinkedList when memory is not a concern. Otherwise all the operations are very fast.
- Use Array to implement Stack when memory is of important concern. But the operations are not so efficient because we have to resize the Array internally.
