Deque

Read this page when you need both ends of the sequence to be first-class operations and you still want indexed reads.

Constructor and API

The deque constructor is:

deque *create_deque(int capacity);

The public API is method-table based:

Field	Meaning
push_front	inserts one element at the front
push_back	inserts one element at the back
pop_front	removes and returns the front element or NULL
pop_back	removes and returns the back element or NULL
peek_front	returns the front element or NULL
peek_back	returns the back element or NULL
get	returns the element at a logical index or NULL
size	returns the current count
is_empty	returns whether the deque is empty
free	frees deque storage

Storage Model

The deque is a circular buffer with dynamic growth.

If capacity <= 0, construction falls back to 16.

When the buffer fills, capacity doubles and the stored pointers are rewritten into logical order.

That gives 3 properties that matter to callers:

Front and back operations are direct.

Indexed reads through get are direct by logical position, not by physical slot.

Wrap-around is an internal detail. The logical order seen by get, peek, and pop stays consistent after wrap-around and after resize.

Boundary Behavior

pop_front, pop_back, peek_front, and peek_back return NULL when the deque is empty.

get returns NULL for negative indices, indices greater than or equal to the current size, or a NULL deque.

d->size(d) returns 0 for an empty deque.

d->is_empty(d) returns true for an empty deque.

The shipped tests also exercise NULL safety for the mutating API. d->push_front(d, ...), d->push_back(d, ...), and d->free(d) do not crash.

Ownership and Cleanup

The deque stores pointers and never frees the pointed-to payloads.

Destroy the deque with d->free(d). Free user payloads in your own code when your program owns them.

When to Prefer a Deque

Use a deque instead of a queue when you need both front and back operations.

Use a deque instead of a list when the main operations are at the ends and you still want indexed reads.

Use a queue or stack instead of a deque when one removal policy is enough and you do not need random access.