A queue offers four operations, and every one costs O(1) when the queue is built well.
enqueue adds an item at the back.
dequeue removes and returns the item at the front.
front reads that front item without removing it.
isEmpty checks whether any items remain.
You touch only the two ends, never the middle. A good design keeps a pointer to both ends, so neither operation walks the line.
How well it is built depends on the storage. A careless array-backed queue can drift or need shifting. Keeping both ends O(1) takes a ring buffer or a linked list.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
How does a ring buffer tell a full queue from an empty one?Head equal to tail means either one on its own. A strong answer names a fix, such as a size counter or always leaving one slot unused.
With a singly linked list, which end gets enqueue and which gets dequeue, and why?Ask which removal needs the previous node. Dequeue goes at the head, because removing the tail of a singly linked list means an O(n) walk.
If the ring buffer can grow when it fills, is enqueue still O(1)?It is amortized O(1), not worst case. A resize copies every item, but doubling the size makes resizes rare enough to average out.
A queue has four operations, and a well-built queue does every one of them in constant time.
Enqueue adds an item at the back, dequeue removes and returns the item at the front, front reads that item without removing it, and isEmpty tells you whether anything is left.
You only ever touch the two ends, never the middle, so if you keep a pointer to each end, no operation has to walk the line.
That O(1) depends on the storage, because a careless array either drifts forward and wastes space or shifts every item on each dequeue.
So I'd use a ring buffer or a linked list, and the ring buffer is cache-friendly but fixed in size unless you grow it, while the list grows freely but allocates a node per item.
Weak answers to avoid
Lists the operations but gives no costsThe question asks what they cost. Say each one is O(1) and why, since only the two ends are touched and you keep a pointer to each.
Dequeues by removing index 0 of a plain arrayShifting every remaining item makes dequeue O(n). Say the cost depends on the storage, and name the ring buffer or linked list that keeps it O(1).
Dequeues from the tail of a singly linked listRemoving the last node needs the node before it, which takes an O(n) walk. Enqueue at the tail and dequeue at the head.
Says dequeue returns the newest itemThat describes a stack. A queue is first in, first out, so items join at the back and leave from the front.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
