//用循環單鏈表實現隊列的基本操作
//算法的實現：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef int DateType; 
struct Node;
typedef struct Node *PNode;

struct Node//結點結構
{
	DateType info;
	PNode link;
};
//函數聲明
int isEmptyQueue_link(PNode &p);
void enQueue_link(PNode &p,DateType x);
void deQueue_link(PNode &p);
DateType frontQueue_link(PNode &p);
void scan_link(PNode &p);


//主函數
void main()
{
  PNode head=NULL;
  int i=1,x,y;
 while(i)
{
 printf("**********************************************************************\n");
 printf("請選擇：1 判斷隊列是否為空 2 進隊列 3 出隊列 4 取隊列頭部元素的值\n");
 printf("        5 遍歷隊列 0 退出程序\n注意：輸入整數后請回車\n");
 printf("**********************************************************************\n");
   scanf("%d",&i);
	
		switch(i)
	   {case 1:y=isEmptyQueue_link(head);
	           if(y==1)
				   printf("隊列為空!\n");
			   else printf("隊列非空！\n");
			   break;
        case 2:printf("請你輸入進隊列的元素值: ");
			   scanf("%d",&x);
			   enQueue_link(head,x);
			   break;
		case 3:deQueue_link(head);
			   break;
		case 4:y=frontQueue_link(head);
			   if(y!=65535)
			   printf("隊列頭部元素的值為：%d\n",y);
			   break;
		case 5:scan_link(head);
			   break;
		
		default:if(i!=0)
			    printf("選擇有錯!請你重新選擇!\n");
		}	       
	}
}
int isEmptyQueue_link(PNode &p)//判斷隊列是否為空
{
	return(p==NULL);
}
void enQueue_link(PNode &p,DateType x)//入隊列
{
	
        PNode flag=NULL;//flag 始終指向第一個結點
        PNode q=NULL;
	if(p==NULL)//創建第一個結點
	{if((p=(PNode)malloc(sizeof(struct Node)))==NULL)
              printf("空間分配失敗!\n");
	 p->info=x;
	 p->link=p;//頭指針p 始終指向尾結點
	 flag=p;
	}
	else //創建其他結點
               {   flag=p->link;//在改變頭指針指向前使flag始終保持指向首結點
                  q=p;
	     if((p=(PNode)malloc(sizeof(struct Node)))==NULL)
              printf("空間分配失敗!\n");
     	  p->info=x;
          q->link=p;
          p->link=flag;}
}
void deQueue_link(PNode &p)//出隊列
{
	PNode q;
	if(p==NULL)
		printf("隊列為空的!\n");
	else 
		 if(p->link==p)//只有一個結點的刪除處理
		 {free(p);
		 p=NULL;}
		 else //兩個或者兩個以上結點的時候的刪除處理
		 {    q=p->link;
		      p->link=p->link->link; 
		      free(q);
                  
		 }
}
DateType frontQueue_link(PNode &p)//取隊列頭部元素值
{
	if(p==NULL)
	{printf("隊列是空的!\n");
	 return 65535;//返回一個特殊值
	}
	else return(p->link->info);
}
void scan_link(PNode &p)//遍歷隊列
{
	PNode q;
	int i=1;
    if(p==NULL)
      printf("隊列是空的!\n");  
	else 
	{   for(q=p->link;q!=p;q=q->link)
		printf("第%d個元素是 %d\n",i++,q->info);
	    printf("第%d個元素是 %d\n",i++,q->info);
	}
}
//