Specialised Containers

Overview

These containers are built on basic containers. They include:-

• Stacks - Last in first out

• Queues - First in first out

Stacks and queues have the same interface. Stacks are built on a vector and queues are built on a list. The usual create and free semantics apply, as do generic naming conventions.

Interface

A stack has the container type ‘stack’ and queue has the container type ‘queue’, so to create:-

/* Stack of ints */
STACK_INT stk = stack_int_create(mem, 16);

/* Queue of char*  */
QUEUE_STR q = queue_str_create(mem);

The interface is more limited than the underlying container. There are two fundamental operations, push() and pop() to add and remove, and also a peek() to check the next available element without removing it. Where ‘spec’ is a queue or stack…

TYPE element = spec_pop(spec);
spec_push(spec, element);
TYPE element = spec_peek(spec);

For example:-

#include <c-craft/mem.h>

MEM_SCOPE = sm_create(0);
QUEUE_PTR q = queue_ptr_create(mem);

typedef struct user { char *name; int age; } USER;

USER user1 = sm_alloc(mem, sizeof(USER));
user1->age = 25;
user1->name = sm_strdup(mem, "Jim Smith");

USER user2 = sm_alloc(mem, sizeof(USER));
user2->age = 57;
user2->name = sm_strdup(mem, "Ellen Smith");

queue_push(q, user1);
queue_push(q, user2);        /* Queue contains two */

USER same1 = queue_peek(q);  /* Still contains two */
same1 = queue_pop(q);        /* Points to user1, first pushed */
USER same2 = queue_pop(q);   /* Queue now empty */

sm_free(mem);

It is also possible to query the size of a queue or stack:

QUEUE_INT q = queue_int_create(mem);
for(int i = 0; i < 5; i++)
    queue_push(q, i);

size_t count = queue_int_count(q);  /* Returns 5 */

Note that a queue is based on a list, so will literally count the elements.