Queue using dynamic array

A dynamic-array queue starts like a circular array queue, but grows when full. This keeps enqueue/dequeue O(1) amortized while avoiding fixed-capacity limits.

1) Representation

2) Growth idea

When size == capacity, allocate a new array with double capacity, copy elements in queue order (front forward, wrapping as needed), then reset front = 0.

3) Example in C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int* arr;        // Dynamic array
    int front;       // Front index (points to first element)
    int rear;        // Rear index (points to last element)
    int capacity;    // Current capacity
    int size;        // Number of elements
} Queue;

// Function to create a new queue
Queue* createQueue(int initialCapacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->capacity = initialCapacity;
    q->front = -1;
    q->rear = -1;
    q->size = 0;
    q->arr = (int*)malloc(q->capacity * sizeof(int));
    return q;
}

// Function to check if queue is empty
int isEmpty(Queue* q) {
    return q->size == 0;
}

// Function to check if queue is full
int isFull(Queue* q) {
    return q->size == q->capacity;
}

// Function to resize the array (double capacity)
void resize(Queue* q) {
    int newCapacity = q->capacity * 2;
    int* newArr = (int*)malloc(newCapacity * sizeof(int));

    // Copy elements in order (front to rear)
    for (int i = 0; i < q->size; i++) {
        newArr[i] = q->arr[q->front + i];
    }

    // Update queue properties
    free(q->arr);
    q->arr = newArr;
    q->front = 0;
    q->rear = q->size - 1;
    q->capacity = newCapacity;

    printf("Queue resized! New capacity: %d\n", newCapacity);
}

// Function to add element (Enqueue)
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full! Resizing...\n");
        resize(q);
    }

    if (isEmpty(q)) {
        q->front = 0;  // First element
    }

    q->rear++;
    q->arr[q->rear] = value;
    q->size++;
    printf("Enqueued: %d (Size: %d/%d, Front: %d, Rear: %d)\n",
           value, q->size, q->capacity, q->front, q->rear);
}

// Function to remove element (Dequeue)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Queue is empty\n");
        return -1;
    }

    int value = q->arr[q->front];
    q->front++;
    q->size--;

    printf("Dequeued: %d (Size: %d/%d, Front: %d, Rear: %d)\n",
           value, q->size, q->capacity, q->front, q->rear);

    // Reset queue if becomes empty
    if (q->size == 0) {
        q->front = -1;
        q->rear = -1;
        printf("Queue is now empty, reset to initial state\n");
    }

    // Optional: Shrink array if size becomes too small
    if (q->size > 0 && q->size <= q->capacity / 4 && q->capacity > 4) {
        int newCapacity = q->capacity / 2;
        int* newArr = (int*)malloc(newCapacity * sizeof(int));

        for (int i = 0; i < q->size; i++) {
            newArr[i] = q->arr[q->front + i];
        }

        free(q->arr);
        q->arr = newArr;
        q->front = 0;
        q->rear = q->size - 1;
        q->capacity = newCapacity;
        printf("Queue shrunk! New capacity: %d\n", newCapacity);
    }

    return value;
}

// Function to get front element without removing
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->arr[q->front];
}

// Function to display all elements
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }

    printf("Queue elements (front -> rear): ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->arr[i]);
    }
    printf("\n");
}

// Function to show memory layout
void showMemoryLayout(Queue* q) {
    printf("\n=== Memory Layout ===\n");
    printf("Capacity: %d\n", q->capacity);
    printf("Size: %d\n", q->size);
    printf("Front index: %d\n", q->front);
    printf("Rear index: %d\n", q->rear);

    printf("Array contents: [");
    for (int i = 0; i < q->capacity; i++) {
        if (i >= q->front && i <= q->rear) {
            printf(" %d ", q->arr[i]);
        } else if (i < q->front && q->front != -1) {
            printf(" X ");  // Wasted space (dequeued elements)
        } else {
            printf(" _ ");  // Empty space
        }
    }
    printf("]\n");
    printf("(X = Dequeued but space not reused, _ = Never used)\n\n");
}

// Function to get current size
int getSize(Queue* q) {
    return q->size;
}

// Function to get current capacity
int getCapacity(Queue* q) {
    return q->capacity;
}

// Function to free memory
void freeQueue(Queue* q) {
    free(q->arr);
    free(q);
}

// Main function to test simple linear queue
int main() {
    printf("=== Simple Linear Queue (Non-Circular) ===\n");
    printf("Note: Once elements are dequeued, their space is WASTED!\n");
    printf("Front index only moves forward, never wraps around.\n\n");

    Queue* q = createQueue(4);

    // Enqueue elements
    printf("--- Enqueuing elements ---\n");
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    enqueue(q, 40);
    display(q);
    showMemoryLayout(q);

    // Dequeue some elements (creates wasted space)
    printf("--- Dequeuing elements (creates wasted space) ---\n");
    dequeue(q);
    dequeue(q);
    display(q);
    showMemoryLayout(q);

    // Try to add more elements (will resize)
    printf("--- Adding more elements (triggers resize) ---\n");
    enqueue(q, 50);
    enqueue(q, 60);
    display(q);
    showMemoryLayout(q);

    // Show that wasted space is NOT reused
    printf("--- Notice: Wasted space (X) is still there! ---\n");
    printf("The queue only moves front forward, never wraps.\n\n");

    // Remove all elements
    printf("--- Removing all elements ---\n");
    while (!isEmpty(q)) {
        dequeue(q);
    }
    display(q);

    // Add new elements after empty
    printf("\n--- Adding new elements after queue became empty ---\n");
    enqueue(q, 100);
    enqueue(q, 200);
    display(q);
    showMemoryLayout(q);

    // Free memory
    freeQueue(q);

    return 0;
}

Output

=== Simple Linear Queue (Non-Circular) ===
Note: Once elements are dequeued, their space is WASTED!
Front index only moves forward, never wraps around.

--- Enqueuing elements ---
Enqueued: 10 (Size: 1/4, Front: 0, Rear: 0)
Enqueued: 20 (Size: 2/4, Front: 0, Rear: 1)
Enqueued: 30 (Size: 3/4, Front: 0, Rear: 2)
Enqueued: 40 (Size: 4/4, Front: 0, Rear: 3)
Queue elements (front -> rear): 10 20 30 40

=== Memory Layout ===
Capacity: 4
Size: 4
Front index: 0
Rear index: 3
Array contents: [ 10  20  30  40 ]
(X = Dequeued but space not reused, _ = Never used)

--- Dequeuing elements (creates wasted space) ---
Dequeued: 10 (Size: 3/4, Front: 1, Rear: 3)
Dequeued: 20 (Size: 2/4, Front: 2, Rear: 3)
Queue elements (front -> rear): 30 40

=== Memory Layout ===
Capacity: 4
Size: 2
Front index: 2
Rear index: 3
Array contents: [ X  X  30  40 ]
(X = Dequeued but space not reused, _ = Never used)

--- Adding more elements (triggers resize) ---
Queue is full! Resizing...
Queue resized! New capacity: 8
Enqueued: 50 (Size: 3/8, Front: 0, Rear: 2)
Enqueued: 60 (Size: 4/8, Front: 0, Rear: 3)
Queue elements (front -> rear): 30 40 50 60

=== Memory Layout ===
Capacity: 8
Size: 4
Front index: 0
Rear index: 3
Array contents: [ 30  40  50  60  _  _  _  _ ]
(X = Dequeued but space not reused, _ = Never used)

--- Notice: Wasted space (X) is still there! ---
The queue only moves front forward, never wraps.

--- Removing all elements ---
Dequeued: 30 (Size: 3/8, Front: 1, Rear: 3)
Dequeued: 40 (Size: 2/8, Front: 2, Rear: 3)
Dequeued: 50 (Size: 1/8, Front: 3, Rear: 3)
Dequeued: 60 (Size: 0/8, Front: 4, Rear: 3)
Queue is now empty, reset to initial state
Queue is empty

--- Adding new elements after queue became empty ---
Enqueued: 100 (Size: 1/8, Front: 0, Rear: 0)
Enqueued: 200 (Size: 2/8, Front: 0, Rear: 1)
Queue elements (front -> rear): 100 200

=== Memory Layout ===
Capacity: 8
Size: 2
Front index: 0
Rear index: 1
Array contents: [ 100  200  _  _  _  _  _  _ ]
(X = Dequeued but space not reused, _ = Never used)

Key Characteristics of Simple Linear Queue

4) Complexity

• enqueue: O(1) amortized, O(n) on grow steps.
• dequeue: O(1).
• space: O(n).