/*
 * Queue サンプル
 *
 *  2004.12.08 
 *
 */

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

typedef struct _LIST{
    int data;
    struct _LIST *next;
}LIST;

LIST *NodeAlloc(void);
void NodeFree(LIST *Node);
void HeadInsert(LIST **Head, LIST *Node);
void TailInsert(LIST **Head, LIST *Node);
void DeleteNode(LIST **Head, int Position);

int GetNodeTotal(LIST **Head);
LIST *GetNode(LIST **Head, int n);

int main(void)
{
    LIST *p, *wp;
    LIST *head;
    int w, in, data;

    head = (LIST *)NULL;

    for(;;){
        printf(" 1.キューに入れる\n");
        printf(" 2.キューから取り出す\n");
        printf(" 3.キューに連続で入れる -1で終了\n");
        printf(" 4.全データ表示\n");
        printf(" 5.要素の数\n");
        printf("-1.終了\n");
        printf("\n");
        printf("Input Number >> ");

        scanf("%d", &in);
        if(in == -1)
            break;
        
        switch(in){
            case 1:
                printf("Data   >> ");
                scanf("%d", &data);
                p = NodeAlloc();
                p->data =http://www.mamicode.com/ data;
                TailInsert(&head, p);
                printf("入れました >> %d\n", p->data);
                break;

            case 2:
                w=1;                            /* 先頭を指定 */
                p=GetNode(&head, w);
                if(p!=(LIST *)NULL){
                    printf("取り出しました >> %d\n", p->data);
                    DeleteNode(&head, w);
                }else{
                    printf("取り出すデータはありません");
                }
                printf("\n");
                break;

            case 3:
                for(;;){
                    printf("Data >> ");
                    scanf("%d", &data);
                    if(data=http://www.mamicode.com/=-1)break;

                    p = NodeAlloc();
                    p->data =http://www.mamicode.com/ data;

                    TailInsert(&head, p);
                }
                break;
            case 4:
                printf("\nView All Data\n");
                w=1;
                while((p=GetNode(&head, w))!=(LIST *)NULL){
                    printf("%2d >> %d\n", w, p->data);
                    w++;
                }
                printf("\n");
                break;
            case 5:
                printf("\n要素の数 >> %d個\n", GetNodeTotal(&head));
                break;
            default:
                break;
        }
        printf("\n");
    }

    for(p=head; p!=(LIST *)NULL; p = wp){
        wp = p->next;
        NodeFree(p);
    }
    return 0;
}

/*
 * リストの先頭にNodeを追加
 */

void HeadInsert(LIST **Head, LIST *Node)
{
      /* データを追加 */
    Node->next = *Head;
    *Head = Node;
}

/*
 * リストの最後にNodeを追加
 */

void TailInsert(LIST **Head, LIST *Node)
{
    LIST *p;
    
    if(*Head == (LIST *)NULL){ /* リストにデータが無い場合、先頭に追加 */
        HeadInsert(Head, Node);
    }else{
        for(p=*Head; p->next!=(LIST *)NULL; p=p->next); /* リストの最後を検索 */

          /* データを追加 */
        p->next = Node;
        Node->next = NULL;
    }
}

/*
 * リスト内のNodeを削除
 */

void DeleteNode(LIST **Head, int Position)
{
    LIST *p, *Node;

    Position--;                                   /* 削除位置の一つ前にする */

    if(*Head != (LIST *)NULL){                    /* LISTが存在しないなら終了 */
        if(Position==0){                          /* 削除位置が先頭なら解放 */
            p=*Head;
            *Head = p->next;
            NodeFree(p);
        }else if(GetNodeTotal(Head)>Position && Position>0){   /* 削除位置がList内なら */
            p=GetNode(Head, Position);            /* 削除位置のNodeを取得 */
            Node = p->next;                       /* Nodeを解放する */
            p->next = Node->next;
            NodeFree(Node);
        }
    }
}

/*
 * Nodeを確保する
 */

LIST *NodeAlloc(void)
{
    return (LIST *)malloc(sizeof(LIST));
}

/*
 * Nodeを解放する
 */

void NodeFree(LIST *Node)
{
    free(Node);
}

/*
 * Nodeの総数を取得
 */

int GetNodeTotal(LIST **Head)
{
    LIST *p;
    int n=0;
    
    for(p=*Head; p!=(LIST *)NULL; p=p->next)    /* NULLが出るまで、ノードをカウント */
        n++;

    return n;
}

/*
 * Nodeのデータを取得
 */

LIST *GetNode(LIST **Head, int n)
{
    int j=1;
    LIST *p;

    for(p=*Head; p!=(LIST *)NULL; p=p->next){    /* NULLが出るか、n番目のノードを取得するまでループ */
        if(j==n)break;
        j++;
    }
    
    return p;
}