C語言實作順序隊列（環形）

一、頭檔案、自定義資料類型及自定義變量

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

typedef int QElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define MAXQSIZE 100	//隊列所能達到的最大長度
           

二、順序隊列的存儲結構

typedef struct{
	QElemType  data[MAXQSIZE];	
	int front;	//頭指針（數組下标）
	int rear;	//尾指針（數組下标） 
}SqQueue; 
           

三、建立隊列（初始化）

Status InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
	printf("空隊列已經建立\n");
	return OK; 	
} 
           

四、求隊列長度

int QueueLength(SqQueue Q){
	return (Q.rear+MAXQSIZE-Q.front)%MAXQSIZE; 
} 
           

解析：

隊列中有效資料個數：(rear+MAXQSIZE-front)%MAXQSIZE

因為是環形隊列，有以下兩種情況：

1、front位于rear之前

有效資料個數：rear-front

與(rear+MAXQSIZE-front)%MAXQSIZE等價

2、front位于rear之後

有效資料個數：rear+MAXQSIZE-front

因為rear-front<0

(rear-front)%MAXQSIZE=rear-front

與(rear+MAXQSIZE-front)%MAXQSIZE等價

五、入隊

在非空隊列中，頭指針始終指向隊列頭元素，尾指針始終指向隊列尾元素的下一個位置

入隊時，尾指針rear+1

Status EnQueue(SqQueue &Q,QElemType e){
	if((Q.rear+1)%MAXQSIZE==Q.front){	//隊滿
		printf("隊滿，無法執行此操作\n");
		return ERROR;
	}
	Q.data[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXQSIZE;	
} 
           

注意

rear+1取模含義：

當rear+1<MAXQSIZE時為原數，

大于時，把多出的補在開頭，

組止了數組越界

六、出隊

出隊時，頭指針front+1

Status DeQueue(SqQueue &Q,QElemType &e){
	if(Q.front==Q.rear){
		printf("隊列為空，無法執行此操作\n");
		return ERROR;
	}
	e=Q.data[Q.front];	//儲存隊列頭元素
	Q.front=(Q.front+1)%MAXQSIZE;
	printf("已成功入隊\n");
	printf("出隊元素：%d",e);
	return OK; 
} 
           

七、取循環隊列頭元素

QElemType GetHead(SqQueue Q){
	if(Q.front==Q.rear){
		printf("隊列中無元素，将輸出預設元素0\n");
		return ERROR; 
	}
	return Q.data[Q.front];
} 	
           

八、展示隊列

Status ShowQueue(SqQueue Q){
	int n=Q.front+(Q.rear+MAXQSIZE-Q.front)%MAXQSIZE;
	if(n==0){
		printf("隊列空，無法展示\n");
		return ERROR;
	}
	else{
		for(int i=Q.front;i<n;i++){
			printf("arr[%d]:%d\n",i%MAXQSIZE,Q.data[i%MAXQSIZE]);
		}	
		return OK;
	}
} 
           

九、主函數

int main(){
	SqQueue Q;
	int flag=0;
	int n=0;
	int l=0;
	int h=0;
	int gt=0;
	bool loop=true;
	InitQueue(Q);
	while(loop){
		printf("請操作\n");
		printf("1(Enter):入隊\n");
		printf("2(Delete):出隊\n");
		printf("3(Length):隊列目前長度\n");
		printf("4(Get):取隊首元素\n");
		printf("5(Show):展示隊列\n");
		printf("6(exit):退出程式\n");
		scanf("%d",&flag);
		switch(flag){
			case 1:
				printf("請輸入入隊元素\n");
				scanf("%d",&n);
				EnQueue(Q,n);
				printf("已成功入隊\n");
				break;
			case 2:
				DeQueue(Q,n);
				printf("已成功出隊\n");
				break;
			case 3:
				l=QueueLength(Q);
				printf("隊列目前長度為：%d\n",l);
				break;
			case 4:
				h=GetHead(Q);
				printf("隊首元素為：%d\n",h);
				break;
			case 5:
				printf("展示隊列：\n");
				ShowQueue(Q);
				break;
			case 6:
				loop=false;
				break;
		}
	}
	return 0;
}