Implement stack using an array

Problem

Design and implement a stack using an array. The stack should support the following operations:

• push(x): Push element x onto the stack.
• pop(): Removes the element on top of the stack and returns it.
• top(): Get the top element.
• isEmpty(): Return whether the stack is empty.

Point to be aware of:

1. Fixed Capacity: The stack can hold a maximum of n elements, which is specified during initialization.
2. Overflow: If the stack reaches its maximum capacity, no further elements can be pushed.
3. Underflow: If the stack is empty and an attempt is made to pop an element, an underflow error occurs.

Examples

Example 1:

Input: 
Operations: ["push(1)", "push(2)", "top()", "pop()", "isEmpty()"]
Output: 
[null, null, 2, 2, false]
Explanation: 
- push(1) adds 1 to the stack.
- push(2) adds 2 to the stack.
- top() returns the current top element, which is 2.
- pop() removes and returns the current top element, which is 2.
- isEmpty() returns false as the stack is not empty.

Solution

Method 1 - Integer stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. By implementing it using an array, we will maintain an array to store stack elements and an integer variable to keep track of the index of the top element.

Here is an approach.

Initialization

1. Initialize an array stack[] of size n to store stack elements.
2. Initialize an index top with -1, indicating that the stack is empty.

Push Operation

1. If the stack is full (i.e., top is equal to n-1), throw an overflow error.
2. Otherwise:
   • Increment top by 1.
   • Set stack[top] to the new data.

Pop Operation

1. If the stack is empty (i.e., top is equal to -1), throw an underflow error.
2. Otherwise:
   • Return the element at the top postion
   • Decrement top by 1.

Other Operations

1. Top Operation: Return the element at the top of the stack without removing it.
2. isEmpty Operation: Check if the stack is empty by verifying the position index.

I recall seeing a similar example in the book "Effective Java" by Joshua Bloch, although I was unsure of its context.

Code

Java

public class Solution {
    private int[] stack;
    private int top;
    private int capacity;

    public Solution(int capacity) {
        this.capacity = capacity;
        stack = new int[capacity];
        top = -1;
    }

    public void push(int x) {
        if (top == capacity - 1) {
            throw new IllegalStateException("Stack overflow");
        }
        stack[++top] = x;
    }

    public int pop() {
        if (top == -1) {
            throw new IllegalStateException("Stack underflow");
        }
        return stack[top--];
    }

    public int top() {
        if (top == -1) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top];
    }

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

Python

class Solution:
    def __init__(self, capacity: int) -> None:
        self.stack: List[int] = [0] * capacity
        self.top: int = -1
        self.capacity: int = capacity

    def push(self, x: int) -> None:
        if self.top == self.capacity - 1:
            raise Exception("Stack overflow")
        self.top += 1
        self.stack[self.top] = x

    def pop(self) -> int:
        if self.top == -1:
            raise Exception("Stack underflow")
        res = self.stack[self.top]
        self.top -= 1
        return res

    def top(self) -> int:
        if self.top == -1:
            raise Exception("Stack is empty")
        return self.stack[self.top]

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

# Example usage
s = Solution(10)
s.push(1)
s.push(2)
print(s.top())    # Output: 2
print(s.pop())    # Output: 2
print(s.isEmpty()) # Output: False

Method 2 - Generic Stack

Code

Java

public class Stack<E> {
    private E[] arr;
    private int CAP;
    private int top;
    private int size;

    @SuppressWarnings("unchecked")
    public Stack(int cap) {
        this.CAP = cap;
        this.arr = (E[]) new Object[cap];
        this.top = -1;
        this.size = 0;
    }

    public E pop() {
        if (this.size == 0) {
            return null;
        }
        this.size--;
        E result = this.arr[top];
        this.arr[top] = null; // prevent memory leak
        this.top--;
        return result;
    }

    public boolean push(E e) {
        if (isFull()) {
            return false;
        }
        this.size++;
        this.arr[++top] = e;
        return true;
    }

    public boolean isFull() {
        return this.size == this.CAP;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public E top() {
        if (isEmpty()) {
            return null;
        }
        return this.arr[top];
    }

    public String toString() {
        if (this.size == 0) {
            return null;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < this.size; i++) {
            sb.append(this.arr[i]).append(", ");
        }

        sb.setLength(sb.length() - 2);
        return sb.toString();
    }

    public static void main(String[] args) {
        Stack<String> stack = new Stack<>(3);
        stack.push("hello");
        stack.push("world");

        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
        System.out.println(stack.isEmpty());
    }
}

Python

from typing import Generic, TypeVar, Optional, List

T = TypeVar('T')

class Stack(Generic[T]):
    def __init__(self, capacity: int) -> None:
        self.capacity: int = capacity
        self.stack: List[Optional[T]] = [None] * capacity
        self.top: int = -1
        self.size: int = 0

    def push(self, item: T) -> bool:
        if self.isFull():
            return False
        self.top += 1
        self.stack[self.top] = item
        self.size += 1
        return True

    def pop(self) -> Optional[T]:
        if self.isEmpty():
            return None
        item = self.stack[self.top]
        self.stack[self.top] = None # prevent memory leakage
        self.top -= 1
        self.size -= 1
        return item

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

    def top(self) -> Optional[T]:
        if self.isEmpty():
            return None
        return self.stack[self.top]

    def __str__(self) -> str:
        if self.isEmpty():
            return "Stack is empty"
        return ', '.join(str(self.stack[i]) for i in range(self.size) if self.stack[i] is not None)

# Example usage
stack = Stack[str](3)
stack.push("hello")
stack.push("world")

print(stack)       # Output: hello, world
print(stack.pop()) # Output: world
print(stack)       # Output: hello
print(stack.pop()) # Output: hello
print(stack)       # Output: Stack is empty
print(stack.isEmpty()) # Output: True

Complexity

• ⏰ Time complexity: 
  • Time complexity for push, pop, and top: O(1) since these operations involve a single step.
• 🧺 Space complexity: O(n), where n is the maximum number of elements in the stack.