Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Implement stack using array

EASYProblemSolveExternal Links

Description

Implement a stack data structure using an array of fixed size n. The stack must follow the LIFO (Last In, First Out) principle — the element that is inserted last is the first one to be removed.

Your implementation must support the following operations:

  1. push(x): Insert an element x at the top of the stack. If the stack is already full (contains n elements), do nothing.
  2. pop(): Remove and return the element from the top of the stack. If the stack is empty, return -1.
  3. peek(): Return the top element without removing it. If the stack is empty, return -1.
  4. isEmpty(): Return true if the stack contains no elements, otherwise return false.
  5. isFull(): Return true if the stack has reached its maximum capacity n, otherwise return false.

You will be given a sequence of queries. Each query calls one of the above operations. Implement the functions, and the driver code will handle the output.

Examples

Example 1

Input: n = 3, queries = [[1, 5], [1, 3], [3], [2], [4], [5]]

Output: [3, false, false]

Explanation:

  • push(5): Stack becomes [5]. Element 5 is placed at the bottom.
  • push(3): Stack becomes [5, 3]. Element 3 is now on top of 5.
  • peek(): The top element is 3, so return 3.
  • pop(): Remove and return top element 3. Stack becomes [5].
  • isEmpty(): The stack still contains element 5, so return false.
  • isFull(): The stack has capacity 3 but only 1 element, so return false.

Example 2

Input: n = 1, queries = [[2], [3], [4], [1, 9], [5]]

Output: [-1, -1, true, true]

Explanation:

  • pop(): Stack is empty, nothing to remove. Return -1.
  • peek(): Stack is empty, no top element exists. Return -1.
  • isEmpty(): Stack has no elements. Return true.
  • push(9): Stack becomes [9]. The single available slot is now occupied.
  • isFull(): Stack capacity is 1 and it holds 1 element. Return true.

Constraints

  • 1 ≤ n ≤ 10^3
  • 1 ≤ q ≤ 10^3
  • 0 ≤ x ≤ 10^5

Editorial

Brute Force

Intuition

Imagine you have a row of empty boxes on a table and you want to use them as a stack. The simplest idea — without any bookkeeping — is to look through the boxes each time you need to do something.

When you want to push an element, you walk from the left end and find the first empty box. When you want to pop or peek, you walk from the right end and find the last occupied box. You are essentially scanning the array every single time because you never bother to remember where the top of the stack currently is.

This works correctly, but it is wasteful. Every push, pop, and peek requires scanning through potentially the entire array. The core inefficiency is that we are not maintaining any state about where the top element lives — we rediscover it from scratch on every operation.

We mark empty slots with a sentinel value (such as -1). Since all valid values satisfy 0 ≤ x ≤ 10^5, the sentinel -1 can never collide with an actual element.

Step-by-Step Explanation

Let's trace through Example 1 with n = 3, queries: push(5), push(3), peek(), pop():

Step 1: Initialize array of size 3 with sentinel -1: arr = [-1, -1, -1]. No top pointer is maintained.

Step 2: push(5): Scan from index 0 to find the first empty slot.

  • arr[0] = -1 → empty! Place 5 here.
  • arr becomes [5, -1, -1].

Step 3: push(3): Scan from index 0 again.

  • arr[0] = 5 → occupied, skip.
  • arr[1] = -1 → empty! Place 3 here.
  • arr becomes [5, 3, -1].

Step 4: peek(): Scan backward from the last index to find the topmost element.

  • arr[2] = -1 → empty, skip.
  • arr[1] = 3 → found! Return 3.

Step 5: pop(): Scan backward from the last index.

  • arr[2] = -1 → empty, skip.
  • arr[1] = 3 → found! Save value 3, reset slot to -1.
  • arr becomes [5, -1, -1]. Return 3.

Result: Output from peek() is 3. Each operation required scanning through the array.

Brute Force — Scanning the Array Without a Top Pointer — Without maintaining a top pointer, every operation must linearly scan the array to locate the correct position — push scans forward for the first empty slot, pop and peek scan backward for the last occupied slot.

Algorithm

  1. Initialize an array of size n with all elements set to -1 (sentinel for empty).
  2. push(x):
    • Scan from index 0 to n-1.
    • Find the first index where arr[i] == -1.
    • Set arr[i] = x.
    • If no empty slot found, stack is full — do nothing.
  3. pop():
    • Scan from index n-1 down to 0.
    • Find the last index where arr[i] != -1.
    • Save arr[i], set arr[i] = -1, return saved value.
    • If all slots are -1, stack is empty — return -1.
  4. peek():
    • Scan from index n-1 down to 0.
    • Return the first arr[i] != -1 found.
    • If none found, return -1.
  5. isEmpty(): Scan all slots; if all are -1, return true.
  6. isFull(): Scan all slots; if none are -1, return true.

Code

class MyStack {
    int arr[1000];
    int capacity;

public:
    MyStack(int n) {
        capacity = n;
        for (int i = 0; i < n; i++)
            arr[i] = -1;
    }

    void push(int x) {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] == -1) {
                arr[i] = x;
                return;
            }
        }
    }

    int pop() {
        for (int i = capacity - 1; i >= 0; i--) {
            if (arr[i] != -1) {
                int val = arr[i];
                arr[i] = -1;
                return val;
            }
        }
        return -1;
    }

    int peek() {
        for (int i = capacity - 1; i >= 0; i--) {
            if (arr[i] != -1)
                return arr[i];
        }
        return -1;
    }

    bool isEmpty() {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] != -1)
                return false;
        }
        return true;
    }

    bool isFull() {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] == -1)
                return false;
        }
        return true;
    }
};
class MyStack:
    def __init__(self, n):
        self.arr = [-1] * n
        self.capacity = n

    def push(self, x):
        for i in range(self.capacity):
            if self.arr[i] == -1:
                self.arr[i] = x
                return

    def pop(self):
        for i in range(self.capacity - 1, -1, -1):
            if self.arr[i] != -1:
                val = self.arr[i]
                self.arr[i] = -1
                return val
        return -1

    def peek(self):
        for i in range(self.capacity - 1, -1, -1):
            if self.arr[i] != -1:
                return self.arr[i]
        return -1

    def isEmpty(self):
        for i in range(self.capacity):
            if self.arr[i] != -1:
                return False
        return True

    def isFull(self):
        for i in range(self.capacity):
            if self.arr[i] == -1:
                return False
        return True
class MyStack {
    private int[] arr;
    private int capacity;

    public MyStack(int n) {
        capacity = n;
        arr = new int[n];
        Arrays.fill(arr, -1);
    }

    public void push(int x) {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] == -1) {
                arr[i] = x;
                return;
            }
        }
    }

    public int pop() {
        for (int i = capacity - 1; i >= 0; i--) {
            if (arr[i] != -1) {
                int val = arr[i];
                arr[i] = -1;
                return val;
            }
        }
        return -1;
    }

    public int peek() {
        for (int i = capacity - 1; i >= 0; i--) {
            if (arr[i] != -1)
                return arr[i];
        }
        return -1;
    }

    public boolean isEmpty() {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] != -1)
                return false;
        }
        return true;
    }

    public boolean isFull() {
        for (int i = 0; i < capacity; i++) {
            if (arr[i] == -1)
                return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n) per operation

Every operation — push, pop, peek, isEmpty, and isFull — requires scanning through the array. In the worst case, push must scan all n slots (when the stack is nearly full), pop and peek must scan from the end all the way to index 0 (when only one element exists at the start), and isEmpty/isFull must check every slot. For q queries, the total time is O(n × q).

Space Complexity: O(n)

We use a fixed-size array of n elements. No additional data structures are needed beyond the array itself.

Why This Approach Is Not Efficient

The brute force spends O(n) time on every single operation because it rediscovers the top position from scratch each time. With n up to 10^3 and q up to 10^3, the total work can reach 10^6 array accesses — functional but wasteful.

The fundamental problem is the absence of state tracking. A stack's top only moves by one position per push or pop, yet we scan up to n slots to find it. We are doing linear work for what should be a constant-time update.

Additionally, the sentinel-based approach has a subtle limitation: it reserves one value (-1) as "empty," preventing that value from being stored. While the constraints (0 ≤ x ≤ 10^5) make this safe here, it is not a general solution.

Key insight: If we simply maintain a single integer variable top that tracks the index of the most recently pushed element, every operation becomes a direct array access — no scanning required. One extra variable eliminates all linear overhead.

Optimal Approach - Top Pointer Tracking

Intuition

Think of a stack of plates in a cafeteria. You do not count all the plates to figure out which one is on top — you just look at the top plate directly. The cafeteria knows the top because it tracks the height of the pile.

We apply the same idea: maintain a single integer variable top that always stores the index of the topmost element in the array. When we push, we increment top and place the element at that index. When we pop, we read the element at top and decrement it. Peek just reads arr[top]. isEmpty checks top == -1, and isFull checks top == n - 1.

By remembering just one number — the index of the top — we convert every O(n) scan into an O(1) direct access. This is the standard, universally-used array-based stack implementation.

Step-by-Step Explanation

Let's trace through Example 1 with n = 3, queries: push(5), push(3), peek(), pop(), isEmpty(), isFull():

Step 1: Initialize: arr = [0, 0, 0], top = -1. A top of -1 means the stack is empty.

Step 2: push(5): Is the stack full (top == n - 1 = 2)? No (top = -1). Increment top to 0. Set arr[0] = 5. Done in O(1).

Step 3: push(3): Is the stack full? No (top = 0 ≠ 2). Increment top to 1. Set arr[1] = 3. Done in O(1).

Step 4: peek(): Is the stack empty (top == -1)? No (top = 1). Return arr[1] = 3. No modification needed. O(1).

Step 5: pop(): Is the stack empty? No (top = 1). Save arr[1] = 3. Decrement top to 0. Return 3. O(1).

Step 6: isEmpty(): Is top == -1? No (top = 0). The stack still has element 5. Return false. O(1).

Step 7: isFull(): Is top == n - 1 = 2? No (top = 0). Two slots are still free. Return false. O(1).

Result: Output: [3, false, false]. Every operation completed in constant time — zero scanning.

Optimal Stack — Direct Access via Top Pointer — Watch how a single top pointer variable eliminates all scanning. Every push, pop, peek, isEmpty, and isFull operation completes in O(1) by reading or updating the top index directly.

Algorithm

  1. Initialize an array arr of size n and set top = -1.
  2. push(x):
    • If top == n - 1, the stack is full — do nothing.
    • Otherwise, increment top and set arr[top] = x.
  3. pop():
    • If top == -1, the stack is empty — return -1.
    • Otherwise, save arr[top], decrement top, return the saved value.
  4. peek():
    • If top == -1, return -1.
    • Otherwise, return arr[top].
  5. isEmpty(): Return top == -1.
  6. isFull(): Return top == n - 1.

Code

class MyStack {
    int arr[1000];
    int topIdx;
    int capacity;

public:
    MyStack(int n) {
        capacity = n;
        topIdx = -1;
    }

    void push(int x) {
        if (topIdx < capacity - 1) {
            arr[++topIdx] = x;
        }
    }

    int pop() {
        if (topIdx >= 0) {
            return arr[topIdx--];
        }
        return -1;
    }

    int peek() {
        if (topIdx >= 0) {
            return arr[topIdx];
        }
        return -1;
    }

    bool isEmpty() {
        return topIdx == -1;
    }

    bool isFull() {
        return topIdx == capacity - 1;
    }
};
class MyStack:
    def __init__(self, n):
        self.arr = [0] * n
        self.capacity = n
        self.top = -1

    def push(self, x):
        if self.top < self.capacity - 1:
            self.top += 1
            self.arr[self.top] = x

    def pop(self):
        if self.top >= 0:
            val = self.arr[self.top]
            self.top -= 1
            return val
        return -1

    def peek(self):
        if self.top >= 0:
            return self.arr[self.top]
        return -1

    def isEmpty(self):
        return self.top == -1

    def isFull(self):
        return self.top == self.capacity - 1
class MyStack {
    private int[] arr;
    private int topIdx;
    private int capacity;

    public MyStack(int n) {
        arr = new int[n];
        capacity = n;
        topIdx = -1;
    }

    public void push(int x) {
        if (topIdx < capacity - 1) {
            arr[++topIdx] = x;
        }
    }

    public int pop() {
        if (topIdx >= 0) {
            return arr[topIdx--];
        }
        return -1;
    }

    public int peek() {
        if (topIdx >= 0) {
            return arr[topIdx];
        }
        return -1;
    }

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

    public boolean isFull() {
        return topIdx == capacity - 1;
    }
}

Complexity Analysis

Time Complexity: O(1) per operation

Every operation — push, pop, peek, isEmpty, and isFull — performs a fixed number of steps regardless of the stack size:

  • push: one comparison + one increment + one array write = O(1)
  • pop: one comparison + one array read + one decrement = O(1)
  • peek: one comparison + one array read = O(1)
  • isEmpty/isFull: one comparison = O(1)

For q queries, the total time is O(q), which is optimal since we must process each query at least once.

Space Complexity: O(n)

We use a fixed-size array of n elements plus one integer (top). The top variable is O(1) additional space, so the overall space remains O(n) — the same as the brute force. The improvement is entirely in time complexity, achieved by spending one extra integer of space to track the top position.