#include
#include
#include

#ifndef type
#define type int
#endif

// single link
struct link {
type value;
struct link* next;
};

// single linked list with head and tail pointers
struct queue {
struct link* head;
struct link* tail;
};

// stack with two queue instances
struct stack {
struct queue* q1;
struct queue* q2;
};

/**
internal func allocates the queue's sentinel. sets sentinels' next to null,
and queue's head and tail to the sentinel.
param: queue struct linkedlist ptr
pre: queue is not null
post: queue sentinel not null
sentinel next points to null
head points to sentinel (always)
tail points to sentinel (always point to last link unless empty)