A queue is a very basic and commonly used data structure, whose core feature is “First In First Out” (FIFO). Imagine queuing to check out at a supermarket: the first person checks out and leaves first, followed by the second person. This is a typical scenario of a queue—those who arrive earlier are at the front and get processed first.
一、Basic Concepts of a Queue¶
- Queue: A data structure that follows the “FIFO” principle, where elements can only be added at one end (the rear) and removed from the other end (the front).
- Front: The first element of the queue, which is the earliest element to enter.
- Rear: The last element of the queue, which is the latest element to enter.
- Basic Operations:
- Enqueue: Add a new element to the rear of the queue.
- Dequeue: Remove and retrieve the element from the front of the queue.
二、How to Implement a Queue? (Using an Array as an Example)¶
To simply understand queue implementation, we can simulate a queue with a fixed-size array. Two key variables are needed:
- front: Points to the front of the queue (the first element), initialized to 0.
- rear: Points to the rear of the queue (the last element), initialized to 0.
- Array arr: Stores queue elements, with a capacity of max_size (e.g., 5).
Core Rules:¶
- Empty Queue Condition:
front == rear(the queue is empty with no elements). - Full Queue Condition:
rear == max_size(the queue is full and no more elements can be enqueued). - Enqueue Logic: Place the element at
arr[rear], then incrementrear. - Dequeue Logic: Retrieve
arr[front], then incrementfront.
三、Example Demonstration: Simulating “Enqueue” and “Dequeue”¶
Assume the queue capacity is 5. Initially, front=0, rear=0, and the array is empty.
Step 1: Enqueue 1, 2, 3¶
- Enqueue 1:
arr[0] = 1,rear=1→ Queue:[1] - Enqueue 2:
arr[1] = 2,rear=2→ Queue:[1, 2] - Enqueue 3:
arr[2] = 3,rear=3→ Queue:[1, 2, 3]
Step 2: Dequeue 1, then Enqueue 4¶
- Dequeue 1: Retrieve
arr[front=0],front=1→ Queue:[2, 3] - Enqueue 4:
arr[3] = 4,rear=4→ Queue:[2, 3, 4]
Step 3: Enqueue 5, then Dequeue 2¶
- Enqueue 5:
arr[4] = 5,rear=5→ Queue:[2, 3, 4, 5](the queue is now full and no more enqueues are allowed) - Dequeue 2: Retrieve
arr[front=1],front=2→ Queue:[3, 4, 5]
At this point, the remaining elements in the queue are 3, 4, 5, with front=2 and rear=5. The queue is neither empty nor full.
四、Applications of Queues¶
Queues are widely used in programming and real-world scenarios, such as:
- Task Scheduling: The “task queue” in operating systems (e.g., new tasks wait in line for CPU processing).
- Breadth-First Search (BFS): Traversing nodes level by level in trees or graphs (similar to “processing layer by layer”).
- Printer Queue: Documents submitted first are printed first.
- Network Requests: Simultaneously requested resources are processed in order in the queue during web page loading.
五、Summary¶
The core of a queue is “FIFO”. It can be easily implemented using arrays, linked lists, or other structures. The key to understanding a queue is remembering: elements are added at the rear and removed from the front, always maintaining the order of “earlier arrivals get processed first”. This simple rule enables queues to play a vital role in data processing, task scheduling, and other scenarios.