/* C11. Linked stack and queue with explicit allocation and ownership. */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *next; } Node;
typedef struct { Node *top; } Stack;
typedef struct { Node *front, *rear; } Queue;
static Node *make_node(int value)
{
    Node *p = malloc(sizeof *p);
    if (p != NULL) *p = (Node){value, NULL};
    return p;
}
static bool push(Stack *s, int value)
{
    Node *p = make_node(value);
    if (p == NULL) return false;
    p->next = s->top; s->top = p; return true;
}
static bool pop(Stack *s, int *out)
{
    if (s->top == NULL) return false;
    Node *p = s->top; *out = p->value; s->top = p->next; free(p); return true;
}
static bool enqueue(Queue *q, int value)
{
    Node *p = make_node(value);
    if (p == NULL) return false;
    if (q->rear == NULL) q->front = p;
    else q->rear->next = p;
    q->rear = p; return true;
}
static bool dequeue(Queue *q, int *out)
{
    if (q->front == NULL) return false;
    Node *p = q->front; *out = p->value; q->front = p->next;
    if (q->front == NULL) q->rear = NULL; /* Never leave a dangling tail. */
    free(p); return true;
}
static void clear_stack(Stack *s) { int ignored; while (pop(s, &ignored)) {} }
static void clear_queue(Queue *q) { int ignored; while (dequeue(q, &ignored)) {} }
int main(void)
{
    Stack s = {NULL}; Queue q = {NULL, NULL}; int value = -1;
    assert(!pop(&s, &value) && !dequeue(&q, &value) && value == -1);
    for (int i = 1; i <= 3; ++i) {
        if (!push(&s, i) || !enqueue(&q, i)) {
            clear_stack(&s); clear_queue(&q); return EXIT_FAILURE;
        }
    }
    printf("Linked stack:");
    for (int i = 3; i >= 1; --i) {
        assert(pop(&s, &value) && value == i); printf(" %d", value);
    }
    putchar('\n');
    printf("Linked queue:");
    for (int i = 1; i <= 3; ++i) {
        assert(dequeue(&q, &value) && value == i); printf(" %d", value);
    }
    putchar('\n'); assert(q.front == NULL && q.rear == NULL && s.top == NULL);
    for (int i = 0; i < 100; ++i) {
        assert(enqueue(&q, i)); assert(dequeue(&q, &value) && value == i);
        assert(q.front == NULL && q.rear == NULL);
    }
    assert(push(&s, 9) && enqueue(&q, 9));
    clear_stack(&s); clear_queue(&q); clear_stack(&s); clear_queue(&q);
    assert(s.top == NULL && q.front == NULL && q.rear == NULL);
    puts("linked stack/queue tests passed");
    return EXIT_SUCCESS;
}