队列-C

队列C

队列和栈一样，实质上都是表
区别：

栈：进/出栈只能在栈顶
队列：队头出队，队尾入队

将他队列抽象出来就像一个宽度只能容纳一个人的走廊，所有人只能从这个走廊的一端进入，从另一端走出，不能插队
进入的一端就是队尾，走出的一端就是队头

队列的操作

对栈的基本操作一般只有EnQueue(入队)和DeQueue(出队)

入队：就相当于是从末尾插入一个数据
出队：就相当于是删除第一个数据

数组循环队列

当我们使用数组来实现队列时，就会出现一个问题

首先来解释一下数组队列的操作逻辑

让一个数据入队，需要让队尾的下标+1，将数据赋值到相应的位置
让一个数据出队，需要让队头的下标+1

现在又下面这样一个存储在数组的队列，现在里面每一个下标都存储了相应的数据

现在我执行两次出队操作，也就是队头下标执行两次+1
其实这里数据还在，但是为了方便理解，就当作是被删除掉了

现在这个情况，如果再次执行入队的话，就超出了数组的长度，但是其实数组中还是有空的位置可以用来存储数据(也就是上图的下标0、1)，这样就会造成存储空间的浪费

为了解决这种存储空间浪费的问题，就出现了循环队列
循环队列就是在队头或者队尾到达数组的末尾时，就把他们又绕回数组的开头

就类似一个封闭的圆圈，当需要继续入队的话，就直接把队尾的下标移至0处，利用剩余的空间

数组队列

数据队列的结构体

typedef struct {
	QElemType* base; 
	int front;
	int rear;
}SqQueue;

base：存储数据的数组
front：存储队头下标
rear：存储队尾下标

初始化

创建一个固定长度的数组，并将队列的队头和队尾指向下标0

int InitQueue(SqQueue* queue) {
	queue->base = (SqQueue*)malloc(sizeof(SqQueue) * MAXQSSIZE);
	if (!queue->base) {
		return 0;
	}
	else {
		queue->front = queue->rear = 0;
		return 1;
	}
}

入队

int EnQueue(SqQueue* queue, QElemType elem) {
	if ((queue->rear + 1) % MAXQSSIZE == queue->front) {
		return 0;
	}
	else {
		queue->base[queue->rear] = elem;
		queue->rear = (queue->rear + 1) % MAXQSSIZE;
		return 1;
	}
}

(queue->rear + 1) % MAXQSSIZE == queue->front判断是否队满，这里为了与判断”队空”的queue->front == queue->rear做区分，所以牺牲了一个存储空间使用这个方法

将数据elem赋值给，base[rear]也就是队尾
队尾下标+1

出队

int DeQueue(SqQueue* queue, QElemType *elem) {
	if (queue->front == queue->rear) {
		return 0;
	}
	else {
		*elem = queue->base[queue->front];
		queue->front = (queue->front + 1) % MAXQSSIZE;
		return 1;
	}
}

如果有需要的话可以把queue->base[queue->front]的数据用*elem数据带出去
将下标为1的位置设置为队头

链表队列

链表队列的结构体

QNode是一个节点
LinkQueue是指向节点的队头指针和队尾指针

typedef struct QNode {
	QElemType data;
	struct QNode* next;
 }QNode,*QueueStr;

typedef struct {
	QueueStr front;
	QueueStr rear;
}LinkQueue;

初始化

int InitQueue(LinkQueue* queue) {
	queue->front = queue->rear = (QueueStr)malloc(sizeof(QNode));
	queue->front->next = NULL;
	return 1;
}

实例化了一个QNode节点，作为头节点，数据区域并不存储任何节点，将next指向NULL
将queue->front和queue->rear指向这个节点

入队

int EnQueue(LinkQueue* queue,QElemType elem) {
	QueueStr en_node;
	en_node = (QueueStr)malloc(sizeof(QNode));
	en_node->data = elem;
	en_node->next = NULL;
	queue->rear->next = en_node;
	queue->rear = en_node;
	return 1;
}

实例化一个QNode节点，并赋值给data
将原队尾节点的next指向en_node节点
最后将rear指向en_node节点

出队

int DeQueue(LinkQueue* queue, QElemType* elem) {
	QueueStr de_node;
	if (queue->front == queue->rear) {
		return 0;
	}
	else {
		de_node = queue->front->next;
		*elem = de_node->data;

		queue->front->next = de_node->next;

		if (queue->rear == de_node) {
			queue->rear = queue->front;
		}
		free(de_node);
		return 1;
	}
}