257. Simulate a Queue

Simulate a queue given n operations, each either 'ENQUEUE x', 'DEQUEUE', or 'FRONT'. On DEQUEUE, print the removed value (or 'EMPTY' if the queue was already empty); on FRONT, print the current front value without removing it (or 'EMPTY' if empty). ENQUEUE 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: 'ENQUEUE x', 'DEQUEUE', or 'FRONT'. Output: Print one line per DEQUEUE/FRONT operation, in order, printing the value or 'EMPTY' if the queue was empty.

1 <= n <= 10^5

Handling the empty-queue case correctly (reporting EMPTY rather than crashing) for both DEQUEUE and FRONT is exactly the kind of edge case a real interview implementation is expected to handle without being explicitly reminded.

Build the basic behavior of a queue from scratch: things join at the back, and only ever leave from the front, in the exact order they joined. Brute force: There isn't really a 'brute force vs optimized' distinction here - this problem IS the fundamental operation; the only real risk is accidentally implementing stack behavior (removing from the back) instead of true queue behavior (removing from the front). Optimised: Using a data structure with O(1) operations at both ends (a language's built-in deque, or a circular-array-backed queue) keeps every ENQUEUE/DEQUEUE/FRONT operation instant, regardless of how many elements are currently in the queue.

Use a fixed or growable array together with two separate indices, front and rear, instead of always operating at index 0. ENQUEUE writes at rear and advances rear; DEQUEUE reads the element at front and simply advances the front index (or wraps around in a circular buffer) rather than physically shifting any remaining elements, printing 'EMPTY' when front == rear; FRONT just reads the element at the front index without moving anything. Every operation touches a fixed number of array cells regardless of how many elements are currently queued, giving true worst-case constant time per operation. Time: O(1) per operation, O(n) overall Space: O(n)

Store the queue's contents in a plain dynamic array. ENQUEUE appends to the end of the array; DEQUEUE removes the element at index 0 and then shifts every remaining element one position to the left to close the gap (or prints 'EMPTY' if the array is empty); FRONT simply reads index 0 (or prints 'EMPTY'). Because removing from the front requires shifting all remaining elements, a single DEQUEUE can cost O(current size), making repeated dequeues on a large queue expensive overall. Time: O(n) per DEQUEUE, O(n^2) overall worst case Space: O(n)

Maintain two stacks: an 'in' stack that receives every ENQUEUE via a plain push, and an 'out' stack used for DEQUEUE/FRONT. Whenever the 'out' stack is empty and a DEQUEUE or FRONT is requested, pop every element off 'in' and push it onto 'out', which reverses their order so the oldest enqueued element ends up on top of 'out'; then just pop or peek 'out' as needed (printing 'EMPTY' if both stacks are empty). Each element is moved from 'in' to 'out' at most once, so the total work across all n operations is linear even though a single operation can occasionally cost O(n). Time: O(n) total (amortized O(1) per operation) Space: O(n)

1. Keep a list representing the line, with a 'front' end and a 'back' end. 2. ENQUEUE adds a new value to the back of the line. 3. DEQUEUE removes and reports the value at the front of the line (or reports EMPTY if there's no one there). 4. FRONT reports the value at the front without removing them (or EMPTY if no one's there).

Time: O(1) per operation - adding or removing from either end of a proper queue never has to touch or shift any other elements. Space: O(n), proportional to how many elements are currently sitting in the queue.

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

Be explicit that a queue is FIFO (First In, First Out) versus a stack's LIFO (Last In, First Out) - confusing these two is one of the most basic, most commonly checked mistakes in any data-structures interview.