Queue

A queue is a FIFO (first-in, first-out) data structure: elements are added at one end and removed from the other. The two core operations are enqueue (add at the back) and dequeue (remove from the front). Like a line at a coffee shop — first to arrive is first to be served.

Operations:

• enqueue(item) — add an item to the back/tail.
• dequeue() — remove the item at the front/head.
• peek() / getFront() — read the front item without removing.
• isEmpty() / isFull() — state queries.

The queue maintains two pointers: front (head, where dequeue happens) and end (tail, where enqueue happens).

Use cases

FIFO order matches:

• Task scheduling — process requests in arrival order.
• Print queues — print jobs in submission order.
• BFS traversal — see Breadth-first search; the queue holds the next vertices to visit.
• Buffering — producer adds at one end, consumer removes from the other (with synchronization).
• Operating system scheduling — many OS schedulers use queues for ready/waiting processes.

Implementation 1: linked list

Use a singly linked list with both head and tail pointers. Enqueue appends a node at the tail; dequeue removes from the head:

struct item {
    int value;
    struct item *next;
};
struct item *front = NULL;
struct item *end   = NULL;
 
void enqueue(int n) {
    struct item *pnew = malloc(sizeof(struct item));
    pnew->value = n;
    pnew->next  = NULL;
    if (end != NULL) {
        end->next = pnew;
    }
    end = pnew;
    if (front == NULL) {     // empty queue → set front
        front = pnew;
    }
}
 
bool dequeue(int *n) {
    if (front == NULL) return false;
    struct item *temp = front;
    *n    = front->value;
    front = front->next;
    if (front == NULL) end = NULL;   // queue is now empty
    free(temp);
    return true;
}

Both operations are O(1). Capacity is unbounded (limited by available memory).

Implementation 2: circular array

A naive array implementation runs into a problem: as you dequeue from the front, the array’s “used” region drifts toward the right end. Eventually you can’t enqueue even though the front of the array is empty.

The fix: circular indexing. Use modulo arithmetic to wrap around when you reach the end:

#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = 0, end = 0, count = 0;
 
bool enqueue(int n) {
    if (count == MAX_SIZE) return false;   // full
    queue[end] = n;
    end = (end + 1) % MAX_SIZE;
    count++;
    return true;
}
 
bool dequeue(int *n) {
    if (count == 0) return false;          // empty
    *n = queue[front];
    front = (front + 1) % MAX_SIZE;
    count--;
    return true;
}

When end reaches MAX_SIZE - 1, the next increment wraps it to 0. Same for front. The count variable disambiguates “empty” from “full” — both states have front == end if you only track front and end, so the count makes the distinction explicit.

Pros of array-based: contiguous memory, no per-element malloc overhead.

Cons: fixed capacity. Bigger queues need a bigger pre-allocated array, or fall back to linked-list.

Comparison with stack

Property	Stack	Queue
Order	LIFO	FIFO
Add at	Top	Tail
Remove from	Top	Head
Use case	Reversal, recursion, undo	Scheduling, BFS, buffering

A stack handles the most recently added; a queue handles the longest waiting. Pick based on which the problem calls for.

For the version with both ends accessible, see Deque. For variations where elements have priorities, see Priority queue / Heap (data structure).