Difficulty: Beginner | Prerequisites: Basic data structures concept, arrays
A queue is one of the foundational abstract data types in computer science. It models any situation where things wait in line: print jobs, web server requests, streaming data buffers. This material covers three variants, each suited to different problems: simple (FIFO) queues, priority queues, and circular queues. Knowing which type fits which scenario is a standard exam question, and the reasoning behind each choice matters more than memorising the names.
A simple queue is first-in, first-out, like a checkout line. A priority queue serves elements by importance rather than arrival order, which is useful for calculators and scheduling. A circular queue wraps around to reuse freed space, making it ideal for continuous data buffers. The exam will ask you to match queue types to real-world scenarios and explain why.
Queue
An abstract data type representing an ordered collection of elements where insertion happens at the back (enqueue) and removal happens at the front (dequeue). Think of it as a queue at a shop: you join at the back and leave from the front.
FIFO (First-In, First-Out)
The ordering principle of a simple queue: the element that has been waiting longest is served first. In simple terms, first come, first served.
Simple queue (linear queue)
A basic queue that follows strict FIFO ordering. Elements are added at the rear and removed from the front, with no re-ordering or jumping the line.
Priority queue
A queue variant where each element has an associated priority, and elements are served in priority order rather than arrival order. Think of it as an A&E department: the most urgent patient is seen first, regardless of who arrived when.
Circular queue (ring buffer)
A queue variant where the last position wraps around to connect to the first, forming a logical circle. When space is freed at the front, new elements can fill it without shifting the entire queue. Think of it as a revolving sushi belt: plates go round and round, and empty spots get refilled.
Enqueue
The operation of adding an element to the back of a queue.
Dequeue
The operation of removing an element from the front of a queue.
Elements enter at the back and leave at the front.
No element can skip ahead.
Best use: any scenario where fairness (processing order = arrival order) is the priority.
When to use it: A printer queue. Print jobs should be processed in the order they were submitted. No job is more important than another, so strict FIFO is the fair and logical choice.
Each element carries a priority value.
The element with the highest priority is dequeued first, regardless of when it was added.
If two elements share the same priority, FIFO typically breaks the tie.
When to use it: A calculator's expression stack. When evaluating mathematical expressions with multiple operators, operator precedence (PEMDAS/BODMAS) determines which operation happens first. A priority queue lets you process higher-precedence operators before lower ones, even if the lower-precedence operator appeared first in the expression.
Internally uses a fixed-size array, but the front and rear pointers wrap around.
When an element is dequeued from the front, that space becomes available for future enqueues without needing to shift all remaining elements.
Avoids the "phantom full" problem of linear queues, where the queue appears full because the rear has reached the end of the array, even though space exists at the front.
When to use it: A data buffer for continuous data collection (e.g. streaming sensor data, audio buffering). Data flows in constantly and old data is consumed and discarded. A circular queue reuses freed memory efficiently, so the buffer never needs to be resized or shifted.
Why circular over simple for buffering: In a simple queue, once the rear pointer reaches the end of the array, you either shift all elements forward (expensive) or declare the queue full (wasteful). A circular queue simply wraps the rear pointer to the front, using space freed by earlier dequeues. This is the key advantage: efficient memory utilisation without element shifting.
Operating systems use priority queues to schedule processes (high-priority system tasks run before low-priority background jobs). Network routers use simple FIFO queues for packet processing. Audio and video streaming applications use circular buffers to maintain a steady flow of data without allocating new memory for every frame.
"A priority queue is just a sorted list." A priority queue is an abstract data type; it can be implemented with a heap, a sorted array, or other structures. The point is the interface (highest priority out first), not the internal arrangement.
"Circular queues have unlimited capacity." They still have a fixed size. The advantage is that they reuse vacated space, not that they grow without bound.
"Simple queues are always the right default." When processing order should not match arrival order (e.g. urgent tasks, operator precedence), a simple queue is the wrong tool.
"A stack and a queue are the same thing." A stack is LIFO (last-in, first-out); a queue is FIFO. They have opposite removal orders.
⚠️ "Which type of queue for a printer?" – Simple / FIFO. Know why: fairness, no job has higher priority.
⚠️ "Which type of queue for a calculator?" – Priority. Know why: operator precedence (PEMDAS).
⚠️ "Which type of queue for a continuous data buffer?" – Circular. Know why: efficient memory reuse, wrapping pointers.
⚠️ Be ready to explain the reasoning, not just name the queue type. Exam answers require complete sentences with justification.
Fill in the blank: A queue that follows the principle "first come, first served" is called a ___ queue. Answer: Simple (or FIFO).
True or false: A circular queue can reuse space freed by dequeued elements without shifting the remaining elements. Answer: True.
Fill in the blank: In a priority queue, the element removed first is the one with the highest ___. Answer: Priority.
Q: When implementing a printer queue, which type of queue would work most fairly, and why?
A: A simple (FIFO) queue. Print jobs should be processed in the order they arrive, and no job needs to jump ahead of another, so first-in, first-out ordering is the fairest approach.
Q: Why is a priority queue a good fit for a calculator's expression evaluation?
A: Calculators must respect operator precedence (PEMDAS). A priority queue lets higher-precedence operators (e.g. multiplication) be processed before lower-precedence ones (e.g. addition), even if the lower-precedence operator appeared earlier in the expression.
Q: What is the main advantage of a circular queue over a simple queue for buffering continuous data?
A: A circular queue wraps around to reuse space freed by dequeued elements, so memory is used efficiently without needing to shift elements or resize the buffer.
Q: What is a queue, and what are some of its best uses?
A: A queue is a collection of ordered elements where items are inserted at the back and removed from the front (FIFO). Common uses include modelling waiting lines (supermarket checkouts, printer queues), task scheduling, and buffering data streams.
Queues connect to linked lists, because a linked list is a common underlying implementation for queues (each node points to the next in line). Priority queues connect to heaps, a tree-based data structure you may encounter later. Stacks are the LIFO counterpart to queues and are covered in the linked lists and stacks notes.
queue, FIFO, first-in first-out, simple queue, linear queue, priority queue, circular queue, ring buffer, enqueue, dequeue, buffer, data structure, PEMDAS, operator precedence, memory utilisation, APCS queues, abstract data type