Data Structures

Circular Queue

A fixed-size queue can wrap its head and tail indexes around the array.

tail wrap Modulo arithmetic moves the tail back to zero after the final slot.
first out Reading from the head removes the oldest queued value first.

Circular Queue

count
circular_queue.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int count = 3;
    int queue[4] = {0, 0, 0, 0};
    int head = 0;
    int tail = 0;

    for (int i = 0; i < count; i++) {
        queue[tail] = (i + 1) * 10;
        tail = (tail + 1) % 4;
    }

    int first = queue[head];
    head = (head + 1) % 4;
    int second = queue[head];

    printf("first=%d second=%d tail=%d\n", first, second, tail);
    return 0;
}

#include <stdio.h>

int main(void) {
    int count = 2;
    int queue[4] = {0, 0, 0, 0};
    int head = 0;
    int tail = 0;

    for (int i = 0; i < count; i++) {
        queue[tail] = (i + 1) * 10;
        tail = (tail + 1) % 4;
    }

    int first = queue[head];
    head = (head + 1) % 4;
    int second = queue[head];

    printf("first=%d second=%d tail=%d\n", first, second, tail);
    return 0;
}

#include <stdio.h>

int main(void) {
    int count = 4;
    int queue[4] = {0, 0, 0, 0};
    int head = 0;
    int tail = 0;

    for (int i = 0; i < count; i++) {
        queue[tail] = (i + 1) * 10;
        tail = (tail + 1) % 4;
    }

    int first = queue[head];
    head = (head + 1) % 4;
    int second = queue[head];

    printf("first=%d second=%d tail=%d\n", first, second, tail);
    return 0;
}

  1. count ← 3, queue ← ⟨addr A⟩, head ← 0, tail ← 0

    3int main(void) {4    int count→ 3 = 3; //@count=2, 45    int queue→ ⟨addr A⟩[4] = {0, 0, 0, 0};6    int head→ 0 = 0;7    int tail→ 0 = 0;

  2. queue[tail] ← 10, tail ← 1

    pass 1 of 3
    9for (int i0 = 0; i < count3; i++) {10    queue[tail]→ 10 = (i0 + 1) * 10;11    tail→ 1 = (tail + 1) % 4;12}
    All 3 passes — pass 1 is the card above
    passiqueue[tail]tail
    100 → 100 → 1
    210 → 201 → 2
    320 → 302 → 3

  3. first ← 10, head ← 1, second ← 20

    14    int first→ 10 = queue[head]10;15    head→ 1 = (head + 1) % 4;16    int second→ 20 = queue[head]20;1718    printf("first=%d second=%d tail=%d\n", first10, second20, tail3);19    return 0;20}
    outputfirst=10 second=20 tail=3

  1. count ← 2, queue ← ⟨addr A⟩, head ← 0, tail ← 0

    3int main(void) {4    int count→ 2 = 2;5    int queue→ ⟨addr A⟩[4] = {0, 0, 0, 0};6    int head→ 0 = 0;7    int tail→ 0 = 0;

  2. queue[tail] ← 10, tail ← 1

    pass 1 of 2
    9for (int i0 = 0; i < count2; i++) {10    queue[tail]→ 10 = (i0 + 1) * 10;11    tail→ 1 = (tail + 1) % 4;12}

  3. queue[tail] ← 20, tail ← 2

    pass 2 of 2
    9for (int i1 = 0; i < count2; i++) {10    queue[tail]→ 20 = (i1 + 1) * 10;11    tail→ 2 = (tail + 1) % 4;12}

  4. first ← 10, head ← 1, second ← 20

    14    int first→ 10 = queue[head]10;15    head→ 1 = (head + 1) % 4;16    int second→ 20 = queue[head]20;1718    printf("first=%d second=%d tail=%d\n", first10, second20, tail2);19    return 0;20}
    outputfirst=10 second=20 tail=2

  1. count ← 4, queue ← ⟨addr A⟩, head ← 0, tail ← 0

    3int main(void) {4    int count→ 4 = 4;5    int queue→ ⟨addr A⟩[4] = {0, 0, 0, 0};6    int head→ 0 = 0;7    int tail→ 0 = 0;

  2. queue[tail] ← 10, tail ← 1

    pass 1 of 4
    9for (int i0 = 0; i < count4; i++) {10    queue[tail]→ 10 = (i0 + 1) * 10;11    tail→ 1 = (tail + 1) % 4;12}
    All 4 passes — pass 1 is the card above
    passiqueue[tail]tail
    100 → 100 → 1
    210 → 201 → 2
    320 → 302 → 3
    430 → 403 → 0

  3. first ← 10, head ← 1, second ← 20

    14    int first→ 10 = queue[head]10;15    head→ 1 = (head + 1) % 4;16    int second→ 20 = queue[head]20;1718    printf("first=%d second=%d tail=%d\n", first10, second20, tail0);19    return 0;20}
    outputfirst=10 second=20 tail=0