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

typedef struct node {
    int val;
    struct node *next;
} Node;

Node *head = NULL;

// ノード作成
Node* createN(int x){
    Node *newnode;
    newnode = (Node *)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

// メモリ解放
void freeL(){
    Node *p;
    while(head != NULL){
        p = head->next;
        free(head);
        head = p;
    }
}

// リスト出力
void printL(){
    Node *p = head;
    while(p != NULL){
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

// 先頭に挿入（スタック用）
void insHead(int x){
    Node *p = createN(x);
    p->next = head;
    head = p;
}

// 末尾に挿入（キュー用）
void insTail(int x){
    Node *p = head;
    if(p == NULL){
        head = createN(x);
        return;
    }
    while(p->next != NULL){
        p = p->next;
    }
    p->next = createN(x);
}

// 先頭を削除
void delHead(){
    Node *p = head;
    if(head == NULL) return;
    head = head->next;
    free(p);
}

// ---------- スタックの関数 ----------

// push：先頭に追加
void push(int x){
    insHead(x);
}

// pop：先頭を取り出す
int pop(){
    if (head == NULL) return -1;
    int val = head->val;
    delHead();
    return val;
}

// ---------- キューの関数 ----------

// enqueue：末尾に追加
void enqueue(int x){
    insTail(x);
}

// dequeue：先頭を取り出す
int dequeue(){
    if (head == NULL) return -1;
    int val = head->val;
    delHead();
    return val;
}

// ---------- メイン関数 ----------
int main(void){
    int s1, s2, s3, q1, q2, q3;

    // スタックテスト
    push(1);
    push(2);
    push(3);
    s1 = pop();
    s2 = pop();
    s3 = pop();
    printf("%d %d %d\n", s1, s2, s3); // → 3 2 1

    // キューテスト
    enqueue(1);
    enqueue(2);
    enqueue(3);
    q1 = dequeue();
    q2 = dequeue();
    q3 = dequeue();
    printf("%d %d %d\n", q1, q2, q3); // → 1 2 3

    freeL(); // メモリ解放
    return 0;
}