C DSA Queues

What is a Queue?

A queue is a data structure where you add items at the back (the rear) and remove items from the front.

The first item you add is the first item you remove. This rule is called FIFO (First In, First Out).

Queues are used whenever things must wait their turn:

• A printer prints documents in the order they were sent.
• The letters you type on a keyboard are handled in the order you typed them.
• In many games, players take turns in a fixed order.

Queue Operations

A queue has a few basic operations:

Try it! In C, we build a queue with an array. Enqueue adds a value at the rear, and dequeue removes the value at the front:

The yellow box is the front of the queue: the next value to leave. Dequeue a few values, then enqueue some more. Watch rear jump from the end of the array back to index 0! You will learn why in the circular queue section below.

Create a Queue With an Array

Like a stack, a queue can be built with an array. But a queue needs two index variables:

• front - the index of the first item (the next one to leave)
• rear - the index of the last item (the one that joined last)

#include <stdio.h>

int main() {
  int queue[5];
  int front = 0;  // Index of the first item
  int rear = -1;  // Index of the last item

  // Enqueue 10, 20 and 30 (add at the rear)
  rear++;
  queue[rear] = 10;
  rear++;
  queue[rear] = 20;
  rear++;
  queue[rear] = 30;

  // Dequeue (remove from the front)
  printf("Dequeued: %d\n", queue[front]);
  front++;

  printf("Front item now: %d\n", queue[front]);

  return 0;
}

Dequeued: 10
Front item now: 20

Compare this with the stack: we added 10, 20, 30 in both cases. The stack gave us 30 first. The queue gives us 10 first.

Reuse Empty Spots: The Circular Queue

The simple queue above has a problem. front and rear only move forward.

Imagine a queue with room for 5 items. You add 5 items, then remove 2. Now there are 2 free spots at the start of the array. But rear is already at the end, so you cannot add anything!

The fix: when an index reaches the end of the array, send it back to 0. Like the hand of a clock that goes from 12 back to 1. This is called a circular queue.

The modulus operator (%) does this for us:

rear = (rear + 1) % MAX;

With MAX set to 5, rear moves like this:

We also keep a count of the items, so we always know if the queue is full or empty:

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = 0;
int rear = -1;
int count = 0; // Number of items in the queue

void enqueue(int value) {
  if (count == MAX) {
    printf("Queue is full!\n");
    return;
  }
  rear = (rear + 1) % MAX;
  queue[rear] = value;
  count++;
}

int dequeue() {
  if (count == 0) {
    printf("Queue is empty!\n");
    return -1;
  }
  int value = queue[front];
  front = (front + 1) % MAX;
  count--;
  return value;
}

int peek() {
  if (count == 0) {
    printf("Queue is empty!\n");
    return -1;
  }
  return queue[front];
}

// Returns 1 (true) if the queue is empty
int isEmpty() {
  return count == 0;
}

int main() {
  enqueue(10);
  enqueue(20);
  enqueue(30);

  printf("Front item: %d\n", peek());

  // Dequeue items until the queue is empty
  while (!isEmpty()) {
    printf("Dequeued: %d\n", dequeue());
  }

  return 0;
}

Front item: 10
Dequeued: 10
Dequeued: 20
Dequeued: 30

Example Explained

• enqueue() checks if the queue is full. If not, it moves rear one step (wrapping around with %) and stores the value there.
• dequeue() checks if the queue is empty. If not, it takes the value at front and moves front one step.
• count goes up with every enqueue and down with every dequeue.

We added 10, 20, 30, and got them back as 10, 20, 30. First in, first out!

Real-Life Example: Take Turns

Three players play a game. The player at the front of the queue plays a turn, then goes to the back of the queue.

The queue only has room for 3 players, but the game can go on forever. The circular queue reuses the empty spot every time:

#include <stdio.h>
#define MAX 3

int queue[MAX];
int front = 0;
int rear = -1;
int count = 0;

void enqueue(int value) {
  if (count == MAX) {
    printf("Queue is full!\n");
    return;
  }
  rear = (rear + 1) % MAX;
  queue[rear] = value;
  count++;
}

int dequeue() {
  if (count == 0) {
    printf("Queue is empty!\n");
    return -1;
  }
  int value = queue[front];
  front = (front + 1) % MAX;
  count--;
  return value;
}

int main() {
  // Three players join the game
  enqueue(1);
  enqueue(2);
  enqueue(3);

  // Play 7 turns
  for (int turn = 1; turn <= 7; turn++) {
    int player = dequeue(); // The player at the front plays
    printf("Turn %d: Player %d\n", turn, player);
    enqueue(player);        // Then goes to the back of the queue
  }

  return 0;
}

Turn 1: Player 1
Turn 2: Player 2
Turn 3: Player 3
Turn 4: Player 1
Turn 5: Player 2
Turn 6: Player 3
Turn 7: Player 1

Run the simulation below to see how the code above works, one step at a time. Watch front and rear go back to index 0 when they reach the end of the array:

Summary

• A queue adds items at the rear and removes them from the front: First In, First Out (FIFO).
• enqueue adds an item, dequeue removes an item, and peek looks at the front item.
• You can build a queue with an array and two indexes: front and rear.
• A circular queue uses % to reuse empty spots in the array.

Our stacks and queues have a fixed size (MAX). What if you do not know how many items you will need? A linked list can grow while the program runs. That is the next chapter!