顺序循环队列的基本操作

队列是一种只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表(头删尾插),它的存储方式分为 顺序队或链队,以循环队列更常见。

循环队列关键在于 %运算 使数组的下标不断被利用, 节约内存分布, 不断的循环利用

参考代码:

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

#define MAXSIZE 10

typedef struct {
	int data [MAXSIZE];
	int front;  //指向首元素的指针
	int rear;   //指向尾元素的下一个元素
} SeqQueue, *PSeqQueue;


//初始化队列,为整个队列分配内存,将队列队头和队尾指针设为0
PSeqQueue Init_SeqQueue() {
	PSeqQueue S;
	S = (PSeqQueue) malloc(sizeof(PSeqQueue));
	if (!S) {
		return NULL;
	}
	S->front = S->rear = 0;
	return S;
}

//返回队列的实际长度 = (rear-front+maxSize)% maxSize
int Length_SeqQueue(SeqQueue S) {
	return (S.rear - S.front + MAXSIZE) % MAXSIZE;
}

//判断队列是否为空
int Empty_SeqQueue(SeqQueue S) {
	return S.front == S.rear;
}

//入队,参数x为入队元素
void In_SeqQueue(PSeqQueue S, int x) {
	//这里队列判满采用少用一个元素
	if ((S->rear + 1) % MAXSIZE == S->front) {
		printf("队列已满。");
		return;
	}
	S->data[S->rear] = x;
	//S->rear++;	//指针后移不能直接++
	S->rear = (S->rear + 1) % MAXSIZE;
}

//出队
int Out_SeqQueue(PSeqQueue S) {
	if (S->rear == S->front) {
		printf("队列为空。");
		exit(-1);
	}
	int e;
	e = S->data[S->front];
	//同样的出队也不能直接front++;
	S->front = (S->front + 1) % MAXSIZE;
	return e;
}

//获取首元素
int Front_SeqQueue(SeqQueue S) {
	if (Empty_SeqQueue(S)) {
		printf("队列为空。");
		exit(-1);
	}
	return S.data[S.front];
}

//遍历队列
void Print_SeqQueue(SeqQueue S) {
	if (Empty_SeqQueue(S)) {
		printf("队列为空。");
		return;
	}
	int p = S.front;
	while (p != S.rear) {
		printf("%d  ", S.data[p]);
		p = (p + 1) % MAXSIZE;
	}
	printf("\n");
}

void main() {
	PSeqQueue PS;
	PS = Init_SeqQueue();
	int i, n, e;
	printf("请输入队列的元素个数:");
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		printf("请输入第%d个元素:", i + 1);
		scanf("%d", &e);
		In_SeqQueue(PS, e);
	}
	printf("遍历队列:\n");
	Print_SeqQueue(*PS);
	printf("队列长度为:%d\n", Length_SeqQueue(*PS));
	printf("出队,元素为:%d\n", Out_SeqQueue(PS));
	printf("队列的首元素为:%d\n", Front_SeqQueue(*PS));
	printf("遍历队列: \n");
	Print_SeqQueue(*PS);

}
点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注