Jaspreet singh

Posted on Jun 24

Implement stack using array

#computerscience #algorithms #beginners #java

Problem Statement

Implement a Stack using an array supporting:

push(x)
pop()
peek()
isEmpty()
isFull()

Following LIFO:

Last In First Out

Brute Force Intuition

Use a dynamic structure like:

ArrayList<Integer>

Push:

add()

Pop:

remove(size-1)

This works but doesn't teach how Stack works internally.

Moving Towards the Optimal Approach

A Stack only needs:

Array
+
Top Pointer

Maintain:

top = -1

Whenever we push:

arr[++top] = x;

Whenever we pop:

top--;

Pattern Recognition

Stack

=> Array + Top Index

Optimal Java Solution

class myStack {

    int[] arr;
    int top;

    public myStack(int n) {

        arr = new int[n];
        top = -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == arr.length - 1;
    }

    public void push(int x) {

        if (!isFull()) {
            arr[++top] = x;
        }
    }

    public void pop() {

        if (!isEmpty()) {
            top--;
        }
    }

    public int peek() {

        if (!isEmpty()) {
            return arr[top];
        }

        return -1;
    }
}

Dry Run

push(10)

push(20)

push(30)

Stack:

30 ← top
20
10

pop()

Stack:

20 ← top
10

peek()

Returns:

Complexity Analysis

Operation	Complexity
Push	O(1)
Pop	O(1)
Peek	O(1)

Interview One-Liner

Maintain a top pointer and perform all operations directly on the array.

DEV Community