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 this post let us discuss the creation/implementation of stack using dynamic array 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
• Dynamic Arrays 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. 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.

Advantages of Dynamic Array over Static Array

In static array or array based implementation an array of fixed size is used to create a stack where as in dynamic array based implementation, an array of predefined initial capacity is used to create a stack and if the array has reached its max capacity, a new array of double the current capacity is created and the values from old array will be copied to new array and the new array will be considered as our stack.

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

• Capacity :

  • An array of initial capacity is defined and once the array reaches max capacity, arrays grow double the current size.
  • For simplicity the stack array can be initialized with 1 as the current capacity.

• No Overflow :

  • There is no chance of overflow as whenever the array reaches its capacity, the array gets resized to double to the current capacity.

• Waste of Space :

  • Once the stack size grows reasonably high in size and frequent pop operations make waste of space.
  • To avoid waste of space, the array size can be reduced to 1/4 of its current capacity.

• Underflow:

  • When no elements are left in the stack.

• Initialization :

  • Initialize array stack[] with size 1 which is the current capacity of the stack.
  • Initialize an index top with -1. It means no elements left in the stack.

Push Operation

1. If stack is full (If the stack has reaches its maximum capacity)
   • resize the array
2. Else
   • increment top by 1
   • update stack[top] with given data

1void push(int data) : 
2  if stack is full : 
3    // resize the stack with double the current capacity   
4    resize(2*stack.length) 
5
6  // increment top by 1 
7  top = top+1 
8
9  // store new data at top position 
10  stack[top] = data 

1boolean isStackFull() : 
2     // checking if top pointing to last element in the array  
3     return top+1 == n 

1void resize(len) :  
2     // create new array newStack with size len 
3     newStack = int[len] 
4
5     for i=0 to stack.length :   
6        // copy data from old stack to newStack 
7        newStack[i] = stack[i]  
8 
9     // re-assign stack to point to newStack 
10     // which has double the capacity now. 
11     stack = newStack 
12 

Example Explanation

To understand push and pop operations clearly, let us perform below operations. Let us consider we have few balls and we want to place them or delete them on request basis in a container (stack).

• Initialization :

  • Define Initial capacity of the stack as 1.
  • 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 :

  • As stack array reaches its capacity, size gets doubled (from 1 to 2)
  • Increment top by 1 => top = 1
  • Store ball b2 at top position => b2 is the top or last element in the stack

  

• Push b3 :

  • As stack array reaches its capacity, size gets doubled (from 2 to 4)
  • Increment top by 1 => top = 2
  • Store ball b3 at top position => b3 is last element in the stack

  

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

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

• Push b5 :

  • As stack array reaches its capacity, size gets doubled (from 4 to 8)
  • Store ball b5 at top index => b5 is the last element in the stack.

  

• Pop :

  • As As b5 is the last element in the stack, b5 gets removed from the stack.

  

Code Implementation

1public class StackUsingResizableArray {
2
3    private int[] stack;
4    private int top = -1 ;
5
6    public StackUsingResizableArray(){
7        // initialize stack with 1 element
8        stack = new int[1];
9    }
10
11    // method to push data into stack
12    public void push(int data){
13        if(isFull()) {
14            resize(2*stack.length);
15        }
16        // as top index always points to last element in the stack,
17        // increment top index by 1 and push the data
18        top = top +1 ;
19        stack[top] = data;
20    }
21
22    // method to pop data from stack
23    public int pop() {
24        if(isEmpty()) {
25            throw new RuntimeException("Stack is Empty");
26        }
27        // always pop operation removes top/last element in the stack
28        // decrement top index by 1
29        int data = stack[top];
30        top = top -1;
31        return data;
32    }
33
34    // method to return top element from the stack
35    public int peek(){
36        if(isEmpty()) {
37            throw new RuntimeException("Stack is Empty");
38        }
39        return stack[top];
40    }
41
42    // This method is used to resize array when our stack is full
43    // This method can also be used to shrink array
44    private void resize(int capacity) {
45        System.out.println("resizing stack capacity from >> "+stack.length+" to >> "+capacity);
46        int[] newStack = new int[capacity];
47        for(int i=0;i<stack.length;i++){
48            newStack[i] = stack[i];
49        }
50        stack = newStack;
51    }
52
53    // method to check stack overflow or not
54    public boolean isFull(){
55        return top+1 == stack.length;
56    }
57
58    // method to check the stack is empty or not
59    public boolean isEmpty(){
60        return top == -1;
61    }
62
63    // method to print stack data in LIFO order
64    public void print() {
65        System.out.print("Elements in Stack >> ");
66        for(int i=0; i<=top; i++) {
67            System.out.print(stack[i]+ " ");
68        }
69        System.out.println();
70    }
71
72
73    // Driver Method
74    public static void main(String[] args){
75        StackUsingResizableArray obj = new StackUsingResizableArray();
76
77        for(int i =1; i<=10; i++) {
78            obj.push(i*10);
79            obj.print();
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}