Stack Implementation Using Array

Stack Basics

In computer science, a stack is an abstract data type, which supports two main operations: push(Element e) and pop().
push(Element e) – Adds the element e at the top of the stack.
pop() – removes the element at the top of the stack.

All operations takes place at the top of the stack. And based on the operations the top of the stack changes. If we push() an element e onto the stack, the index of the element e becomes the top of the stack. If we pop() the element from the stack, then the index of the element below it becomes the top of the stack.

A stack can be imagined as a pole fixed to the ground.
The operations can be imagined as –
push(Disc c) – add Disc c to the pole from the top.
pop() – remove one Disc, which is at the top, from the pole.

Below figure shows the basic stack operations in the context of pole and disc.

stack

Implementation

A stack may be implemented to have a fixed capacity or variable capacity.

We will see how to implement a fix sized stack for storing Integers using an Array in Java. Though the code is in Java, the same code can be used in c/c++ with minor modifications.

First we will have a variable ‘maxSize’ which will store the max size of the stack.
We will declare an Integer Array of size ‘maxSize’.
We will also have a variable ‘top’ which will maintain the index of the top of the stack.

    static int maxSize = 100;            //max size of the stack   
    static int[] stack = new int[maxSize];  // stack
    static int top = 0;                 //top of the stack

Lets define the Push operation on the stack:-

    static void push(Integer val) {
        if (top >= maxSize) {
            System.out.println("Stack is Full. Can not add element " + val);
        } else {
            stack[top] = val; // Add the element to the stack top
            top++;            // increment the top
        }
    }

Let us now define the Pop operation on the stack:-

    static Integer pop(){
        if(top<=0){
            System.out.println("Stack is Empty. No element to Pop. Returning null");
            return null;
        }else{
            top--;              //decrement the stack top
            return stack[top];  //return the top element
        }
    }

Lets call the operations on the stack from our main function :-

    public static void main(String[] args) {

        System.out.println(pop()); // pop() method is called on the empty stack 
        push(1);
        System.out.println(pop()); // Returns 1
        
        for(int i=0; i<=99; i++){  // add 100 elements, this is max size of our stack
            push(i);
        }
        push(100);                 // This addition will fail due to overflow
        System.out.println(pop()); // Returns 99
        System.out.println(pop()); // Returns 98
    }

OUTPUT :- 
Stack is Empty. No element to Pop. Returning null
null
1
Stack is Full. Can not add element 100
99
98

Note:- All the fields and functions are declared static in order to avoid creating a class. The basic idea is to show the working of a stack. As far as Java is concerned, it is always better to encapsulate the data and functionality into a class and provide abstraction to the user to use this class.

 

Uses

Expression evaluation and syntax parsing
Backtracking

 

Practice problems based on stack

http://www.spoj.com/problems/ONP/
https://www.hackerearth.com/problem/algorithm/monks-love-for-food/

Leave a Reply

Your email address will not be published. Required fields are marked *