//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :3  (3_4)                   *
//*PROGRAM          :鏈式隊列                   *
//*CONTENT          :初始化,入隊列,出隊列       *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
enum BOOL{False,True};
typedef struct QNode       //定義節點結構
{char  data;               //數據域
 struct QNode *next;       //后向指針
}QNode,*QueuePtr;
typedef struct linkqueue{  //定義隊列結構
 QueuePtr front;           //隊首指針
 QueuePtr rear;            //隊尾指針
}LinkQueue;
void initial(LinkQueue &);    //初始化一個隊列
BOOL En_LinkQueue(LinkQueue &,char);   //將一個元素入隊列
BOOL De_LinkQueue(LinkQueue &,char &); //將一個元素出隊列
void Print_LinkQueue(LinkQueue);//顯示隊列中所有元素
void main()
{LinkQueue ls;
 char ch,j;
 int flag=1;
 BOOL temp;
 textbackground(3); //設定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現鏈式結構的隊列的操作。\n");
 printf("可以進行入隊列，出隊列等操作。\n");
 //----------------------------------------------------
 initial(ls);       //初始化隊列
 while(flag)
    { printf("請選擇:\n");
      printf("1.顯示隊列所有元素\n");
      printf("2.入隊列\n");
      printf("3.出隊列\n");
      printf("4.退出程序\n");
      scanf(" %c",&j);
      switch(j)
	{case '1':Print_LinkQueue(ls);   //顯示隊列中所有元素
		  break;
	 case '2':printf("請輸入要人隊的元素(一個字符):");
		  scanf(" %c",&ch);   //輸入要入隊列的字符
		  En_LinkQueue(ls,ch);//入隊列
		  Print_LinkQueue(ls);
		  break;
	 case '3':temp=De_LinkQueue(ls,ch);  //出隊列
		  if(temp!=False) {printf("出隊一個元素:%c\n",ch);//若隊列不空，顯示出隊列的元素
			      Print_LinkQueue(ls);
			     }
		else printf("隊列為空!\n");//否則隊列為空
		break;
	 default:flag=0;printf("程序運行結束，按任意鍵退出!\n");
	}
    }
 getch();
}

void initial(LinkQueue &Q)      
{//隊列初始化
 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //生成一個頭結點，并把首尾指針指向頭結點 
 Q.front->next=NULL;
}

BOOL En_LinkQueue(LinkQueue &Q,char ch)
{//入隊列，成功返回True，失敗返回False
 QueuePtr p;
 p=(QueuePtr)malloc(sizeof(QNode));//生成一個新節點
 p->data=ch;                     //賦值
 p->next=NULL;                
 Q.rear->next=p;                 //插入至隊列尾
 Q.rear=p;                       //修改隊尾指針 
 return True;		        
}

BOOL De_LinkQueue(LinkQueue &Q,char &ch)
{//出隊列,成功返回True，并用ch返回該元素值，失敗返回False
 QueuePtr p;
 if(Q.front==Q.rear) return False;     //判斷隊列是否已空，已空返回False
 p=Q.front->next;           //p指向隊列中第一個元素                              
 ch=p->data;                //取得該元素值
 Q.front->next=p->next;     //修改隊首指針
 if(Q.rear==p) Q.rear=Q.front;//若隊列已空，把隊尾指針指向頭結點
 return True;                     //成功出隊列，返回True
}

void Print_LinkQueue(LinkQueue Q)      
{//顯示隊列中所有元素
 QueuePtr p;
 p=Q.front->next;
 if(p==NULL) printf("隊列為空!\n");//隊列為空
 else  {while(p!=NULL)                       //否則顯示隊列中所有元素
	    {printf("%c ",p->data);
	     p=p->next;
	    }
	printf("\n");
       }
}