158. Simulate a Stack

Simulate a stack given n operations, each either 'PUSH x', 'POP', or 'PEEK'. On POP, print the removed value (or 'EMPTY' if the stack was already empty); on PEEK, print the current top value without removing it (or 'EMPTY' if empty). PUSH produces no output. Print one result per line, in the order the operations occurred.

Input: The first line contains an integer n, the number of operations. Each of the next n lines contains one operation: 'PUSH x', 'POP', or 'PEEK'. Output: Print one line per POP/PEEK operation, in order, printing the value or 'EMPTY' if the stack was empty.

1 <= n <= 10^5

A stack's defining property is LIFO (last in, first out) - always operating on the SAME end is what gives every operation its O(1) speed, in contrast to a queue, which needs to track two different ends.

Directly implement a stack's basic operations: pushing a value, popping the top, and peeking at the top. Brute force: There's no meaningfully different 'slower' approach - directly using an array's own end (append/remove-last) IS the natural, efficient way to implement a stack. Optimised: Both push and pop/peek operate on the SAME end of an underlying array, which is why they're all O(1) - no shifting of other elements is ever needed, unlike operations at the FRONT of an array.

Back the stack with a plain array and a top index. When a PUSH arrives and the backing array is full, allocate a new array that is only a fixed amount larger (rather than doubling it) and copy every existing element into it before adding the new one. POP and PEEK just read/adjust the top index in O(1). Because the array grows by a constant increment instead of geometrically, resizing happens roughly every constant number of pushes, and each resize copies the whole array, so the total cost across n pushes can degrade to quadratic in the worst case. Time: O(n) per push (worst case), O(1) for pop/peek Space: O(n)

Use the standard dynamic array strategy: back the stack with an array and a top index, but when it fills up, allocate a new array of double the capacity and copy the existing elements over. Because the capacity doubles each time instead of growing by a fixed amount, resizes become exponentially rarer as the stack grows, so the total copying cost across n pushes amortizes out to O(1) per push on average, even though individual resize operations still cost O(n). Time: O(1) amortized per operation Space: O(n)

Represent the stack as a singly linked list where the head pointer is the top of the stack. PUSH allocates a new node pointing to the current head and makes it the new head; POP reads the head's value and advances the head to its next node; PEEK just reads the head's value. None of these operations ever needs to copy or resize anything, so every single operation is O(1) worst-case (not just amortized), and memory used is always exactly proportional to the current number of elements, with no over-allocated spare capacity sitting unused. Time: O(1) worst-case per operation Space: O(n)

1. Use an array (or a language's built-in list/stack type), always adding and removing from the SAME end. 2. On PUSH x, append x to that end. 3. On POP or PEEK, check if the stack is empty first (report 'EMPTY' if so); otherwise remove (POP) or just read (PEEK) the last element.

Time: O(1) per operation. Space: O(n), for storing up to n elements.

a POP or PEEK on an already-empty stack (print 'EMPTY', as in the example's last operation); n = 10^5 for performance; a run of only PUSHes, which produces no output at all.

This is a foundational warm-up - the real value is confirming you handle the EMPTY-stack edge case for POP/PEEK correctly, since the problem explicitly treats it as a valid (not erroneous) operation.