Queues: First In, First Out
A collection where values leave in the order they arrived: enqueue at the back, dequeue at the front. The circular queue keeps the front from drifting off the end of the storage.
What a learner can do afterwards
- Trace a queue through a run of enqueue and dequeue operations
- Give the order the same four values come back out of a queue and out of a stack
- Explain why a print spooler or a network buffer needs arrival order kept
1 · Read
A queue is a line you join at the back and leave from the front. Enqueue adds an item at the rear and dequeue removes the item at the front, so the first thing in is always the first thing out.
To trace a queue, write the line left to right after every operation and cross off from the front only. Try it: enqueue 4, enqueue 7, dequeue, enqueue 9 leaves 7 at the front with 9 behind. Run the same four values through a stack and through a queue and the outputs come back in opposite orders. Dequeueing an empty queue is an error. An editor undo needs newest first, so it uses a stack, not a queue.
A print spooler is a queue: several people send documents at once but the printer prints one page at a time. Each document enqueues at the back and the printer dequeues from the front, so jobs print in arrival order and nobody jumps ahead. When a front job jams, everything behind it waits: cancel the stuck job or restart the spooler and the line flows again in order. Network buffers work the same way, holding bursts so nothing is lost or reordered.
In Python a list can act as a small queue. Removing from the front shifts everything else along, which is fine for learning but slow for huge lines, and that cost is why real programs use a dedicated double ended queue.
First in, first out: join at the back, leave from the front.
The rewritten readings were written for this dataset.
More to read
Following a FIFO queue
Queues preserve arrival order. Enqueue places a new item at the rear; dequeue takes the oldest item from the front. This ordering is called first in, first out, or FIFO.
When tracing operations, draw the front on the left and update the line after each operation. Add on the right and remove on the left. An empty queue has nothing to return. Define how your program handles that situation: it might raise an error, wait for an arrival, or return a sentinel value.
Watching documents wait to print
A print spooler holds documents awaiting printing. Several people can submit work together, but the printer must process jobs in a scheduled order. Under FIFO scheduling, each document joins the rear and the oldest leaves the front. Printer settings can also permit different orders.
Open your computer's print-job window to view waiting documents. A stalled job can delay those behind it. Cancelling or restarting that job may allow the remaining documents to print.
Handling a blocked queue
If a stuck print job blocks later documents, try cancelling it or restarting the spooler. Printing may resume with the remaining order unchanged, though restarting alone may not solve the problem. Queue repairs are not restricted to the front item.
Printer and network buffers hold waiting jobs or data. A FIFO consumer takes the oldest arrival first. Buffering helps absorb bursts, but a full buffer can still lose data. Preserving arrival order gives waiting items a predictable turn.
Trying a queue with a Python list
For a small learning example, use a Python list as a queue. Add items with append and take them out with pop(0). Each front removal shifts the remaining items, making this inefficient for large queues. A dedicated double-ended queue avoids that shifting.
For a hand trace, append puts arrivals at the rear and pop(0) returns the oldest. Put four values into a stack and a queue before removing any. The stack returns them in reverse arrival order; the queue returns them in arrival order.
2 · Watch
به انگلیسیTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.