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

typedef struct queue {
    int data;
    struct queue *nextPtr;
} QUEUE;

QUEUE *enqueue(QUEUE *headPtr, int data);
QUEUE *dequeue(QUEUE *headPtr, int *data);
int isEmpty(QUEUE *queuePtr);
void print_queue(QUEUE *queuePtr);
void usage(void);

void usage(void)
{
    printf("使い方 1: キューに値を追加する\n");
    printf("      2: キューから値を削除する\n");
    printf("      3: キューを印刷する\n");
    printf("      4: 終了\n");
}

int main(void)
{
    QUEUE *headPtr = NULL;
    int data;
    int menu;

    usage();
    printf("メニュー番号を入力してください:");
    scanf("%d", &menu);

    while(menu != 4) {
	switch(menu) {
	case 1:
	    printf("キュー追加する整数を入力してください:");
	    scanf("%d", &data);
	    headPtr = enqueue(headPtr, data);
	    print_queue(headPtr);
	    break;
	case 2:
	    if ( !isEmpty(headPtr) ) {
		headPtr = dequeue(headPtr, &data);
		printf("キューから取り除いた値は %d です\n", data);
	    } else {
		printf("キューは空です\n");
	    }
	    break;
	case 3:
	    if ( !isEmpty(headPtr) )
		print_queue(headPtr);
	    else
		printf("キューは空です\n");
	    break;
	default:
	    printf("番号が不正です\n");
	    usage();
	    break;
	}
	printf("メニュー番号を入力してください:");
	scanf("%d", &menu);
    }

    return 0;
}

int isEmpty(QUEUE *queuePtr)
{
    return queuePtr == NULL;
}

QUEUE *enqueue(QUEUE *headPtr, int data)
{
    QUEUE *newPtr, *tmpPtr;

    newPtr = (QUEUE *)malloc(sizeof(QUEUE));

    if ( newPtr != NULL ) {
	newPtr->data = data;
	newPtr->nextPtr = NULL;

	if (isEmpty(headPtr)) {
	    headPtr = newPtr;
	} else {
	    tmpPtr = headPtr;
	    while(tmpPtr->nextPtr != NULL) {
		tmpPtr = tmpPtr->nextPtr;
	    }
	    tmpPtr->nextPtr = newPtr;
	}
    } else {
	    printf("メモリが足りません\n");
    }
    return headPtr;
}

QUEUE *dequeue(QUEUE *headPtr, int *data)
{
    QUEUE *tmpPtr;

    if (headPtr == NULL)
	return NULL;

    *data = headPtr->data;
    tmpPtr = headPtr;
    headPtr = headPtr->nextPtr;
    free(tmpPtr);

    return headPtr;
}

void print_queue(QUEUE *queuePtr)
{
    if (queuePtr == NULL) {
	printf("キューは空です\n");
    } else {
	while ( queuePtr != NULL ) {
	    printf("%d-> ", queuePtr->data);
	    queuePtr = queuePtr->nextPtr;
	}
	printf("NULL\n\n");
    }
}