Stack Data Structure – Introduction and Implementation

What is Stack??

  • Stack is an abstract data type (ADT) and very useful in programming.
  • In computer science, a stack is an abstract data type that serves as a collection of elements.
  • Majorly all the operations are done at only one end of the stack which is top of the stack.
  • The order in which elements in stack are stored is with LIFO (Last-in-First-Out) manner. Means the element inserted last will be removed first.

See the diagram below for more understanding.

Stack Operations

Operations on Stack and How to Implement:

Java already has a built-in class for Stack. Click here to read about it.

Ways to implement Stack

  1. Implement stack using Array (discussed in this article)
  2. Implement stack using LinkedList

Operations:

Initialize a topIndex = -1;

  • For push() operation- increment topIndex by 1 and add element at this index in array. Time- O(1)
  • For pop() operation- remove element from the topIndex, decrement topIndex by. Time- O(1)
  • For peek() operation- return the element from the topIndex. Time- O(1)
  • For isEmpty() operation- check if topIndex<0 then return true else false. Time- O(1)
  • For getSize() operation- return the topindex+1. Time- O(1)

Java Code:

public class StackUsingArray {
int size;
int topIndex = 1;
int [] stack;
public StackUsingArray(int size){
this.size = size;
stack = new int[size];
}
public void push(int num){
if(topIndex==size1) {
System.out.println("Stack overflow, …cannot insert new element");
return;
}
System.out.println("Inserting " + num + " into Stack.");
topIndex = topIndex + 1;
stack[topIndex] = num;
}
public Integer pop(){
if(topIndex<0) {
System.out.println("Stack is empty, nothing to pop");
return null;
}
System.out.println("Popping from Stack.");
Integer x = stack[topIndex];
topIndex;
return x;
}
public Object peek(){
if(topIndex<0) {
System.out.println("Stack is empty, nothing to pop");
return null;
}
System.out.println("Popping from Stack.");
return stack[topIndex];
}
public boolean isEmpty(){
return (topIndex<0);
}
public int getSize(){
return topIndex+1;
}
public void displayStack(){
System.out.print("Stack (top–>bottom): ");
for (int i = topIndex; i >=0 ; i) {
System.out.print(stack[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int size = 4;
StackUsingArray stack = new StackUsingArray(size);
System.out.println("Is Stack Empty: " + stack.isEmpty());
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.displayStack();
System.out.println("Popped Element: " + stack.pop());
System.out.println("Popped Element: " + stack.pop());
stack.displayStack();
stack.push(6);
System.out.println("Peeking Element: " + stack.peek());
stack.displayStack();
System.out.println("Is Stack Empty: " + stack.isEmpty());
System.out.println("Stack Size: " + stack.getSize());
}
}

view raw
StackUsingArray.java
hosted with ❤ by GitHub


Output:

Is Stack Empty: true
Inserting 1 into Stack.
Inserting 2 into Stack.
Inserting 3 into Stack.
Inserting 4 into Stack.
Stack overflow, ...cannot insert new element
Stack (top-->bottom): 4 3 2 1
Popping from Stack.
Popped Element: 4
Popping from Stack.
Popped Element: 3
Stack (top-->bottom): 2 1
Inserting 6 into Stack.
Popping from Stack.
Peeking Element: 6
Stack (top-->bottom): 6 2 1
Is Stack Empty: false
Stack Size: 3