Implement Queue using Array

Implement a queue (first-in, first-out) backed by an array, supporting:

push(x) — add x to the back of the queue.
pop() — remove and return the front element; if the queue is empty, return -1.

The first operation names the class (its constructor). Each pop reports its result; push and the constructor report nothing.

Hints

· Stuck? Reveal one nudge at a time.

Push adds at the back — where should pop remove from for FIFO order?

Removing from the front by shifting is O(n); can you avoid moving elements?

Keep a front index that advances on each pop; return -1 once it passes the end.

Common doubts

That shifts every remaining element left, costing O(n). A front index advances in O(1) and leaves the elements in place.

In this simple version, yes — the popped prefix isn't reclaimed. A production queue uses a circular buffer (or a linked list) to reuse space.

Interview follow-ups

· What an interviewer asks next.

Wrap the front and back indices modulo the capacity, reusing freed slots; resize when the buffer is full.

Two stacks give amortized O(1) FIFO by moving elements from an input stack to an output stack only when the output is empty.

Fun facts

Ring buffers — circular-array queues — are everywhere in systems: network packet queues, audio buffers, and OS scheduler run-queues.
The 'advance an index instead of shifting' idea is the same trick behind the two-pointer sliding window.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: push(5), push(10), pop(), pop(), pop()
Output: 5, 10, -1
FIFO: the first pushed (5) is the first popped, then 10, then -1 (empty).

Example 2

Input: push(7), pop()
Output: 7
Push 7, then pop returns 7.

Constraints

- 1 <= number of operations <= 100 - 1 <= x <= 10^5 - pop() returns -1 if the queue is empty.

A queue is first in, first out: you add at the back and remove from the front. The subtlety with an array is that removing from the front naively shifts every element (O(n)). The fix is a front index that just advances — no shifting, so every operation stays O(1).

Prerequisites

Before you start

· Concepts used directly in the solution.

FIFO discipline. The first element enqueued is the first dequeued.

Front pointer. An index marking where the live queue begins, so dequeue is O(1) without shifting.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Where do push and pop act?”

Push adds at the back; pop removes from the front.

“What does pop return when empty?”

-1, by convention.

The ideal opening — say it like this

Queue is FIFO, so I push to the back and pop from the front.

To avoid shifting the array on every pop, I keep a front index that advances.

Pop returns -1 when the front index has passed the last element.

Understand the problem

Worked example — push 5, push 10, pop, pop, pop

push 5   -> arr=[5],     front=0   (null)
push 10  -> arr=[5,10],  front=0   (null)
pop      -> front=1                returns 5
pop      -> front=2                returns 10
pop      -> front=2 (empty)        returns -1

Key observations

1Aha

A front index avoids shifting

Removing from the front of an array by shifting is O(n). Tracking a front index and advancing it makes dequeue O(1); the elements never move.

2Aha

Empty when front reaches the end

The queue is empty exactly when front has advanced past the last pushed element — return -1 then.

Summary

Key takeaway

A queue on an array pushes to the back and pops from the front using a moving front index — never shifting elements — so every operation is O(1). Pop returns -1 once front passes the last element.

push(x): arr.append(x)
pop():   return -1 if front >= len(arr) else arr[front]; front += 1