【数据结构】队列（链队列、循环队列）的存储结构及基本运算（C语言）

1. 队列基本概念2. 链队列

2.1 代码+注释2.2 运行结果 3. 循环队列

3.1 代码+注释3.2 运行结果

队列（Queue）是一种限定性线性表，它只允许在表的一端插入元素，而在另一端删除元素，具有先进先出的特点。在队列中，允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。
队列有顺序和链式两种常用存储表示。

链队列采用带头结点的链表结构，并设置一个队头指针 front 和一个队尾指针 rear ，队头指针始终指向头结点，队尾指针指向最后一个元素。空的链队列的队头指针和队尾指针均指向头结点。
链队列的基本操作包括初始化，队列创建，输出，入队，出队等。

# include
# include
# define TRUE 1
# define FALSE 0



typedef struct Node {
	int data;						//数据域
	struct Node* next;				//指针域
}linkQueueNode;

typedef struct {
	linkQueueNode* front;
	linkQueueNode* rear;
}linkQueue;


int InitQueue(linkQueue* Q) {
	Q->front = (linkQueueNode*)malloc(sizeof(linkQueueNode));
	if (Q->front != NULL) {
		Q->rear = Q->front;
		Q->front->next = NULL;
		return TRUE;
	}
	else
		return FALSE;				//溢出
}


void CreateQueue(linkQueue* Q) {
	linkQueueNode* NewNode;
	int c, flag = 1;
	while (flag) {
		scanf("%d", &c);
		if (c != 0) {
			NewNode = (linkQueueNode*)malloc(sizeof(linkQueueNode));
			NewNode->data = c;
			Q->rear->next = NewNode;	//新结点插入到队尾
			Q->rear = NewNode;			//修改队尾指针
		}
		else {
			flag = 0;
			NewNode->next = NULL;
		}
	}
}


int EnterQueue(linkQueue* Q, int x) {
	
	linkQueueNode* NewNode;
	NewNode = (linkQueueNode*)malloc(sizeof(linkQueueNode));
	if (NewNode != NULL) {
		NewNode->data = x;
		NewNode->next = NULL;
		Q->rear->next = NewNode;	//新结点插入到队尾
		Q->rear = NewNode;			//修改队尾指针
		return TRUE;
	}
	return FALSE;
}


int DeleteQueue(linkQueue* Q, int* x) {
	
	linkQueueNode* p;
	if (Q->front == Q->rear)		//空队列
		return FALSE;
	p = Q->front->next;				//p指向队头元素
	Q->front->next = p->next;		//队头元素p出队
	if (Q->rear == p)				//若队中只有一个元素p，则p出队后成为空队
		Q->rear = Q->front;
	*x = p->data;
	free(p);
	return TRUE;
}


void Display(linkQueue* Q) {
	if (Q->front == Q->rear)		//空队列
		printf("空队列！n");
	else {
		linkQueueNode* p;
		p = Q->front->next;			//p指向队头元素
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
		printf("n");
	}
}

int main() {
	int x;
	linkQueue Q;
	InitQueue(&Q);					//初始化

	printf("创建队列(以0结束)：");		//创建
	CreateQueue(&Q);
	printf("创建的队列元素为：");
	Display(&Q);

	EnterQueue(&Q, 5);				//入队
	printf("入队后队中元素为：");
	Display(&Q);

	DeleteQueue(&Q, &x);			//出队
	printf("出队元素为：%dn", x);
	printf("出队后队中元素为：");
	Display(&Q);
	return 0;
}

循环队列是一种顺序表示的队列，用一组地址连续的存储单元依次存放从队头到队尾的元素。由于队列中队头和队尾的位置是动态变化的，要附设两个指针 front 和 rear ，分别指示队头元素和队尾元素在数组中的位置。初始化队列时，令 front = rear = 0。
循环队列的基本操作包括初始化，队列创建，输出，入队，出队等。

# include
# include
# define TRUE 1
# define FALSE 0
# define MAXSIZE 50



typedef struct {
	int elem[MAXSIZE];
	int front;
	int rear;
}SeqQueue;


void InitQueue(SeqQueue* Q) {
	Q->front = Q->rear = 0;
}


void CreateQueue(SeqQueue* Q) {
	int c, flag = 1;
	while (flag) {
		scanf("%d", &c);
		if (c != 0) {
			Q->elem[Q->rear] = c;
			Q->rear++;
		}
		else {
			flag = 0;
		}
	}
}


int EnterQueue(SeqQueue* Q, int x) {

	if ((Q->rear + 1) % MAXSIZE == Q->front)	//队列已满
		return FALSE;
	Q->elem[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MAXSIZE;			//重新设置队尾指针
	return TRUE;
}


int DeleteQueue(SeqQueue* Q, int* x) {

	if (Q->front == Q->rear)					//队列为空
		return FALSE;
	*x = Q->elem[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;		//重新设置队头指针
	return TRUE;
}


void Display(SeqQueue* Q) {
	if (Q->front == Q->rear)					//队列为空
		printf("空队列！n");
	else {
		int i;
		for (i = Q->front; i < Q->rear; i++)
			printf("%d ", Q->elem[i]);
		printf("n");
	}
}

int main() {
	int x;
	SeqQueue Q;
	InitQueue(&Q);					//初始化

	printf("创建队列(以0结束)：");	//创建
	CreateQueue(&Q);
	printf("创建的队列元素为：");
	Display(&Q);

	EnterQueue(&Q, 5);				//入队
	printf("入队后队中元素为：");
	Display(&Q);

	DeleteQueue(&Q, &x);			//出队
	printf("出队元素为：%dn", x);
	printf("出队后队中元素为：");
	Display(&Q);
	return 0;
}

参考：耿国华《数据结构——用C语言描述（第二版）》

更多数据结构内容关注我的《数据结构》专栏：https://blog.csdn.net/weixin_51450101/category_11514538.html?spm=1001.2014.3001.5482