博客

循环队列其实是为了解决顺序栈的假溢出。设队列大小是M。



这里特别提出一点就是计算队列长度

(Q.rear – Q.front + MAXQSIZE) % MAXQSIZE;

此处说明原因，

因为此处为循环队列。



因为循环队列中，当Q.rear的值小于Q.front时，他们的差是负数要加上队列最大长度才是队列的长度，而如果他们的差大于0再加上最大长度时求余可以得到队列的长度。

/* 循环队列基本操作 */

#include <iostream>
#include <fstream>
using namespace std;

#define MAXQSIZE 1000
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef char QElemType;
typedef char SElemType;
typedef int Status;

typedef struct {
	// 初始化动态分配内存空间
	QElemType *base;
	int front;		// 队头指针
	int rear;		// 队尾指针
}SqQueue;

// 初始化循环队列
Status Init_Queue(SqQueue &Q) {		// 构造一个空队列Q
	Q.base = new QElemType[MAXQSIZE];
	if (!Q.base)
		exit(OVERFLOW);			// 存储空间分配失败
	Q.front = Q.rear = 0;		// 队头指针队尾指针设置为0，队列是为空

	return OK;
}

// 求循环队列的长度
int Calc_QueueLength(SqQueue Q) { // 返回Q的元素个数，即队列的长度
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

// 获取循环队列的人头元素
SElemType GetHead_Queue(SqQueue Q) {  // 返回Q的队头元素，不修改队头指针
	if (Q.front != Q.rear)		// 非空
		return Q.base[Q.front];		// 返回队头元素的值，队头指针不变
}

//  入队
Status Entry_Queue(SqQueue &Q, QElemType e) {	// 插入元素e为Q这个队列队尾的元素
	if ((Q.rear + 1) % MAXQSIZE == Q.front)		// 尾队指针在循环意义上加1后等于头指针，表明队列已经满
		return ERROR;
	Q.base[Q.rear] = e;		// 新元素值e插入队尾
	Q.rear = (Q.rear + 1) % MAXQSIZE;		// 队尾指针加1

	return OK;
}

//  出队 
Status Output_Queue(SqQueue &Q, QElemType &e) {  // 删除Q队列的头元素，用e返回要删除元素的值 
	if (Q.rear == Q.front)		// 队列为空
		return ERROR;
	e = Q.base[Q.front];		// 保存队头元素 
	Q.front = (Q.front + 1) % MAXQSIZE;		// 队头指针加1

	return OK;

}

int main()
{
	int choose, flag = 0;
	SqQueue Q;
	QElemType e, j;

	cout << " 1.初始化队列  2.入队  3.读取队列头元素  4.出队  0.退出\n\n" << endl;
	choose = -1;
	while (choose != 0)
	{
		cout << "请选择队列的操作项[0-4]:";
		cin >> choose;
		switch (choose) {
		case 1:
			if (Init_Queue(Q)) {
				flag = 1;
				cout << "循环队列初始化成功." << endl << endl;
			}
			else
			{
				cout << "循环队列初始化失败." << endl << endl;
			}
			break;
			
		case 2:
		{
			fstream file;
			file.open("CycleQNode.txt");
			if (!file)
			{
				cout << "打开文件失败." << endl << endl << endl;
				return  ERROR;
			}

			if (flag) {
				flag = 1;
				cout << "队列入队元素依次为:\n";
				while (!file.eof()) {
					file >> j;
					if (file.fail())
					{
						break;
					}
					else
					{
						Entry_Queue(Q, j);
						cout << j << "  ";
					}
				}
				cout << endl << endl;
			}
			else
				cout << "队列未创建成功，请重新检测." << endl << endl;
			file.close();			
		}
			break;

		case 3:
			if (flag != -1 && flag != 0)
				cout << "队列头部元素为:\n" << GetHead_Queue(Q) << endl << endl;
			else
				cout << "队列中无此数据元素，请重新检测." << endl << endl;
			break;
			
		case 4:
			cout << "队列依次弹出的数据元素为:" << endl;
			while (Output_Queue(Q, e)) {
				flag = -1;
				cout << e << "  ";
			}
			cout << endl << endl;
			break;
		}
	}

	return 0;
}