typedef struct stack *stack_t;

stack_t stack_create(void);               // create a new stack
void stack_free(stack_t stack);           // free a stack
void stack_push(stack_t stack, int item); // add new item to stack
int stack_pop(stack_t stack);             // remove top item from stack and return it
int stack_is_empty(stack_t stack);        // return true if stack is empty
int stack_top(stack_t stack);             // return top item from stack but don't remove it
int stack_size(stack_t stack);            // return number elements in stack

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

#define MAX 2048

struct stack {
    int elements[MAX];
    int top;
};

// create a new stack
stack_t stack_create(void) {
    struct stack *s = malloc(sizeof *s);
    if (s == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    s->top = 0;
    return s;
}

// add new item to stack
void stack_push(stack_t stack, int item) {
    if (stack->top == MAX) {
        fprintf(stderr, "push() exceeds maximum stack size %d\n", MAX);
        exit(1);
    }
    stack->elements[stack->top] = item;
    stack->top++;
}

// remove top item from stack and return it
int stack_pop(stack_t stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "pop() of empty stack\n");
        exit(1);
    }
    return stack->elements[--stack->top];
}

// return true if stack is empty
int stack_is_empty(stack_t stack) {
    return stack->top == 0;
}

// return top item from stack but don't remove it
int stack_top(stack_t stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "top() of empty stack\n");
        exit(1);
    }
    return stack->elements[stack->top-1];
}

// return number elements in stack
int stack_size(stack_t stack) {
    return stack->top;
}

// free a stack
void stack_free(stack_t stack) {
    free(stack);
}

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

struct node {
    int       data;
    struct node *next;
};

struct stack {
    struct node   *top;
};

// create a new stack
stack_t stack_create(void) {
    struct stack *s = malloc(sizeof *s);
    if (s == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    s->top = NULL;
    return s;
}

// add new item to stack
void stack_push(stack_t stack, int item) {
    struct node *n = malloc(sizeof *n);
    n->data = item;
    n->next  = stack->top;
    stack->top = n;
}

// remove top item from stack and return it
int stack_pop(stack_t stack) {
    int i;
    struct node *n;

    if (stack_is_empty(stack)) {
        fprintf(stderr, "pop() of empty stack\n");
        exit(1);
    }

    n = stack->top;
    i = n->data;
    stack->top = stack->top->next;
    free(n);
    return i;
}

// return true if stack is empty
int stack_is_empty(stack_t stack) {
    return stack->top == NULL;
}

// return top item from stack but don't remove it
int stack_top(stack_t stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "top() of empty stack\n");
        exit(1);
    }
    return stack->top->data;
}

// return number elements in stack
int stack_size(stack_t stack) {
    int i = 0;
    struct node *n = stack->top;
    while (n != NULL) {
        i++;
        n = n->next;
    }
    return i;
}

// free a stack
void stack_free(stack_t stack) {
    while (!stack_is_empty(stack)) {
        stack_pop(stack);
    }
    free(stack);
}

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

#define INITIAL_STACK_SIZE 1024

struct stack {
    int *elements;
    int size;
    int top;
};

// create a new stack
stack_t stack_create(void) {
    struct stack *s = malloc(sizeof *s);
    if (s == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    s->size = INITIAL_STACK_SIZE;
    s->elements = malloc(s->size * sizeof s->elements[0]);
    if (s->elements == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    s->top = 0;
    return s;
}

// add new item to stack
void stack_push(stack_t stack, int item) {
    if (stack->top == stack->size) {
        stack->size = stack->size * 2;
        stack->elements = realloc(stack->elements, stack->size * sizeof stack->elements[0]);
        if (stack->elements == NULL) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
    }
    stack->elements[stack->top] = item;
    stack->top++;
}

// remove top item from stack and return it
int stack_pop(stack_t stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "pop() of empty stack\n");
        exit(1);
    }
    return stack->elements[--stack->top];
}

// return true if stack is empty
int stack_is_empty(stack_t stack) {
    return stack->top == 0;
}

// return top item from stack but don't remove it
int stack_top(stack_t stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "top() of empty stack\n");
        exit(1);
    }
    return stack->elements[stack->top-1];
}

// return number elements in stack
int stack_size(stack_t stack) {
    return stack->top;
}

// free a stack
void stack_free(stack_t stack) {
    free(stack->elements);
    free(stack);
}

typedef struct queue *queue_t;

queue_t queue_create(void);               // create a new queue
void queue_free(queue_t queue);           // free a queue
void queue_enqueue(queue_t queue, int item); // add new item to queue
int queue_dequeue(queue_t queue);             // remove next item from queue and return it
int queue_is_empty(queue_t queue);        // return true if queue is empty
int queue_front(queue_t queue);             // return next item from queue but don't remove it
int queue_size(queue_t queue);            // return number elements in queue

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

int main(void) {
    stack_t s;
    s = stack_create();
    stack_push(s, 10);
    stack_push(s, 11);
    stack_push(s, 12);
    printf("%d\n", stack_size(s)); // prints 3
    printf("%d\n", stack_top(s)); // prints 12
    printf("%d\n", stack_pop(s)); // prints 12
    printf("%d\n", stack_pop(s)); // prints 11
    printf("%d\n", stack_pop(s)); // prints 10
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

int main(void) {
    queue_t q;
    q = queue_create();
    queue_enqueue(q, 10);
    queue_enqueue(q, 11);
    queue_enqueue(q, 12);
    printf("%d\n", queue_size(q)); // prints 3
    printf("%d\n", queue_front(q)); // prints 10
    printf("%d\n", queue_dequeue(q)); // prints 10
    printf("%d\n", queue_dequeue(q)); // prints 11
    printf("%d\n", queue_dequeue(q)); // prints 12
    return 0;
}