Stack Implementation using Array Program

by

A stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack will be the first one to be removed. It’s like a stack of plates, you add to the top and take from the top. This post will explore how to implement a stack using an array in C and Java, including the algorithms and programs.

C Program to Implement Stack Using Array

#include <stdio.h>
#define MAX 500

// Stack structure
typedef struct {
    int top;
    int a[MAX]; // Array to store stack elements
} Stack;

// Function to push an element into the stack
void push(Stack *s, int x) {
    if (s->top >= (MAX - 1)) {
        printf("Stack Overflow\n");
    } else {
        s->a[++(s->top)] = x;
        printf("Item pushed into stack = %d\n", x);
    }
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack Underflow\n");
        return 0;
    } else {
        return s->a[(s->top)--];
    }
}

// Function to peek the top element of the stack
int peek(Stack *s) {
    if (s->top < 0) {
        printf("Stack Underflow\n");
        return 0;
    } else {
        return s->a[s->top];
    }
}

// Function to display all elements in the stack
void display(Stack *s) {
    if (s->top < 0) {
        printf("No elements in Stack\n");
    } else {
        printf("Elements in Stack are:\n");
        for (int i = 0; i <= s->top; i++) {
            printf("%d\n", s->a[i]);
        }
    }
}

// Main function
int main() {
    Stack s;
    s.top = -1;

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Item popped from stack = %d\n", pop(&s));
    printf("%d Returned by Peek operation\n", peek(&s));
    display(&s);

    return 0;
}

Output

Item pushed into stack = 30
Item popped from stack = 30
20 Returned by Peek operation
Elements in Stack are:
10
20

Explanation

The C program provided implements a stack data structure using an array. Let’s go through each part of the program and explain how it works:

Stack Structure Definition
typedef struct {
    int top;
    int a[MAX]; // Array to store stack elements
} Stack;

A structure named Stack is defined, which has two members:

  • top: an integer that will keep track of the index of the top element in the stack.
  • a: an array that serves as the container for the stack elements, with a size defined by the constant MAX.
Push Function
void push(Stack *s, int x) {
    // ...
}

This function takes a pointer to a Stack structure and an integer x to push onto the stack. It checks if the stack is full by comparing the top member against MAX - 1. If there’s room, it increments top and assigns x to the new top position, then prints the pushed item.

Pop Function
int pop(Stack *s) {
    // ...
}

This function removes and returns the top element of the stack. If the stack is empty (top is less than 0), it prints “Stack Underflow” and returns 0. Otherwise, it returns the element at the current top and decrements top.

Peek Function
int peek(Stack *s) {
    // ...
}

This function returns the top element of the stack without removing it, much like looking at the top plate on a pile without taking it off. If the stack is empty, it prints “Stack Underflow” and returns 0. Otherwise, it returns the element at the top.

Display Function
void display(Stack *s) {
    // ...
}

The display function prints all the elements currently in the stack from the bottom to the top. If the stack is empty, it prints “No elements in Stack”.

Main Function
int main() {
    // ...
}

The main function is the entry point of the program. It creates a Stack variable, initializes top to -1 (indicating an empty stack), then uses the push function to add three integers to the stack. It calls pop to remove and print the top element, uses peek to show the current top element without removing it, and finally, calls display to print all elements in the stack.

Java Program to Implement Stack using Array

class Main {
    int MAX = 500;
    int top = -1;
    int[] a = new int[MAX]; // array to store stack elements
  
    public void push(int x) {
        if (top >= (MAX - 1)) {
            System.out.println("Stack Overflow");
        } else {
            a[++top] = x;
            System.out.println("Item pushed into stack = " + x);
        }
    }
 
    public int pop() {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        } else {
            return a[top--];
        }
    }
 
    public int peek() {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        } else {
            return a[top];
        }
    }

    public void display() {
        if (top < 0) {
            System.out.println("No elements in Stack");
        } else {
            for (int i = 0; i <= top; i++) {
                System.out.println(a[i]);
            }
        }
    }

    public static void main(String[] args) {
        Main m = new Main();
        m.push(10);
        m.push(20);
        m.push(30);
        System.out.println("Item popped from stack = " + m.pop());
        System.out.println(m.peek() + " Returned by Peek operation");
        System.out.println("Elements in Stack are:");
        m.display();
    }
}

Output

Item pushed into stack = 10
Item pushed into stack = 20
Item pushed into stack = 30
Item popped from stack = 30
20 Returned by Peek operation
Elements in Stack are:
10
20

Explanation

Class Definition

The class Main contains the stack implementation.

Properties of the Stack
  • int MAX = 500;: This sets the maximum number of items that the stack can hold to 500.
  • int top = -1;: This tracks the top position in the stack. The value -1 indicates that the stack is empty.
  • int[] a = new int[MAX];: This is the array that holds the stack’s elements.
Methods of the Stack
  • public void push(int x): This method adds an element x to the top of the stack. Before doing so, it checks if the stack is full (top >= (MAX - 1)). If not, it increments top and sets the element at this new top index to x.
  • public int pop(): This method removes and returns the top element of the stack. It first checks if the stack is empty (top < 0). If the stack is not empty, it returns the element at top and then decrements top.
  • public int peek(): This method returns the top element of the stack without removing it. It checks if the stack is empty before returning the top element.
  • public void display(): This method prints all the elements present in the stack from the bottom to the top.
Main Method

The main method is the entry point of the program. It performs the following operations:

  • Creates an instance of Main which, in this context, acts as a stack.
  • Pushes three integers onto the stack (10, 20, and 30).
  • Pops the top item from the stack and prints its value, which should be 30 because it was the last item pushed onto the stack.
  • Peeks at the top item of the stack, which should now be 20 after the pop operation, and prints its value.
  • Finally, it prints all elements currently in the stack, which should be 10 and 20.