Pattern: Stack — Problem Statement & Solution Guide
Problem Description
You are required to implement a stack that uses a fixed-size array. The stack supports three operations:
* **push x** – add integer *x* to the top of the stack. If the stack is already full, the operation fails and the string "FULL" must be printed.
* **pop** – remove and return the element at the top of the stack. If the stack is empty, print "EMPTY".
* **peek** – return the element at the top without removing it. If the stack is empty, print "EMPTY".
The input begins with an integer *C* (1 ≤ *C* ≤ 10^5) denoting the capacity of the stack. The next line contains an integer *Q* (1 ≤ *Q* ≤ 10^5) specifying the number of operations to perform. Each of the following *Q* lines contains one operation in the format described above. All values *x* satisfy –10^9 ≤ *x* ≤ 10^9.
For every operation that produces an output (i.e., a failed push, a pop, or a peek), print the corresponding result on its own line. The outputs must appear in the same order as the operations are processed.
Your task is to read the input, simulate the stack operations, and produce the required outputs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern: Stack"
WHY DOES IT MATTER?
The stack pattern is foundational for expression evaluation, backtracking algorithms, and memory management; mastering a fixed‑size implementation teaches you how to control resources, enforce invariants, and achieve deterministic performance—critical in embedded systems and real‑time services.
OPTIMIZATION CHALLENGE
The key insight is to avoid shifting elements on every operation; by keeping a single index that moves forward on push and backward on pop, you eliminate O(N) moves and achieve true constant‑time behavior.
REAL-WORLD CONNECTION
Think of a warehouse loading dock where trucks arrive (push) and depart (pop) in a strict order; the dock has a limited number of bays (array capacity), and the manager must reject new arrivals when full and signal when no trucks are present.
During an interview, initialize the array and top pointer clearly, handle edge cases first (full/empty), and always return or print the required messages before updating the pointer to avoid off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(1)O(N)Core Theory — Why This Approach?
A stack is a linear data structure that follows the Last‑In‑First‑Out (LIFO) principle, meaning the most recently added element is the first to be removed. Implementing a stack with a fixed‑size array leverages contiguous memory for O(1) random access, allowing push, pop, and peek operations to be performed in constant time by maintaining a single index (often called 'top') that points to the current boundary of the stack. Naïve approaches, such as using a dynamically‑resizable list without bounds checking, can lead to hidden amortized costs, memory fragmentation, or uncontrolled growth that violates problem constraints; on large inputs this results in unpredictable latency and possible out‑of‑memory failures. The optimal paradigm is to pre‑allocate an array of the given capacity, enforce strict bounds checks on each operation, and update the top pointer atomically, guaranteeing deterministic O(1) time and O(N) space where N is the maximum stack size.
Interview Questions on This Problem
Q1How would you modify the fixed‑size array stack to support a "min" operation that returns the current minimum element in O(1) time?
Maintain an auxiliary stack that stores the minimum value at each depth; on push, compare the new value with the current minimum and push the smaller onto the auxiliary stack; on pop, pop from both stacks. The top of the auxiliary stack always holds the current minimum.
Q2Why is it unsafe to use recursion to implement stack operations in languages with limited call‑stack depth?
Recursion implicitly uses the language's call stack, which has a fixed size and can overflow for deep recursion, whereas an explicit array‑backed stack provides controlled memory usage and predictable behavior regardless of input size.
Q3In a multi‑threaded environment, what synchronization mechanism would you use to make push and pop thread‑safe without sacrificing O(1) performance?
Use a lock‑free atomic compare‑and‑swap (CAS) on the top index or a lightweight mutex/spinlock around the critical section; both ensure constant‑time updates while preventing race conditions.
Examples
Input
3 6 push 1 push 2 peek pop pop pop
Output
2 2 1 EMPTY
Explanation: The stack capacity is 3. After pushing 1 and 2, the top is 2. The peek operation outputs 2. The first pop removes 2 and outputs it. The second pop removes 1 and outputs it. The third pop finds the stack empty and outputs "EMPTY".
Input
2 5 push 5 push 10 push 15 pop peek
Output
FULL 10 5
Explanation: With capacity 2, the third push exceeds the limit, so "FULL" is printed. The stack now contains [5,10] (10 on top). The pop removes 10 and outputs it. The peek then outputs the new top, 5.
Input
5 5 pop push 7 peek pop peek
Output
EMPTY 7 7 EMPTY
Explanation: The first pop finds the stack empty, printing "EMPTY". Pushing 7 adds it to the stack. Peek outputs 7. The subsequent pop removes 7 and outputs it. The final peek finds the stack empty again, printing "EMPTY".
Constraints
- 1 ≤ C ≤ 10^5
- 1 ≤ Q ≤ 10^5
- –10^9 ≤ x ≤ 10^9
- The stack never holds more than C elements at any time
Optimal Approach & Strategy
Pre‑allocate a fixed array, maintain a top index, and perform push/pop/peek by simple index arithmetic, achieving O(1) time.
Brute Force Approach
Use a dynamic list and on each push or pop shift all elements to simulate stack behavior, leading to O(N) time per operation.
Verified Code Solutions
class Stack { constructor(capacity) { this.capacity = capacity; this.stack = []; } push(val) { if (this.stack.length < this.capacity) { this.stack.push(val); } else { throw new Error('Stack overflow'); } } pop() { if (this.stack.length > 0) { return this.stack.pop(); } else { throw new Error('Stack underflow'); } } peek() { if (this.stack.length > 0) { return this.stack[this.stack.length - 1]; } else { return undefined; } } }class Stack { private: int capacity; int* stack; int top; public: Stack(int capacity) { this->capacity = capacity; stack = new int[capacity]; top = -1; } void push(int val) { if (top < capacity - 1) { stack[++top] = val; } else { throw std::runtime_error('Stack overflow'); } } int pop() { if (top >= 0) { return stack[top--]; } else { throw std::runtime_error('Stack underflow'); } } int* peek() { if (top >= 0) { return &stack[top]; } else { return nullptr; } } }class Stack { private int capacity; private int[] stack; private int top; public Stack(int capacity) { this.capacity = capacity; this.stack = new int[capacity]; this.top = -1; } public void push(int val) { if (top < capacity - 1) { stack[++top] = val; } else { throw new RuntimeException('Stack overflow'); } } public int pop() { if (top >= 0) { return stack[top--]; } else { throw new RuntimeException('Stack underflow'); } } public Integer peek() { if (top >= 0) { return stack[top]; } else { return null; } } }class Stack: def __init__(self, capacity): self.capacity = capacity; self.stack = []; def push(self, val): if len(self.stack) < self.capacity: self.stack.append(val); else: raise Exception('Stack overflow'); def pop(self): if len(self.stack) > 0: return self.stack.pop(); else: raise Exception('Stack underflow'); def peek(self): if len(self.stack) > 0: return self.stack[-1]; else: return Noneclass Stack { constructor(capacity) { this.capacity = capacity; this.stack = []; } push(val) { if (this.stack.length < this.capacity) { this.stack.push(val); } else { throw new Error('Stack overflow'); } } pop() { if (this.stack.length > 0) { return this.stack.pop(); } else { throw new Error('Stack underflow'); } } peek() { if (this.stack.length > 0) { return this.stack[this.stack.length - 1]; } else { return undefined; } } }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.