Introduction

Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it. There are two basic ways to implement stack data structure :

• Array based Implementation
  • Using Array or Static Array (Array size is fixed and has to be given during initialization)
  • Using Dynamic Arrays or Resizable Arrays (Arrays can grow or shrink based on requirement)
• Linked List Based Implementation

In Array (or Static Array) based implementation, an array of fixed size is used to create a stack. Let us discuss the creation/implementation of stack in terms of its operations. Before proceeding with this post, it is highly recommended to understand about arrays and how stack operations are performed.

Prerequisite

• Stack Data Structure
• Array Data Structure

Algorithm

Stack implementation is defined in terms of adding an element which is called Push and deleting an element from the stack which is called Pop.

In an array, elements can be added or deleted at any position but while implementing stack, we have to permit insertions and deletions at top of the stack only. To do this we can use a variable called top which points to the last element in the stack. Initially when the stack is empty, the value of top is initialized to -1. For push operation, first the value of top is increased by -1 and then the new element is pushed at the position of top. For pop operation, first the element at the position of top is popped and then top is decreased by 1.

Below are the points to aware about implementation of stack using arrays

• Fixed Capacity : A stack can hold at max of n elements which is given during initialization of the stack.
• Overflow : Once stack reaches the max capacity, it is not possible to push any new element.
• Underflow: When no elements are left in the stack and we try to pop elements from the stack.

Initialization

1Initialize array stack[] with size n which is used to store stack elements. <br/>
2Initialize an index top with -1. It means no elements left in the stack.

Push Operation

1. If stack is full (If the stack capacity reaches n)
   • throw error
2. Else
   • increment top by 1
   • update stack[top] with new data

1void push(int data) : 
2      if stack is full : 
3           throw error 
4
5      else : 
6        // increment top by 1    
7        top = top+1 
8
9        // put data at top position  
10        stack[top] = data 

1boolean isStackFull() : 
2     // if top index is the last index of the array 
3     // then top = n-1 or top+1 = n 
4     // assumption array index starts with 0 
5     return top+1 == n 

Pop Operation

1. If stack is empty
   
   • throw error
     
2. Else
   
   • remove the element at top index
     
   • update top index to top-1
     

1int pop() :     
2    if stack is empty :  
3      throw error   
4
5    else :   
6       // store data in a temp variable which has be to removed 
7       int data = stack[top]     
8 
9       // decrement top by 1 which means after pop, 
10       // top element points to top-1 
11       top = top-1 
12
13    return data  

1boolean isEmpty() : 
2    // check if index top points -1, 
3    // it means no elements in the stack 
4    return top = -1

Example Explanation

• Initialization :

  • Let us consider max capacity of the stack as 4
  • Initialize top index as -1

  

• Push b1 :

  • Increment top by 1 , it means top now points at index 0
  • store ball b1 at top index which is our top or last element

  

• Push b2 :

  • Increment top by 1 => top = 1
  • Store ball b2 at top position => b2 is the top or last element in the stack

  

• Push b3 :
  • Increment top by 1 => top = 2
  • Store ball b3 at top position => b3 is last element in the stack

1![Stack Operations – Push b3](../assets/images/dsa/StackUsingArray_03PushB3.png)

• Push b4 :

  • Increment top by 1 => top = 3
  • Store ball b4 at top position => b4 is last element in the stack

  

• Push b5 :

  • As stack has reached it max capacity, adding new element will result in overflow

    

• Pop :

  • top element b4 gets removed from the stack

  • top index gets decremented by 1

    

Code Implementation

1public class StackUsingArray {
2
3    private int[] stack;
4    private int top = -1 ;
5    private int capacity;
6
7    // stack can hold at max n elements
8    public StackUsingArray(int n){
9        this.capacity = n;
10        stack = new int[capacity];
11    }
12
13    // method to push data into stack
14    public void push(int data){
15        if(isFull()) {
16            throw new RuntimeException("Stack is already Full");
17        }
18        // as top index always points to last element,
19        // increment top index by 1 and push the data
20        top = top +1 ;
21        stack[top] = data;
22    }
23
24    // method to pop data from stack
25    public int pop() {
26        if(isEmpty()) {
27            throw new RuntimeException("Stack is Empty");
28        }
29        // always pop operation removes top/last
30        // element in the stack
31        // decrement top index by 1
32        int data = stack[top];
33        top = top -1;
34        return data;
35    }
36
37    // method to return top element from the stack
38    public int peek(){
39        if(isEmpty()) {
40            throw new RuntimeException("Stack is Empty");
41        }
42        return stack[top];
43    }
44
45    // method to check overflow condition of the stack
46    public boolean isFull(){
47        return stack.length == top+1 ;
48    }
49
50    // method to check the stack is empty or not
51    public boolean isEmpty(){
52        return top == -1;
53    }
54
55    // method to print stack data in LIFO order
56    public void print() {
57        System.out.print("Elements in Stack >> ");
58        for(int i=0; i<top+1; i++) {
59            System.out.print(stack[i]+ " ");
60        }
61        System.out.println();
62    }
63
64
65    public static void main(String[] args){
66        StackUsingArray obj = new StackUsingArray(4);
67
68        obj.push(20);
69        obj.push(30);
70        obj.push(45);
71        obj.push(50);
72
73        obj.print();
74
75        try{
76            obj.push(80);
77        }catch (Exception e) {
78            System.out.println(e.getMessage());
79        }
80
81        System.out.println("Top Element Is "+obj.peek());
82        System.out.println("POP >> "+obj.pop());
83        System.out.println("Top Element After pop is "+obj.peek());
84        obj.print();
85    }
86
87}