Queues and Stacks - osvaldoandrade/ova-lib GitHub Wiki

Queues and Stacks

Read this page when removal order is fixed by policy: first-in first-out for queues or last-in first-out for stacks.

Queues

The queue constructor is:

queue *create_queue(queue_type type, int capacity, comparator compare);

The shared queue method table is:

Field	Meaning
`enqueue(self, data)`	inserts one item and returns `1` on success, `0` on allocation failure
`dequeue(self)`	removes and returns one item or `NULL`
`is_empty(self)`	returns whether the queue has no items
`size(self)`	returns the current count
`free(self)`	frees queue storage

`QUEUE_TYPE_NORMAL`

QUEUE_TYPE_NORMAL is a linked FIFO queue.

The capacity argument is ignored on this path. enqueue appends at the rear. dequeue removes from the front. dequeue on an empty queue returns NULL.

Use it when arrival order is the only removal rule that matters.

`QUEUE_TYPE_PRIORITY`

QUEUE_TYPE_PRIORITY is a priority queue backed by the binary heap implementation.

The capacity argument is passed to that heap. The comparator decides which item is removed first. With the shipped binary heap, an item outranks another item when cmp(a, b) > 0.

That means an integer comparator such as:

return (lhs > rhs) - (lhs < rhs);

makes larger integers leave first.

If you need handle-based key updates, this wrapper is not enough. Move to Heaps-and-Priority-Queues and use the heap API directly.

Stacks

The stack constructor is:

stack *create_stack(StackType type);

The shared stack method table is:

Field	Meaning
`push(self, item)`	pushes one item
`pop(self)`	removes and returns the top item or `NULL`
`top(self)`	returns the current top item or `NULL`
`is_empty(self)`	returns whether the stack has no items
`size(self)`	returns the current count
`free(self)`	frees stack storage

`ARRAY_STACK`

ARRAY_STACK is implemented on top of an array list. Push and pop happen at the tail.

Use it when you want LIFO behavior and the array-backed growth rule is acceptable.

`LINKED_STACK`

LINKED_STACK is implemented on top of a linked list. Push and pop happen at the head.

Use it when you want LIFO behavior with linked storage instead of array storage.

Empty-Case Behavior

queue->dequeue, stack->pop, and stack->top return NULL on empty structures.

queue->is_empty and stack->is_empty are the fast guard before removal.

Ownership and Cleanup

Queues and stacks store payload pointers only. They do not free the pointed-to objects.

Destroy them with queue->free(queue) or stack->free(stack). Free user payloads in your own code when your program owns them.

Example

#include "queue.h"

int main(void) {
    queue *jobs = create_queue(QUEUE_TYPE_NORMAL, 0, NULL);
    int a = 1;
    int b = 2;

    jobs->enqueue(jobs, &a);
    jobs->enqueue(jobs, &b);

    int *first = (int *)jobs->dequeue(jobs);
    jobs->free(jobs);
    return first && *first == 1 ? 0 : 1;
}