Difficulty: Beginner | Prerequisites: Basic understanding of arrays and pointers in C.
Queues are one of the foundational data structures in computer science, sitting alongside stacks, linked lists, and trees. Where a stack follows last-in, first-out (LIFO) ordering, a queue follows first-in, first-out (FIFO) ordering, which mirrors how real-world lines work: the first person in line is the first person served. You will encounter queues repeatedly in algorithms (particularly graph traversal), operating systems (process scheduling, print spooling), and networking (packet buffering). If you are comfortable with arrays and basic pointer manipulation, you are ready for this material.
A queue is a linear data structure where elements are added at the rear and removed from the front, preserving FIFO order. The three core operations are enqueue (add), dequeue (remove), and peek (view front without removing). Queues can be implemented with arrays or linked lists, each with different trade-offs around memory use and overflow behaviour.
Queue
A linear data structure that stores elements in first-in, first-out (FIFO) order. Think of it as a queue at a shop: whoever arrives first gets served first.
FIFO (First-In, First-Out)
The access pattern where the earliest-added element is the first to be removed. In simple terms, this means whatever goes in first comes out first.
Enqueue
The operation that adds an element to the rear of the queue. Think of it as joining the back of the line.
Dequeue
The operation that removes and returns the element at the front of the queue. Think of it as the next person in line being served and leaving.
Peek (also: front)
The operation that returns the front element without removing it. In simple terms, this means you look at who is next in line without actually serving them.
Front pointer
An index or pointer that tracks the position of the element to be dequeued next.
Rear pointer
An index or pointer that tracks the position where the next element will be enqueued.
Queue overflow
The condition that occurs when you attempt to enqueue into a full queue (relevant to array-based implementations with fixed capacity).
Queue underflow
The condition that occurs when you attempt to dequeue from an empty queue. Typically results in an error or undefined behaviour.
Linear queue
An array-based queue where elements occupy consecutive positions. Once the rear reaches the end of the array, no further enqueues are possible even if earlier positions have been freed by dequeues.
Circular queue (also: ring buffer)
An array-based queue that wraps the rear index back to 0 when it reaches the end of the array, reusing vacated positions. This solves the wasted-space problem of linear queues.
Push
A stack operation, not a queue operation. This distinction is commonly tested. Stacks use push/pop; queues use enqueue/dequeue.
Enqueue adds an element at the rear. In both array-based and linked list-based implementations, this runs in O(1) time.
Dequeue removes the element at the front. Also O(1) in both implementations.
Peek returns the front element without removal. O(1).
The key constraint is ordering: you cannot remove from the middle or rear. Access is strictly from the front.
Array-based queues use a fixed-size array. They are simple and cache-friendly, but they have a hard capacity limit. Once the array is full, you get overflow. In a linear array queue, dequeued positions at the front are wasted unless you shift all elements (which costs O(n)) or switch to a circular design.
Linked list-based queues allocate each node dynamically with malloc. They grow as needed, so there is no overflow (aside from running out of heap memory). The trade-off is extra memory per element for the pointer, and slightly more complex code to manage node allocation and freeing.
In a linear array queue, front and rear both start at -1. As you enqueue, rear advances. As you dequeue, front advances. Once rear hits the last index, the queue reports overflow even if there are free slots at the beginning.
A circular queue fixes this by wrapping the indices using the modulo operator: rear = (rear + 1) % SIZE. When the rear reaches the end of the array, it wraps around to index 0 if that slot is free. This makes full use of the allocated memory.
Breadth-first search (BFS) in graphs: nodes are explored level by level using a queue.
CPU process scheduling: the OS maintains a ready queue of processes.
Print spooling: documents are printed in the order they were submitted.
Data buffering in streams and I/O: data arrives and is consumed in order.
Queues underpin any system where requests must be handled in arrival order. When you send a document to a printer and it waits behind other jobs, that is a queue. When a web server handles incoming requests, it places them in a queue so none are lost during a traffic spike. BFS, one of the most important graph algorithms, is impossible without a queue to track which nodes to visit next.
Students often confuse queue operations with stack operations. Push and pop belong to stacks. Queues use enqueue and dequeue. Exams test this distinction directly.
Students sometimes assume that a linear array queue can reuse space freed by dequeue. It cannot, unless you implement shifting (expensive) or switch to a circular queue.
A common mistake is forgetting to check for underflow before calling dequeue. Without the check, you risk accessing invalid memory or returning garbage values.
Students sometimes think enqueue in a linked list queue is O(n) because linked lists require traversal. With a rear pointer, enqueue is O(1); no traversal is needed.
⚠️ Know the difference between stack operations (push/pop) and queue operations (enqueue/dequeue). This appears as an MCQ staple.
⚠️ Be able to state the time complexity of enqueue and dequeue for both array and linked list implementations. The answer is O(1) for all four cases.
⚠️ Understand why circular queues exist: they solve the wasted-space problem of linear array queues. Expect a short-answer or fill-in-the-blank on the modulo wrap-around.
⚠️ BFS uses a queue. DFS uses a stack. This application-level question is a frequent exam item.
True or false: A queue follows LIFO ordering.
Fill in the blank: The ______ operation adds an element at the rear of a queue.
True or false: push is a valid queue operation.
Fill in the blank: In a circular queue, the rear wraps around to ______ when it reaches the end of the array.
True or false: Enqueue in a linked list-based queue is O(n).
Answers: 1. False (FIFO). 2. Enqueue. 3. False (push is a stack operation). 4. 0. 5. False (O(1) with a rear pointer).
Q: Which data structure uses FIFO order: stack, queue, tree, or graph?
A: Queue.
Q: What is the time complexity of enqueue in a linked list-based queue?
A: O(1), because the rear pointer gives direct access to the insertion point.
Q: What happens when you try to dequeue from an empty queue?
A: Queue underflow occurs, which typically results in an error or undefined behaviour. A well-written implementation should check for this condition and return an error value.
Q: Why is a circular queue preferred over a linear queue in an array implementation?
A: A circular queue avoids wasted space by wrapping the rear index around to reuse positions vacated by earlier dequeues. A linear queue cannot reclaim that space without shifting elements.
Q: What is the role of the front and rear pointers in a queue?
A: front points to the element that will be dequeued next. rear points to the position where the next element will be enqueued.
Q: What is the difference between array-based and linked list-based queue implementations?
A: Array-based queues have a fixed size and may overflow when full. Linked list-based queues are dynamic, allocating memory per node, and grow as needed (no overflow under normal conditions).
This material connects directly to graph algorithms: BFS, covered later in the course, relies entirely on a queue to manage its frontier of nodes. Queues also relate to stacks (the other fundamental linear data structure), and understanding both side by side helps clarify when to use FIFO vs LIFO ordering. If you go on to study operating systems, you will see queues everywhere in process scheduling, I/O buffering, and inter-process communication.
queue, FIFO, first-in first-out, enqueue, dequeue, peek, front pointer, rear pointer, circular queue, ring buffer, linear queue, queue overflow, queue underflow, array-based queue, linked list queue, BFS, breadth-first search, data structures, C programming, CS101, UCF Computer Science I