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

typedef int element;   // 노드에 담을 자료형
typedef struct _MyNode // 노드 구조체
{
    struct _MyNode* next;
    element data;
} MyNode;

typedef struct _Queue  // 큐 구조체
{
    MyNode* front;
    MyNode* rear;
} Queue;

typedef struct _Stack  // 스택 구조체
{
    MyNode* top;
} Stack;

// 노드 생성 함수
MyNode* createNode(element e)
{
    MyNode* n = (MyNode*)malloc(sizeof(MyNode));
    if (n == NULL)
    {
        fprintf(stderr, "failed to create new node!\n");
        exit(1);
    }
    n->data = e;
    n->next = NULL;

    return n;
}

// 스택 초기화
void Stack_Init(Stack* s)
{
    s->top = NULL;
}

// 스택이 비었으면 1 리턴
int Stack_IsEmpty(Stack* s)
{
    return s->top == NULL;
}

// 스택에 삽입
void Stack_Push(Stack* s, element e)
{
    MyNode* newNode = createNode(e);

    if (Stack_IsEmpty(s))
        s->top = newNode;
    else
    {
        newNode->next = s->top;
        s->top = newNode;
    }
}

// 스택에서 제거
element Stack_Pop(Stack* s)
{
    if (Stack_IsEmpty(s))
    {
        fprintf(stderr, "cannot pop from an empty stack!\n");
        exit(1);
    }
    MyNode* removed = s->top;
    s->top = removed->next;

    element removedElement = removed->data;
    free(removed);
    return removedElement;
}

// 스택 출력
void Stack_Print(Stack* s)
{
    if (Stack_IsEmpty(s))
        printf("Empty stack\n");
    else
    {
        for (MyNode* i = s->top; i != NULL; i = i->next)
        {
            if (i == s->top)
                printf("[TOP : %d] ", i->data);
            else
                printf("%d ", i->data);

            printf("-> ");
        }
        printf("NULL\n");
    }
}

// 큐 초기화
void Queue_Init(Queue* q)
{
    q->front = q->rear = NULL;
}

// 큐가 비었다면 1 리턴
int Queue_IsEmpty(Queue* q)
{
    return q->front == NULL || q->rear == NULL;
}

// 큐에 삽입
void Queue_Enqueue(Queue* q, element e)
{
    MyNode* newNode = createNode(e);

    if (Queue_IsEmpty(q))
    {
        q->front = q->rear = newNode;
    }
    else
    {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 큐에서 제거
element Queue_Dequeue(Queue* q)
{
    if (Queue_IsEmpty(q))
    {
        fprintf(stderr, "cannot removed from an empty queue!\n");
        exit(1);
    }

    MyNode* removed = q->front;
    element removedElement = removed->data;

    // 큐에 하나만 남았다면
    if (q->front == q->rear)
    {
        // 큐는 이제 빈 상태
        q->front = q->rear = NULL;
        // 원래 첫 노드 제거
        free(removed);
        return removedElement;
    }
    // 두개 이상 있다면 front 노드만 제거하면 됨
    else
    {
        // 큐의 첫 노드를 두번째 노드로 이동
        q->front = removed->next;
        // 원래 첫 노드 제거
        free(removed);
        return removedElement;
    }
}

// 큐 출력
void Queue_Print(Queue* q)
{
    if (Queue_IsEmpty(q))
        printf("Empty Queue\n");
    else
    {
        for (MyNode* i = q->front; i != NULL; i = i->next)
        {
            if (q->front == q->rear)
                printf("[FRONT/REAR: %d] ", i->data);
            else if (i == q->front)
                printf("[FRONT: %d] ", i->data);
            else if (i == q->rear)
                printf("[REAR: %d] ", i->data);
            else
                printf("%d ", i->data);

            printf("-> ");
        }
        printf("NULL\n");
    }
}

int main()
{
    printf("==== STACK ====\n");

    Stack s;
    Stack_Init(&s);

    Stack_Push(&s, 10);
    Stack_Push(&s, 20);
    Stack_Push(&s, 30);
    Stack_Print(&s);

    Stack_Pop(&s);
    Stack_Pop(&s);
    Stack_Print(&s);

    Stack_Pop(&s);
    Stack_Print(&s);

    printf("\n==== QUEUE ====\n");

    Queue q;
    Queue_Init(&q);

    Queue_Enqueue(&q, 10);
    Queue_Enqueue(&q, 20);
    Queue_Enqueue(&q, 30);
    Queue_Print(&q);

    Queue_Dequeue(&q);
    Queue_Print(&q);

    Queue_Dequeue(&q);
    Queue_Print(&q);

    Queue_Dequeue(&q);
    Queue_Print(&q);

    return 0;
}