Queues explained
LinkA photo-printing kiosk has one printer, but several customers can submit jobs while it is busy. Ava sends twelve photos. A few seconds later, Bo sends one, then Chen sends six. The printer cannot handle all three jobs at once, so the kiosk needs to keep the unfinished jobs somewhere. It should normally print Ava’s job before Bo’s and Bo’s before Chen’s because that is the order in which they arrived.
One variable cannot hold several waiting jobs. An array can. An array is a row of numbered slots in memory, and each slot can store a value or a reference to a value elsewhere in memory. We could put the next job in slot 0, the following job in slot 1, and so on. The problem appears when Ava’s job leaves. Removing slot 0 creates a hole. If we insist that the next job must always occupy slot 0, the programme has to copy Bo’s reference one position to the left, then Chen’s, followed by every other waiting reference. Removing one job from a queue of one million could copy 999,999 references.
A queue gives us a better rule. It adds new items at one end and removes waiting items from the other. A circular array can maintain this rule without moving the remaining items after each removal. The programme remembers where the next item lives and where the next empty slot is. Ordinary additions and removals then take a fixed amount of work, regardless of whether the queue holds three jobs or three million. A fixed circular array does have a limit: once every slot is occupied, the programme must reject new work, wait for space, or apply another deliberate policy.
How does a queue work?
LinkA queue is a rule for deciding which stored item comes out next. In an ordinary first-in, first-out queue, the item that arrived first leaves first. This rule is often shortened to FIFO. Adding an item is called enqueueing. The new item joins at the tail. Removing the oldest item is called dequeueing, and that item leaves from the head. Peeking reads the item at the head without removing it.
The rule matters more than the storage underneath it. One programme may keep its queue in an array. Another may connect separately allocated pieces of memory called linked nodes. Both can still present the same FIFO behaviour to the code that uses them.
Not every collection with “queue” in its name follows FIFO. A priority queue chooses according to a ranking, while a double-ended queue allows additions and removals at both ends. This article concerns the ordinary FIFO queue.
Why not remove the first array slot?
LinkStart with four array slots. Each occupied slot stores a reference to a print job. A reference is a value that tells the programme where the full job can be found in memory. Copying a reference does not copy all the photos, but copying hundreds of thousands of references still takes work.
position: 0 1 2 3
job: Ava Bo Chen empty
If dequeue always removes position 0, removing Ava leaves a hole before Bo. The programme can repair the layout by copying Bo’s reference into position 0 and Chen’s into position 1.
position: 0 1 2 3
job: Bo Chen empty empty
This layout looks neat, but that neatness has a cost. Every remaining reference moved. As the queue grows, each removal may require more copying.
There is no need to keep the next job at position 0. The programme can store a number named headPosition instead. That number identifies the slot containing the next job. After removing Ava, the programme clears position 0 and changes the head from 0 to 1. Bo and Chen stay where they are.
position: 0 1 2 3
job: empty Bo Chen empty
^ head ^ tail
Clearing the old slot matters. The queue no longer owns Ava’s job, so it should not retain a reference to it. If no other part of the programme refers to that job, the memory manager can then reclaim its memory.
The second remembered number is tailPosition. It identifies the empty slot where the next enqueued job will go. The queue now changes positions instead of moving all the live references.
Reusing the array as a circle
LinkMoving the head and tail to the right creates empty slots at the beginning of the array. Eventually the tail reaches the final position even though those earlier slots are available. A circular array solves this by treating the position after the final slot as position 0. No physical circle exists in memory. The programme still owns one ordinary row of slots. Only the position calculation wraps around.
We will use an array with five slots and remember three numbers. headPosition identifies the next item to remove. tailPosition identifies the next slot to fill. itemCount records how many items are present.
At first, every slot is empty. The head and tail both have position 0, and the item count is 0.
position: 0 1 2 3 4
stored value: empty empty empty empty empty
headPosition: 0
tailPosition: 0
itemCount: 0
logical order: empty
Enqueue Ava, Bo, and Chen. Each operation writes one reference into the slot named by the tail, advances the tail, and adds one to the count.
position: 0 1 2 3 4
stored value: Ava Bo Chen empty empty
headPosition: 0
tailPosition: 3
itemCount: 3
logical order: Ava, Bo, Chen
Now dequeue twice. The first call reads Ava from position 0 and clears that slot. The second does the same with Bo at position 1. The head advances twice and the count falls twice. Chen’s reference does not move.
position: 0 1 2 3 4
stored value: empty empty Chen empty empty
headPosition: 2
tailPosition: 3
itemCount: 1
logical order: Chen
Enqueue Dina and Eli. Their references enter positions 3 and 4. After writing Eli at position 4, the tail must advance. Position 5 does not exist, so it wraps to 0.
The programme can calculate this by adding one to the current position, dividing by the array’s capacity, and keeping the remainder. The remainder is what remains after making as many complete groups as possible. Five divided by five has remainder 0, so advancing position 4 in a five-slot array produces position 0.
position: 0 1 2 3 4
stored value: empty empty Chen Dina Eli
headPosition: 2
tailPosition: 0
itemCount: 3
logical order: Chen, Dina, Eli
Enqueue Faye. Her reference enters the available slot at position 0, and the tail advances to position 1.
position: 0 1 2 3 4
stored value: Faye empty Chen Dina Eli
headPosition: 2
tailPosition: 1
itemCount: 4
logical order: Chen, Dina, Eli, Faye
Reading the occupied slots from left to right gives Faye, Chen, Dina, Eli. That is not the queue order. The logical order begins at the moving head, continues to the end of the array, and then wraps to the beginning. The next dequeue returns Chen, not Faye.
The item count also resolves a quiet ambiguity. When the head and tail are both 0, the queue might be empty, as it was initially. They can also meet after the tail completes a full lap and fills every slot. A count of 0 means empty, while a count of 5 means full. The positions alone cannot tell us which state we have.
How does a queue work in code?
LinkThe pseudocode below implements the same five-slot queue. noItem represents an empty slot and cannot be a valid print job. The code returns queueFull or queueEmpty instead of silently overwriting a job or reading an empty slot.
; Memory begins as five empty slots and three bookkeeping numbers.
(define capacity 5)
(define storedJobs (makeArray capacity noItem))
(define headPosition 0)
(define tailPosition 0)
(define itemCount 0)
(define advancePosition (function currentPosition)
; Position 4 advances to 0 because 5 divided by 5 has remainder 0.
(return (remainder (add currentPosition 1) capacity))))
(define enqueue (function job)
(if (equals itemCount capacity)
(return queueFull))
; Before this write, tailPosition names an empty slot.
; Afterwards, that slot contains a reference to the new job.
(arraySet storedJobs tailPosition job)
(set tailPosition (advancePosition tailPosition))
(set itemCount (add itemCount 1))
(return added)))
(define dequeue (function)
(if (equals itemCount 0)
(return queueEmpty))
(define nextJob (arrayGet storedJobs headPosition))
; Remove the queue's reference before advancing the head.
(arraySet storedJobs headPosition noItem)
(set headPosition (advancePosition headPosition))
(set itemCount (subtract itemCount 1))
(return nextJob)))
(define peek (function)
; Peeking reads the head slot without changing memory.
(if (equals itemCount 0)
(return queueEmpty))
(return (arrayGet storedJobs headPosition))))
(enqueue "Ava")
(enqueue "Bo")
(enqueue "Chen")
; Slots: [Ava, Bo, Chen, noItem, noItem]
; Head: 0, tail: 3, count: 3
(dequeue)
; Returns Ava, clears slot 0, and advances the head to 1.
(dequeue)
; Returns Bo, clears slot 1, and advances the head to 2.
(enqueue "Dina")
(enqueue "Eli")
; Eli enters slot 4, then the tail wraps to 0.
(enqueue "Faye")
; Slots: [Faye, noItem, Chen, Dina, Eli]
; Logical order: Chen, Dina, Eli, Faye
(dequeue)
; Returns Chen. The leftmost occupied slot is not the head.
Real programming interfaces handle empty and full states in several ways. Some throw an error, some return a success flag beside the result, and some return a special value. Whichever approach an interface chooses, it must distinguish that special outcome from a valid stored item.
How much work does a queue do?
LinkAn ordinary enqueue writes one array slot and changes the tail and count. An ordinary dequeue reads and clears one slot, then changes the head and count. The number of waiting jobs does not add more steps to either operation. This is called constant time and is commonly written as O(1). Constant time does not mean that the operation takes no time. It means the amount of work does not grow with the queue length.
Peeking also takes constant time because it reads the known head slot without changing memory. Searching for a particular job is different. A FIFO queue only tells the programme which item is next. It has no rule for jumping directly to Chen, so a search may have to inspect every waiting item.
A queue that grows its array needs one more qualification. When its current storage fills, it can allocate a larger array and copy the live references into it. That one enqueue is expensive because the copying grows with the number of waiting items. If the array repeatedly grows by a large factor, such as doubling, most enqueues still perform only the small fixed set of operations. The occasional copying cost is spread across many cheap enqueues. This is called amortised constant time.
When are queues used?
LinkQueues are useful when work arrives at one rate and another part of a system handles it at a different rate. The kiosk accepts a short burst of print jobs even though one printer can finish only one job at a time. The code receiving submissions is a producer because it creates queued work. The printer is a consumer because it removes and processes that work. The same arrangement appears in email delivery, image processing, and web servers that keep requests waiting for an available worker.
A queue absorbs a temporary difference in speed. It does not create processing capacity. If customers submit jobs faster than the printer completes them for long enough, the queue eventually fills or consumes increasing amounts of memory. A fixed-capacity queue forces the system designer to choose what happens next. The producer might wait until space becomes available, reject the new job, or save it in more durable storage. Making the producer wait or slow down is one form of backpressure. The consumer’s limited rate pushes back towards the source instead of allowing the waiting work to grow without a limit.
Queues also help algorithms explore possibilities in layers. Imagine finding a route with the fewest train connections. Start at Home, with direct connections to Museum and Park. Enqueue both stations and mark them as discovered immediately, so another route cannot enqueue either station again. Dequeue Museum and enqueue its unvisited neighbour Library. Then dequeue Park and enqueue Stadium. Every station one connection away entered the queue before any station two connections away, so the algorithm visits closer layers first. This method is called breadth-first search. It finds a path with the fewest connections when every connection has the same cost. Routes with different travel times need a rule that considers those costs.
Message brokers use a related idea between separate programmes. A publisher sends a message to the broker, and a consumer receives it later. The broker may store messages on disk, wait for acknowledgements, redeliver failed work, or distribute messages among several consumers. Those features make its promises more involved than those of our local array. The basic separation remains useful: producers can submit work without performing it themselves.
Capacity and completion order
LinkA fixed circular queue reserves one compact block of slots and makes its memory limit explicit. Its normal operations do not allocate a new piece of memory for each item. The cost is the fixed maximum. A resizable array removes that particular maximum, but one growth operation must allocate new storage and copy every live reference.
A linked queue makes a different trade-off. It allocates one node for each enqueued item. A node stores the item and a reference to the next node. The queue remembers the head node and the tail node. It can grow one node at a time without copying the existing items, but every item needs an extra reference and usually a separate allocation. Both representations can provide constant-time enqueue and dequeue operations. Neither changes the FIFO rule seen by its caller.
FIFO also describes the order in which items leave the queue, not necessarily the order in which work finishes. Suppose one worker dequeues Ava and another worker then dequeues Bo. The queue dispatched Ava first. If Bo’s job is much smaller, Bo may still finish first. Failures and retries can alter visible results further. Strict completion ordering needs more than a FIFO container, often including one consumer and a carefully defined failure policy.
Recap and takeaway
LinkA FIFO queue adds new items at the tail and removes the oldest item from the head. A naive array can preserve that order by shifting every remaining reference after each removal, but the work grows with the queue. A circular array avoids those shifts. It advances head and tail positions through the same storage, wraps them to position 0 at the end, and stores a count to distinguish an empty queue from a full one.
The idea to remember is that queue order comes from the moving head, not from the physical left-to-right order of occupied memory. The implementation may use a circular array, linked nodes, or storage inside a message broker. The FIFO contract still answers the same question: which waiting item should leave next? Capacity, failure handling, and the number of consumers are separate choices that determine what the surrounding system can promise.
Further reading
LinkPython’s data-structures tutorial explains why removing the first item from a list requires shifting the remaining elements. Its deque documentation describes a collection designed for efficient additions and removals at both ends. Java’s Queue interface shows how real interfaces distinguish operations that report empty and full states in different ways. For a distributed example, the RabbitMQ queue guide explains how several producers, consumers, and redeliveries affect the ordering an application observes.