The post explains two important implementations of Java Stack data structure using array and linked list with examples. It also discusses the advantages & disadvantages of one implementation over the other and the time complexity of each implementation.
Prerequisites:
Knowledge of Java, data structures, stack data structure and the operations performed on it. Basic knowledge of linked list and its working, understanding of time and space complexity is required.
Refer https://hetalrachh.home.blog/2020/01/04/java-util-stack-common-operations/ to understand about stack data structure and the common operations that can be performed on it.
Array based implementation:
In array based implementation, elements of the stack are stored in an array. A top variable is maintained which stores the index of the topmost element of the stack i.e. the index of the last element stored in the stack. push(), pop(), peek() operations are performed at the top end of the stack.
Stack class consist of:
- A constant variable MAX_SIZE = 5 which indicates the maximum number of elements that can be stored in the stack.
- An integer array with size as MAX_SIZE.
- Two variables top and SIZE, where top points to the topmost element of the array and SIZE indicates the number of elements present in the array.
- A no-argument constructor which initializes top = -1 and SIZE = 0 indicating no elements are present in the array initially.
- boolean push(int element) method which first checks if the stack is full, if yes then it returns false and does not insert any element into the stack. If the stack is not full then it increments top by 1, adds the element to the stack array,increases the size of the stack array by 1 and returns true.
- int pop() method which first checks if the stack is empty, if yes then it returns -1 and does not pop any element from the stack. If the stack is not empty, then retrieves the topmost element of the stack, decrements top pointer by 1, decreases the size of the stack by 1 and returns the element which is popped.
- int peek() method first checks if the stack is empty, if yes then returns -1 indicating that peek operation cannot be performed. If the stack is not empty then it returns the topmost element of the stack.
- boolean isEmpty() method checks if the SIZE of the stack is 0, if yes it returns true. Else this method returns false.
- boolean isFull() method checks if the SIZE of the stack equals MAX_SIZE, if yes then it returns true. Else this method returns false.
- int getSize() is a getter method which returns the current SIZE of the stack.
MainClass consist of :
Creating an instance of the Stack class and calling stack methods using that instance.
Example code:
public class StackUsingArray {
public static void main(String[] args) {
Stack s = new Stack();
s.pop();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(6);
s.getSize();
s.pop();
s.peek();
}
}
class Stack {
// maximum size of stack array
final int MAX_SIZE = 5;
// array to store elements
int[] stackArray = new int[MAX_SIZE];
// top of stack and current size of the stack
int top, SIZE;
// initialize top and current size of stack
Stack() {
top = -1;
SIZE = 0;
}
// method to push a new element to the stack
boolean push(int element) {
if (isFull()) {
System.out.println("Stack is full. Cannot insert new element " + element + " to the stack");
return false;
} else {
stackArray[++top] = element;
SIZE = SIZE + 1;
System.out.println("Element pushed to the stack = " + stackArray[top]);
return true;
}
}
// method to pop the top element from the stack
int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot pop element from the stack.");
return -1;
} else {
int elementPopped = stackArray[top--];
SIZE = SIZE - 1;
System.out.println("Element popped from the stack = " + elementPopped);
return elementPopped;
}
}
// method to peek/view the topmost element of the stack
int peek() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot peek element from the stack");
return -1;
} else {
System.out.println("Top most element of the stack = " + stackArray[top]);
return stackArray[top];
}
}
// method to check if the stack is empty
boolean isEmpty() {
if (SIZE == 0) {
return true;
} else {
return false;
}
}
// method to check if the stack is full
boolean isFull() {
if (SIZE == MAX_SIZE) {
return true;
} else {
return false;
}
}
// method to get the current size of stack
int getSize() {
System.out.println("Current size of stack is = " + SIZE);
return SIZE;
}
}
Output of above code:
Stack is empty. Cannot pop element from the stack.
Element pushed to the stack = 1
Element pushed to the stack = 2
Element pushed to the stack = 3
Element pushed to the stack = 4
Element pushed to the stack = 5
Stack is full. Cannot insert new element 6 to the stack
Current size of stack is = 5
Element popped from the stack = 5
Top most element of the stack = 4
Time and space complexities of stack implementation using array :
All operations push(), pop(), peek(), isEmpty(), isFull(), getSize() require constant time. We do not iterate over the array elements for performing any of these operations. Hence the time complexity is O(1). Space complexity = O(N), where N = number of elements.
Advantages of stack using array :
Arrays are more efficient in terms of time and memory as it does not involve using pointers like in case of linked list. Hence no work is associated in creating new memory space when the size of stack increases and garbage collecting it when the size of the stack decreases.
Disadvantages of stack using array :
Size of the stack is not dynamic. It cannot change during runtime.
Linkedlist based implementation :
In linked list based stack implementation , the elements are stored in a linked list as nodes. A root node i.e. top node is used to keep the track of the topmost element of the list. push(), pop(), peek() operations are performed at the top end of the list.
StackUsingLinkedList class consist of :
- A static StackNode class representing a node in the linked list, which has an int data variable representing the integer data stored in the node and a StackNode next which is the pointer to the next node in the list.
- A StackNode top which points to the first/topmost node of the list.
- A no-argument constructor which initializes top=null.
- A constructor in StackNode class which accepts the int value to be pushed and initializes the node data part with it. Also it initializes the next pointer to null.
- void push(int data) method which creates a new StackNode using data. It then checks if top pointer is null, which means the list is empty. If it is empty, then it points top to the new node that is created. If the list is not empty, then it points newNode.next pointer to the the node where the top currently points i.e. the already existing first node of the list. And then points the top node to the newly created node.
- int pop() method which first checks if the list is empty by checking if the top pointer is null. If yes, then it returns -1 and does not remove any element from the list. If the list is not empty, then it retrieves the element data from the first node of the list i.e. top node and points top to the second node of the list represented by top.next and returns the popped element.
- int peek() method which first checks if the list is empty by checking if the top pointer is null. If yes, it returns -1 indicating the list is empty. If the list is not empty it returns the data element of the node at which top points to.
- boolean isEmpty() method which returns true if the list is empty by checking the condition top pointer is null, else it returns false.
- void viewList() method prints the data present in the list. It runs a pointer starting from the top node to the last node, while pointer is not null and prints the list data.
Example code:
public class StackUsingLinkedList {
// top node which points to the topmost/first node of the linked list
StackNode top;
// constructor initializing top to null
StackUsingLinkedList() {
this.top = null;
}
// class which represents a node in the linked list
static class StackNode {
// data stored in the node
int data;
// pointer to the next node
StackNode next;
// constructor initializing data and next pointer
StackNode(int val) {
this.data = val;
next = null;
}
}
// method to push a new element to the stack
void push(int data) {
StackNode newNode = new StackNode(data);
if (top == null) {
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
System.out.println("Element pushed to the stack = " + newNode.data);
}
// method to pop the topmost element of the stack
int pop() {
if (top == null) {
System.out.println("Stack is empty. Cannot pop element from empty stack.");
return -1;
} else {
int elementPopped = top.data;
top = top.next;
System.out.println("Element popped from the stack = " + elementPopped);
return elementPopped;
}
}
// method to peek/view the topmost element of the stack
int peek() {
if (top == null) {
System.out.println("Stack is empty. Cannot peek element from empty stack.");
return -1;
} else {
int elementPeeked = top.data;
System.out.println("Element peeked from the stack = " + elementPeeked);
return elementPeeked;
}
}
// method to check if the stack is empty
boolean isEmpty() {
if (top == null) {
return true;
} else {
return false;
}
}
// method to view the list data
void viewList() {
StackNode pointer = top;
System.out.print("List data = ");
while (pointer != null) {
System.out.print(pointer.data + " ");
pointer = pointer.next;
}
System.out.println("");
}
public static void main(String[] args) {
StackUsingLinkedList s = new StackUsingLinkedList();
s.push(5);
s.push(6);
s.push(7);
s.viewList();
s.pop();
s.peek();
s.pop();
s.pop();
s.pop();
s.peek();
}
}
Output of above code :
Element pushed to the stack = 5
Element pushed to the stack = 6
Element pushed to the stack = 7
List data = 7 6 5
Element popped from the stack = 7
Element peeked from the stack = 6
Element popped from the stack = 6
Element popped from the stack = 5
Stack is empty. Cannot pop element from empty stack.
Stack is empty. Cannot peek element from empty stack.
Time complexities of stack implementation using linked list :
All operations push(), pop(), peek() and isEmpty() has constant time complexity as they are performed at the top end of the list which require constant time to push, pop, peek element to/from the list. We do not iterate over the elements of the list to perform the operations hence the time complexity is O(1). Space complexity = O(N), where N is number of elements in the list.
Advantages of stack using linked list :
Size of the list is dynamic and it can change at runtime. Hence stack implemented using linked list can store any number of elements.
Disadvantages of stack using linked list :
Extra memory space is required to store the top pointer. Popping the elements from the list requires garbage collection to be done by the JVM to free the memory of unused nodes.
Here is the link to above code on my github profile, Stack using array and Stack using Linked List.
Please share your feedback on below comments section, also you can post your queries. Happy learning..!!
Data structures and algorithms in Java 