![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Stack Using 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 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
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
- If stack is full (If the stack capacity reaches n)
- throw error
- Else
- increment top by 1
- update stack[top] with new data
1void push(int data) :2 if stack is full :3 throw error45 else :6 // increment top by 17 top = top+189 // put data at top position10 stack[top] = data
1boolean isStackFull() :2 // if top index is the last index of the array3 // then top = n-1 or top+1 = n4 // assumption array index starts with 05 return top+1 == n
Pop Operation
- If stack is empty
- throw error
- throw error
- Else
- remove the element at top index
- update top index to top-1
- remove the element at top index
1int pop() :2 if stack is empty :3 throw error45 else :6 // store data in a temp variable which has be to removed7 int data = stack[top]89 // decrement top by 1 which means after pop,10 // top element points to top-111 top = top-11213 return data
1boolean isEmpty() :2 // check if index top points -1,3 // it means no elements in the stack4 return top = -1
Example Explanation
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
Code Implementation
- Java
- Python
- C++
1public class StackUsingArray {23 private int[] stack;4 private int top = -1 ;5 private int capacity;67 // stack can hold at max n elements8 public StackUsingArray(int n){9 this.capacity = n;10 stack = new int[capacity];11 }1213 // method to push data into stack14 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 data20 top = top +1 ;21 stack[top] = data;22 }2324 // method to pop data from stack25 public int pop() {26 if(isEmpty()) {27 throw new RuntimeException("Stack is Empty");28 }29 // always pop operation removes top/last30 // element in the stack31 // decrement top index by 132 int data = stack[top];33 top = top -1;34 return data;35 }3637 // method to return top element from the stack38 public int peek(){39 if(isEmpty()) {40 throw new RuntimeException("Stack is Empty");41 }42 return stack[top];43 }4445 // method to check overflow condition of the stack46 public boolean isFull(){47 return stack.length == top+1 ;48 }4950 // method to check the stack is empty or not51 public boolean isEmpty(){52 return top == -1;53 }5455 // method to print stack data in LIFO order56 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 }636465 public static void main(String[] args){66 StackUsingArray obj = new StackUsingArray(4);6768 obj.push(20);69 obj.push(30);70 obj.push(45);71 obj.push(50);7273 obj.print();7475 try{76 obj.push(80);77 }catch (Exception e) {78 System.out.println(e.getMessage());79 }8081 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}