Arrays & Linear Structures

queue

A queue is a line at a shop: people join at the back and get served from the front, in the order they arrived. Whatever goes in first comes out first — this is FIFO, first in, first out, the opposite of a stack. The two core moves are enqueue (add to the back) and dequeue (remove from the front); front lets you peek at who is next.

Done well, both ends are O(1). A naive version on a plain array would dequeue by shifting everything forward (O(n)); the usual fix is a circular buffer, where a front and back index wrap around the array so neither end ever has to shift. A doubly linked list also gives O(1) at both ends. In C++ you would reach for std::queue, which wraps a deque.

Queues model fairness and order. They drive task and print schedulers, message pipelines and buffers between a fast producer and a slow consumer, and — crucially — breadth-first search, which uses a queue to visit a graph layer by layer.

#include <queue>
std::queue<int> q;
q.push(1); q.push(2); q.push(3);
//  front [ 1 | 2 | 3 ] back
int f = q.front();  // 1   (peek, O(1))
q.pop();            // removes 1 from the front, O(1)
// now front() == 2

FIFO order; enqueue and dequeue are both O(1).

Stack is LIFO, queue is FIFO — remembering this one pairing unlocks half of when to use which.

Also called

FIFOFIFO queue队列佇列先進先出