Implementation Of Stack using Array

In this article, we will learn what is a stack, the algorithm for the implementation of stack using array, the algorithm of the stack with an example dry-run, the program for the implementation of stack using array, and the applications of stack.

What is a Stack?

A stack is a linear data structure. It follows the last in first out (LIFO) methodology. We need a pointer to implement the stack data structure which is called the top. This top pointer points to the last inserted element because we have to return the last inserted element.

What is LIFO (Last In First Out) Strategy?

In the LIFO strategy, the element which is inserted at last will come out first. For example, we can consider the pile of dinner plates, in that we first take out the top plate and after that, we take one by one plate from the pile. This is one real-life example of a stack.

Algorithm for the Implementation of Stack using Array

Push: This function is used to insert a new element into the stack

Algorithm to perform Push Operation:

1. if the stack is full then return
2. else increment the value of the top pointer
3. assign the new value to stack[top]

Pop: This function is used to retrieve a topmost element from the stack

Algorithm to perform Pop Operation:

1. if the stack is empty then return
2. else store the value of stack[top]
3. decrement the value of the top pointer
4. Return the stored value

Top: This function is used to get the top element from the stack.

Algorithm to perform Top Operation:

1. if the stack is empty then return
2. else return stack[top]

isEmpty: This function is used to check whether the stack is empty or not.

Algorithm to Perform isEmpty Operation:

1. if the top is greater than 1 then return true
2. else return false

Algorithm of the Stack with an example dry-run

Now, we know what is stack and the algorithms of operations of the stack. Let’s understand the implementation of stack using array with an example dry run.

First, we will take an empty array of capacity 5 and initialize a top variable with -1.

Now, let’s perform various operations to understand the working of the stack.

Operation: push(10)
In this push operation, first, we will check if the stack is full or not. If the stack is full we will not do anything. If the stack is not full then we will increment the variable top by 1. In this case, the stack is empty so we will increment the top by 1 and the top will become 0. Now, we will assign value 10 to stack[top].

Operation: push(20)
In this push operation, we will insert new element 20 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 1. Now, we will assign value 20 to stack[top].

Operation: pop()
In this pop operation, first, we will check if the stack is empty or not. If the stack is empty we will not do anything. If the stack is not empty then we will store the value of stack[top] (20) in the temp variable. After that, we will decrement the value of the top by 1 so the top will become 0 and remove the top element from the array.

Operation: push(30)
In this push operation, we will insert new element 30 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 1. Now, we will assign the value 30 to stack[top].

Operation: push(40)
In this push operation, we will insert new element 40 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 2. Now, we will assign the value 40 to stack[top].

Operation: push(50)
In this push operation, we will insert new element 50 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 3. Now, we will assign the value 50 to stack[top].

Operation: pop()
In this pop operation, first, we will check if the stack is empty or not. If the stack is empty we will not do anything. If the stack is not empty then we will store the value of stack[top] (50) in the temp variable. After that, we will decrement the value of the top by 1 so the top will become 2 and remove the top element from the array.

Program for the Implementation of Stack using Array

Let’s see how to write a program for the implementation of a stack using an array.

// java program for implementation of stack using array
class Stack {
    static final int capacity = 5;
    int top;
    int a[] = new int[capacity]; // Maximum size of Stack

    boolean isEmpty()
    {
        return (top < 0);
    }
    Stack()
    {
        top = -1;
    }

    boolean push(int x)
    {
        if (top >= (capacity - 1)) {
            System.out.println("Stack is full");
            return false;
        }
        else {
            a[++top] = x;
            System.out.println(x + " is pushed into the stack");
            return true;
        }
    }

    int pop()
    {
        if (top < 0) {
            System.out.println("Stack empty");
            return 0;
        }
        else {
            int x = a[top--];
            return x;
        }
    }

    int peek()
    {
        if (top < 0) {
            System.out.println("Stack empty");
            return 0;
        }
        else {
            int x = a[top];
            return x;
        }
    }
    
    void print_stack(){
        System.out.print("Stack: ");
    	for(int i = top;i>-1;i--){
    	    System.out.print(" | "+ a[i]);
        }
        System.out.print(" |");
        System.out.println("");
    }
}


class Main {
    public static void main(String args[])
    {
        Stack s = new Stack();
        s.push(10);
        s.print_stack();
        
        s.push(20);
        s.print_stack();
        
        System.out.println(s.pop() + " is popped from the stack");
        s.print_stack();
        
        s.push(30);
        s.print_stack();
        
        s.push(40);
        s.print_stack();
        
        s.push(50);
        s.print_stack();
        
        System.out.println(s.pop() + " is popped from the stack");
        s.print_stack();
        
    }
}

Output:

10 is pushed into the stack
Stack:  | 10 |
20 is pushed into the stack
Stack:  | 20 | 10 |
20 is popped from the stack
Stack:  | 10 |
30 is pushed into the stack
Stack:  | 30 | 10 |
40 is pushed into the stack
Stack:  | 40 | 30 | 10 |
50 is pushed into the stack
Stack:  | 50 | 40 | 30 | 10 |
50 is popped from the stack
Stack:  | 40 | 30 | 10 |

Applications of Stack:

• A stack can be used in memory management
• A stack can be used to perform infix to postfix or prefix conversion
• A stack can be used to perform Depth First Traversal (DFS)
• A stack can be used to implement various backtracking algorithms
• A stack can also be used in graph algorithms like topological sort and strongly connected components

FAQs Related to Stack Data Structure

1) Which data structures can be used for queue implementation?
An array, queue, or linked list can be used to implement a stack. Using an Array is the simplest way to implement a stack.

2) What is the Time Complexity of various stack operations?

3) Which is better stack or queue?
The stack can be used to solve recursive problems such as pre-order, post-order, and in-order traversal of the binary tree, whereas the queue can be used to solve problems such as the producer-consumer problem, which involves sequential processing of underlying data. Stack follows LIFO methodology while queue follows FIFO methodology.