Implement circular stack

Problem

Design and implement a circular stack. A circular stack is similar to a regular stack, but the underlying array is used in a circular manner. The operations push, pop, top (peek), and isEmpty should be supported.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 - Using array

A stack follows the Last In First Out (LIFO) principle. By using a circular array to implement a stack, we can efficiently manage the stack operations by utilizing a circular buffer.

Here is the approach:

Use an array to store the elements.
Use an integer top to keep track of the index of the most recently added element.
If top reaches the end of the array, it wraps around to the beginning (circular logic).

Here are the operations:

Circular Array: The array is considered circular, meaning that if the end of the array is reached, it wraps around to the beginning.
Push Operation: Inserts an element at the next available position considering the circular nature of the array.
Pop Operation: Removes the most recently added element considering the circular nature of the array.
Top Operation: Retrieves the most recently added element without removing it.
isEmpty Operation: Checks if the stack is empty.
isFull Operation: Checks if the stack is full.
Static Capacity: The stack has a fixed capacity and will not resize.

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
59
60
61
62


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

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

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

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack underflow");
        }
        int value = stack[top];
        stack[top] = 0; // Clear element
        top = (top - 1 + capacity) % capacity;
        size--;
        return value;
    }

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

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

    public boolean isFull() {
        return size == capacity;
    }

    public static void main(String[] args) {
        Solution stack = new Solution(2);
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());     // Outputs: 2
        System.out.println(stack.pop());     // Outputs: 2
        System.out.println(stack.isEmpty()); // Outputs: false
        stack.push(3);
        System.out.println(stack.pop());     // Outputs: 3
        System.out.println(stack.isEmpty()); // Outputs: false
        System.out.println(stack.pop());     // Outputs: 1
        System.out.println(stack.isEmpty()); // Outputs: true
    }
}

 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


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

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

    def pop(self) -> int:
        if self.is_empty():
            raise Exception("Stack underflow")
        value = self.stack[self.top]
        self.stack[self.top] = 0
        self.top = (self.top - 1 + self.capacity) % self.capacity
        self.size -= 1
        return value

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

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

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

# Example usage
stack = Solution(2)
stack.push(1)
stack.push(2)
print(stack.top())     # Outputs: 2
print(stack.pop())     # Outputs: 2
print(stack.is_empty()) # Outputs: False
stack.push(3)
print(stack.pop())     # Outputs: 3
print(stack.is_empty()) # Outputs: False
print(stack.pop())     # Outputs: 1
print(stack.is_empty()) # Outputs: True

Complexity

⏰ Time complexity
- push: O(1)
- pop: O(1)
- top: O(1)
- isEmpty: O(1)
- isFull: O(1)
🧺 Space complexity: O(n), where n is the fixed capacity of the stack.

Problem#

Examples#

Example 1:#

Solution#

Method 1 - Using array#

Code#

Complexity#