Problem

We have seen Implement stack using an array. In a previous solution, we implemented a stack using an array with a fixed capacity. However, this implementation has the limitation of overflow when the number of elements exceeds the array size. To overcome this limitation, we can implement a dynamically growing stack that increases its capacity when it reaches the maximum size.

Examples:

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: 
Operations: ["push(1)", "push(2)", "top()", "push(3)", "pop()", "isEmpty()"]
Output: 
[null, null, 2, null, 3, 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.
- push(3) adds 3 to the stack.
- pop() removes and returns the current top element, which is 3.
- isEmpty() returns false as the stack is not empty.

Solution

Method 1 - Growing the array

A stack follows the Last In First Out (LIFO) principle. By using an array to implement a dynamically growing stack, we can manage elements efficiently by resizing the array when necessary. This approach involves doubling the array size whenever it gets full, similar to how dynamic arrays (like Python lists or Java ArrayLists) work.

A fixed-size array is used in static array-based stack implementations, where the stack’s capacity is fixed at initialization. In contrast, a dynamic array-based implementation uses an array with an initial capacity that grows as needed. When the array reaches its capacity, a new array with double the current capacity is created, and elements from the old array are copied to the new one. This dynamic resizing ensures no overflow occurs.

Points to Consider for Implementing a Stack with Resizable Arrays

  • Capacity:
    • Define an initial capacity for the array, and double the array size when it reaches maximum capacity.
    • Initialize the stack with a minimal capacity, such as 1, to simplify the implementation.
  • No Overflow:
    • Dynamic resizing prevents overflow by creating a new, larger array whenever needed.
  • Waste of Space:
    • As the stack size grows and frequently pops, unused space may accumulate.
    • To optimize space, consider reducing the array size to a quarter of its current capacity when appropriate.
  • Underflow:
    • Occurs when no elements are left in the stack.

Key Operations

Initialization
  • Begin by initializing an array stack[] with an initial capacity of 1.
  • Set the index top to -1, indicating an empty stack.
Push Operation
  1. If the stack is full (i.e., it has reached its maximum capacity):
    • Resize the array to double its current capacity.
  2. Otherwise:
    • Increment the top index by 1.
    • Insert the new value at stack[top].
Pop Operation
  1. If the stack is empty:
    • Throw an exception.
  2. Otherwise:
    • Retrieve and store the element from stack[top].
    • Decrement the top index by 1, effectively removing the element.

Optionally, we can shrink the array. Similar to push operation, can repeated halving work here? Answer is no.

Suppose the array size is almost full, so we double the array, and again due to some reason stack shrinked, and we shrinked the array by 2, and again only few elements are added such that stack again is full, and again we have to double. So, we have to do it again and again.

But if we shrink the array size by 4, then atleast we don’t have to worry again and again for array size.

Other Operations
  1. Top Operation:
    • Return the element at the top index without removing it.
  2. isEmpty Operation:
    • Check if the top index is -1, indicating the stack is empty.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

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

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

    public void push(int x) {
        if (top == capacity - 1) {
            resize(capacity * 2);
        }
        stack[++top] = x;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack underflow");
        }
        int item = stack[top];
        stack[top--] = 0;
        if (top > 0 && top == capacity / 4) {
            resize(capacity / 2);
        }
        return item;
    }

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

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

    private void resize(int newCapacity) {
        int[] newStack = new int[newCapacity];
        System.arraycopy(stack, 0, newStack, 0, top + 1);
        stack = newStack;
        capacity = newCapacity;
    }

    public static void main(String[] args) {
        Solution stack = new Solution(2);
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());  // Outputs: 2
        stack.push(3);  // Resizes the stack
        System.out.println(stack.pop());  // Outputs: 3
        System.out.println(stack.isEmpty());  // Outputs: false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution:
    def __init__(self, capacity: int = 2) -> 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:
            self._resize(self.capacity * 2)
        self.top += 1
        self.stack[self.top] = x

    def pop(self) -> int:
        if self.isEmpty():
            raise Exception("Stack underflow")
        value = self.stack[self.top]
        self.stack[self.top] = 0
        self.top -= 1
        if self.top > 0 and self.top == self.capacity // 4:
            self._resize(self.capacity // 2)
        return value

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

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

    def _resize(self, new_capacity: int) -> None:
        new_stack = [0] * new_capacity
        for i in range(self.top + 1):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

# Example usage
stack = Solution(2)
stack.push(1)
stack.push(2)
print(stack.top())  # Outputs: 2
stack.push(3)  # Resizes the stack
print(stack.pop())  # Outputs: 3
print(stack.isEmpty())  # Outputs: False

VS Linked list implemenation

Read more - Implement stack using linked list#Resizing array vs linked list.