《數(shù)據(jù)結(jié)構(gòu)（C語言版）》循環(huán)隊列的實現(xiàn)
清華大學(xué)計算機(jī)系列教材? ?累計發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉民?編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第三章棧和隊列中循環(huán)隊列的代碼實現(xiàn)，即課本3.4.3節(jié)隊列的順序表示和實現(xiàn)，本人使用少用一個元素空間的方式區(qū)分隊滿與隊空，并處理了非法輸入字母等問題。
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯）?
代碼實現(xiàn)如下
/*
課本P63頁倒數(shù)第二段，由于C語言中中僅憑等式Q.front==Q.rear無法判斷隊列空間是“空”還是“滿”
可以采取兩種處理方法：
1.另設(shè)一個標(biāo)志位以區(qū)別隊列是“空”還是“滿”
2.少用一個元素空間，約定以隊列頭指針在隊列尾指針的下一位置作為隊列成“滿”狀態(tài)的標(biāo)志
下列代碼中采取處理方法2
隊空標(biāo)志：front==rear
隊滿標(biāo)志：(rear+1)%MAXQSIZE==front
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXQSIZE 6
typedef int Status;
typedef int QElemType;
typedef struct
{
QElemType* base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue& Q);//隊列的初始化
int QueueLength(SqQueue Q);//返回Q的元素個數(shù)，即隊列的長度
Status EnQueue(SqQueue& Q, QElemType e);//入隊
Status DeQueue(SqQueue& Q, QElemType& e);//出隊
Status GetHead(SqQueue Q, QElemType& e);//用e返回隊頭元素，若隊空返回ERROR
void Menu()
{
printf("***************************\n");
printf("********0：退出系統(tǒng)********\n");
printf("********1：元素入隊********\n");
printf("********2：元素出隊********\n");
printf("********3：求隊列長********\n");
printf("********4：求隊頭值********\n");
printf("***************************\n");
}
int main()
{
int option;
int value;
SqQueue MyQueue;
InitQueue(MyQueue);
Menu();
printf("請輸入你想使用的功能：");
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');
switch (option)
{
case 1:
printf("請輸入你想入隊的元素：");
while (scanf("%d", &value) != 1)
{
while (getchar() != '\n');
printf("非法輸入，請重試\n");
}
if (EnQueue(MyQueue, value))
{
printf("入隊成功！\n");
}
else
{
printf("隊列的最大長度為%d,隊列已滿！\n", MAXQSIZE - 1);
}
break;
case 2:
if (DeQueue(MyQueue, value))
{
printf("元素%d出隊成功!\n", value);
}
else
{
printf("隊空，無元素可出隊\n");
}
break;
case 3:
printf("隊列長度為%d\n", QueueLength(MyQueue));
break;
case 4:
if (GetHead(MyQueue, value))
{
printf("隊頭元素為%d\n", value);
}
else
{
printf("隊空，無隊頭元素\n");
}
break;
case 0:
printf("感謝使用！\n");
exit(0);
default:
printf("非法輸入，請重試\n");
}
Menu();
printf("請輸入你想使用的功能：");
}
return 0;
}
Status InitQueue(SqQueue& Q)//隊列的初始化
//構(gòu)造一個空隊列
{
Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
if (!Q.base)
{
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return OK;
}
int QueueLength(SqQueue Q)//返回Q的元素個數(shù)，即隊列的長度
{
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue(SqQueue& Q, QElemType e)//入隊
//插入元素e為Q的新的隊尾元素
{
if ((Q.rear + 1) % MAXQSIZE == Q.front)
{
return ERROR;//隊列滿
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;//隊尾指針+1
return OK;
}
Status DeQueue(SqQueue& Q, QElemType& e)//出隊
//若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK，否則返回ERROR
{
if (Q.front == Q.rear)//如果隊空
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
Status GetHead(SqQueue Q, QElemType& e)//用e返回隊頭元素，若隊空返回ERROR
{
if (Q.front != Q.rear)
{
e = Q.base[Q.front];//返回對頭指針元素，對頭指針不變
return OK;
}
return ERROR;
}
