题目

设以数组Q.elems[maxSize]存储循环队列的元素，同时以Q.rear和Q.length分别指示循环队列中的队尾位置和队列中所含元素的个数。试着给出该循环队列的队空条件和队满条件，并写出相应的入队（enQueue）和出队（deQueue）的操作。

分析

本题和普通的循环队列是不一样的，普通的循环队列是有两个指针的，即队头指针front和队尾指针rear，而本题中没有队头指针，因此出队的时候就需要根据已有的数据计算队头指针，来达到出队的目的。

队空的条件是：Q.length==0
	
队满的条件是：Q.length==maxSize


入队很简单，同普通的循环队列入队是一样的，需要注意的是注意Q.length的变化。

Q.rear=(Q.rear+1)%maxSize;// 移动指针
Q.elems[Q.rear]=x;// 入队元素
Q.length++;// 队列长度加1

出队是有些麻烦，因为没有队头指针，所以需要根据已有的信息计算队头指针，其核心语句如下：

x=Q.elems[(Q.rear-Q.length+1+maxSize)%maxSize];// 计算front的关键代码 
Q.length--;// 出队后，队列长度减1 

而(Q.rear-Q.length+1+maxSize)%maxSize就是头指针，在循环队列中的下标。

代码

核心代码如下：

/* 入队 */
int enQueue(Queue &Q,int x) {
	/* 入队元素之前判断队列是否满队 */
	if(isQueueFull(Q)==1) {
		return 0;
	} else {
		Q.rear=(Q.rear+1)%maxSize;// 移动指针
		Q.elems[Q.rear]=x;// 入队元素
		Q.length++;// 队列长度加1
		return 1;
	}
}

/* 出队 */ 
int deQueue_2(Queue &Q,int &x){
	if(Q.length==0){
		return 0;
	}
//	--(Q.length);// 参考代码是先减长度 
	x=Q.elems[(Q.rear-Q.length+1+maxSize)%maxSize];// 计算front的关键代码 
	Q.length--;// 出队后，队列长度减1 
	return 1;
}

完整代码：

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

#define maxSize 8

typedef struct Queue {
	int elems[maxSize];
	int rear;// 循环队列的队尾位置
	int length;// 循环队列中所含元素的个数
} Queue;

/* 初始化队列 */
void initQueue(Queue &Q) {
	Q.rear=0;
	Q.length=0;
}

/* 判断是否循环队列队满，满队返回1，否则返回0 */
int isQueueFull(Queue Q) {
	if(Q.length==maxSize) { // 队满的条件是队列中元素个数等于maxSize
		return 1;
	}
	return 0;
}

/* 判断是否循环队列队空，空队返回1，否则返回0 */
int isQueueEmpty(Queue Q) {
	if(Q.length==0) { // 队空的条件是队列的元素个数为0
		return 1;
	}
	return 0;
}

/* 入队 */
int enQueue(Queue &Q,int x) {
	/* 入队元素之前判断队列是否满队 */
	if(isQueueFull(Q)==1) {
		return 0;
	} else {
		Q.rear=(Q.rear+1)%maxSize;// 移动指针
		Q.elems[Q.rear]=x;// 入队元素
		Q.length++;// 队列长度加1
		return 1;
	}
}

/* 出队 */ 
int deQueue_2(Queue &Q,int &x){
	if(Q.length==0){
		return 0;
	}
//	--(Q.length);// 参考代码是先减长度 
	x=Q.elems[(Q.rear-Q.length+1+maxSize)%maxSize];// 计算front的关键代码 
	Q.length--;// 出队后，队列长度减1 
	return 1;
}

/* 打印循环队列 */ 
void print(Queue Q){
	printf("打印循环队列如下：");
	while(Q.length!=0){
		printf("%d\t",Q.elems[(Q.rear-Q.length+1+maxSize)%maxSize]);
		Q.length--;
	}
	printf("\n");
}

int main(){
	Queue Q;
	initQueue(Q);// 初始化队列
	
	/* 入队 */
	enQueue(Q,1); 
	enQueue(Q,2); 
	enQueue(Q,3); 
	enQueue(Q,4); 
	enQueue(Q,5); 
	printf("\n");
	printf("入队元素：1,2,3,4,5\n");
	printf("循环队列的长度：%d\n",Q.length);
	printf("循环队列的队尾rear：%d\n",Q.rear);
	print(Q);
	
	/* 出队元素1 */
	int x;
	printf("\n");
	deQueue_2(Q,x);
	printf("出队元素：%d\n",x);
	printf("循环队列的长度：%d\n",Q.length);
	printf("循环队列的队尾rear：%d\n",Q.rear);
	print(Q);
	/* 出队元素2 */
	printf("\n");
	deQueue_2(Q,x);
	printf("出队元素：%d\n",x);
	printf("循环队列的长度：%d\n",Q.length);
	printf("循环队列的队尾rear：%d\n",Q.rear);
	print(Q); 
	
	
	/* 再入队 */ 
	enQueue(Q,6);
	enQueue(Q,7);
	enQueue(Q,8);
	enQueue(Q,9);
	printf("\n");
	printf("入队元素：6,7,8,9\n");
	printf("循环队列的长度：%d\n",Q.length);
	printf("循环队列的队尾rear：%d\n",Q.rear);
	print(Q);
	
	/* 再出队 */
	deQueue_2(Q,x);
	printf("\n");
	printf("出队元素：%d\n",x); 
	printf("循环队列的长度：%d\n",Q.length);
	printf("循环队列的队尾rear：%d\n",Q.rear);
	print(Q);
	 
	return 0;
}

运行结果如下：

题目
假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag = 0 和 tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试设计与此结构相应的插入和删除算法，编写代码，并带入数据运行验证通过
#include<iostream>
using namespace std;
#define MaxSize 100
int tag; //以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为"空"还是"满"
typedef struct{
	int *base;
	int front;
	int rear;
}Seq; 

int Init(Seq &L){    //初始化
	L.base = new int[MaxSize];
	L.front = L.rear = 0;
	tag = 0;
	return 1;
}

int Enter(Seq &L,int m){     //入队列
	if(L.rear%MaxSize == L.front && tag == 1){
		cout<<"队列已满！";
		return 0; 
	}
	L.base[L.rear] = m;
	L.rear = (L.rear+1)%MaxSize;
	if(L.rear == L.front)tag = 1;
	return 1;
}

int Out(Seq &L,int &m){    // 出队列
	if(L.rear == L.front && tag == 0){
		cout<<"队列空！";
		return 0;
	}
	m = L.base[L.front];
	L.front = (L.front+1)%MaxSize;
	if(L.rear == L.front)tag = 0;
	return 1;
}

int JudgeEmpty(Seq L){
	if(L.rear == L.front && tag == 0){
		cout<<"队列空！";
		return 0;
	}
}

int JudgeFullness(Seq L){
	if(L.rear%MaxSize == L.front && tag == 1){
		cout<<"队列已满！";
		return 0; 
	}
}

int main(){
	Seq S;
	int m;
	Init(S);
	Enter(S,4);
	Enter(S,5);
	Enter(S,7);
	Enter(S,6);
	Enter(S,8);
	
	for(int i = 0;i < 5;i++){
		Out(S,m);
		cout<<m<<" ";
	}
	JudgeEmpty(S);
	return 0;
}


参考资料：

《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民

/*数据结构与算法-第三章栈和队列课后习题
*课本第85页3.7
*题目:假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag,以tag=0和tag=1来区别在队头指针(front)和队尾指针(rear)相等时,
*     队列状态为"空"还是"满"。
*     试编写与此结构相应的插入(enqueue)和删除(dequeue)算法。
*编译环境:VC 6.0
*/
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define overflow -1
#define MAXSIZE 10

typedef int qelemType;
int count=0;

typedef struct
{
	qelemType q[MAXSIZE];
	int tag;
	int head,rear;
}sqqueue;

void initQueue(sqqueue &queue)//队列初始化
{
	queue.head=0;
	queue.rear=0;
	queue.tag=0;
}

int enqueue(sqqueue &queue,qelemType e)
{
	if(count==MAXSIZE)
		queue.tag=1;
	if(queue.tag==1 && queue.head==queue.rear)//即队列已满
		return ERROR;
	else
	{
		queue.q[queue.rear]=e;
		queue.rear=(queue.rear+1)%MAXSIZE;
		count++;
	}
	return OK;
}

int dequeue(sqqueue &queue,qelemType &e)
{
	if(count==0)
		queue.tag=0;
	if(queue.tag==0 && queue.head==queue.rear)
		return ERROR;
	else
	{
		e=queue.q[queue.head];
		queue.head=(queue.head+1)%MAXSIZE;
		count--;
	}
	return OK;
}

int queuelen(sqqueue queue)
{
	return (queue.rear-queue.head+MAXSIZE)%MAXSIZE;
}

int main()
{
	sqqueue queue1;
	initQueue(queue1);
	int num;
	for(int i=12;i>=1;i--)
	{
		printf("ATTENTION---Queue's length=%d,",queuelen(queue1));
		if(enqueue(queue1,i))
			printf("成功插入元素%d!\n",i);
		else
		{
			printf("队列已满!\n");
			break;
		}
	}
	printf("\n\n");
	for(int k=1;k<=14;k++)
	{
		printf("ATTENTION---Queue's length=%d,",queuelen(queue1));
		if(dequeue(queue1,num))
			printf("成功删除元素%d!\n",num);
		else
		{
			printf("队列已空!\n");
			break;
		}
	}
	return 0;
}

数组元素
声明和使用数组
对象数组
命令行实参
可变长度参数表 
二维数组与多维数组
转载于:https://www.cnblogs.com/q2546/p/10926309.html