# Stack Using Dynamic Array

# 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

# 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

- If stack is full (If the stack has reaches its maximum capacity)
- resize the array

- 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 capacity4 resize(2*stack.length)56 // increment top by 17 top = top+189 // store new data at top position10 stack[top] = data

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

1void resize(len) :2 // create new array newStack with size len3 newStack = int[len]45 for i=0 to stack.length :6 // copy data from old stack to newStack7 newStack[i] = stack[i]89 // re-assign stack to point to newStack10 // which has double the capacity now.11 stack = newStack12

# 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).

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.

# Code Implementation

- Java
- Python
- C++

1public class StackUsingResizableArray {23 private int[] stack;4 private int top = -1 ;56 public StackUsingResizableArray(){7 // initialize stack with 1 element8 stack = new int[1];9 }1011 // method to push data into stack12 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 data18 top = top +1 ;19 stack[top] = data;20 }2122 // method to pop data from stack23 public int pop() {24 if(isEmpty()) {25 throw new RuntimeException("Stack is Empty");26 }27 // always pop operation removes top/last element in the stack28 // decrement top index by 129 int data = stack[top];30 top = top -1;31 return data;32 }3334 // method to return top element from the stack35 public int peek(){36 if(isEmpty()) {37 throw new RuntimeException("Stack is Empty");38 }39 return stack[top];40 }4142 // This method is used to resize array when our stack is full43 // This method can also be used to shrink array44 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 }5253 // method to check stack overflow or not54 public boolean isFull(){55 return top+1 == stack.length;56 }5758 // method to check the stack is empty or not59 public boolean isEmpty(){60 return top == -1;61 }6263 // method to print stack data in LIFO order64 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 }717273 // Driver Method74 public static void main(String[] args){75 StackUsingResizableArray obj = new StackUsingResizableArray();7677 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 }8687}