In this article, we are going to understand Stack Data Structures. We will go over the benefits and operations of the data structure. We will dive into their visual representation and at last, we will see how to implement Stack in Java.
1. Stack Data Structure
A stack is a LIFO (last-in-first-out) principle-based linear data structure; it maintains a single pointer “TOP” at the topmost element of the stack. You can think of a pile of books as stack data structure and books can be added or removed from the top of the Stack. Similarly, an element will be added or deleted from the top of the Stack only. We define stack with a capacity and it will store max those many elements.
1.1. Stack Data Structure Basic Operations.
The basic operations of a stack are:
- Push: To add an element at the top of the stack.
- Pull: To remove an element from the top of the stack.
- Peek: To get the top element without removing it.
- IsEmpty: To check if the stack is empty.
- IsFull: To check if the stack is full.
1.2. Stack Visual Representation.
Here is a visual representation of stack data structure for better understanding.
1.3. Stack PUSH Operation.
- Check if stack is full.
- If stack is full, give a message to the user about full stack.
- If not full, add element to the top of stack and increase the stack size.
1.4. Stack POP Operation.
- Check if stack is empty before POP operation.
- If empty, give the underflow error to the user.
- If not empty, pop the top element of the stack and decrease the size of the stack by 1.
2. Stack Implementation in Java
Let’s see how to implement a stack data structure in Java. Stack can be easily implemented using the Array or Linked List data structure. While we choose the data structure for stack implementation, keep in mind the following important points.
- Arrays are quick, but lack the ability of dynamic resizing.
- Linked List is dynamic (no size constraints as Array) but will have time complexity and overhead of managing the links.
package stack;
class MyStack {
private int array[];
private int top;
private int capacity;
MyStack(int size) {
array = new int[size];
capacity = size;
top = -1;
}
/**
*
* @param item
*/
public void push(int item) {
if (isFull()) {
System.out.println("Can't push the element, Stack is full");
return;
}
System.out.println("Inserting: " + item);
array[++top] = item;
}
/**
*
* @return
*/
public int pop() {
if (isEmpty()) {
System.out.println("Can't pop the element, Stack is empty");
return -1;
}
System.out.println("Popping top element:" + array[top]);
return array[top--];
}
/**
* returns the size of stack
* @return
*/
public int size() {
return top + 1;
}
/**
* checks is stack is empty
* @return
*/
public Boolean isEmpty() {
return size() == 0;
}
/**
* checks if stack is full
* @return
*/
public Boolean isFull() {
return size() == capacity;
}
public static void main(String[] args) {
MyStack stack = new MyStack(3);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.push(5);
System.out.println("The stack size is " + stack.size());
stack.pop();
System.out.println("The stack size is " + stack.size());
}
}
Let’s understand some important point on this implementation. The size()
method is used to check if stack is empty or not:
/**
* @return the size of the queue
*/
public int size() {
return top + 1;
}
The isFull()
method tells us if the stack is full or not.
/**
* checks if stack is full
* @return
*/
public Boolean isFull() {
return size() == capacity;
}
If we run our Java program, we will have the following output.
3. Usage of Stack
- A Stack can reverse a String.
- We use a Stack for Tree/Graph Depth-First Search.
- We use a Stack for Recursion.
- A Stack is used for UNDO and REDO operations.
- We use a Stack for solving problems like Backtracking.
- A Stack is used for expression conversion like Infix to Post-fix.
- A Stack is used by Thread by managing their local variables.
4. Time Complexity of Stack
Both push()
and pop()
operation works on the top element of the stack and have time complexity as <strong>O(1)</strong>
.
Summary
In this article, we talked about the stack data structure and its basic operation. We also saw Java implementation for stack and it’s time complexity. The source code for this article and other from our data structure series are available on our GitHub repository.