Queue

队列

队列这种逻辑结构，也能用顺序表和链表实现，本次主要讲用顺序结构实现的循环队列。

队列是一种被限制的线性表，只能在队列的队头进行删除，在队尾进行增加

循环队列

首先，我们要先认识一下循环队列。这里的循环队列，我们用顺序结构（数组）实现。

从逻辑上，把队头和队尾拼接起来。（当指针指向队尾，再往前移动一个位置，就%MaxSize）

结构

typedef struct {
	ElemType data[MaxSize];
	int front;//指向队头元素
	int rear;//指向队尾元素的下一个元素
} SqQueue;

要面临的两个问题是：

1. 队列为空的条件。

2. 队列为满的条件。

由于队列在增加和删除的过程中，元素在队列中的序号是变化的，所以不能像栈一样用常量-1表示。所以，我们定义q.front == q.rear即队列为空。定义(q.rear + 1) % MaxSize == q.front队列为满。

流程图

基本操作

循环队列不像顺序表和链表那样把元素真正增加，删除，而是去更改头尾指针。

出入队时，都让指针往顺时针方向进1

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MaxSize 5
#define ElemType int

typedef struct {
	ElemType data[MaxSize];
	int front;
	int rear;
} SqQueue;

void Init(SqQueue &q) {
	q.front = q.rear = 0;
}

bool IsEmpty(SqQueue q) {
	if (q.front == q.rear) {
		return true;
	}
	return false;
}

bool IsFull(SqQueue q) {
	if ((q.rear + 1) % MaxSize == q.front) {
		return true;
	}
	return false;
}

bool EnQueue(SqQueue& q, ElemType e) {
	if (IsFull(q)) {
		return false;
	}
	q.data[q.rear] = e;
	q.rear = (q.rear + 1) % MaxSize;
	return true;
}

bool DeQueue(SqQueue& q, ElemType &e) {
	if (IsEmpty(q)) {
		return false;
	}
	e = q.data[q.front];
	q.front = (q.front + 1) % MaxSize;
	return true;
}

链队列

这类似于单链表，与单链表最大的不同是，它是由一个头指针front和尾指针rear，只用他们来操作单链表。

结构

//队列节点
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;

//队列头尾指针
typedef struct {
	LinkNode* front;
	LinkNode* rear;
}LinkQueue;

1. 队列为空的条件

   front==rear

流程图

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 5
#define ElemType int
//队列节点
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;

//队列头尾指针
typedef struct {
	LinkNode* front;
	LinkNode* rear;
}LinkQueue;

void InitQueue(LinkQueue& lq) {
	//头节点
	LinkNode* s = (LinkNode *)malloc(sizeof(LinkNode));
	s->next = NULL;

	lq.front = lq.rear = s;
}

void EnQueue(LinkQueue& lq,ElemType e) {
	//新节点
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	//尾插法
	lq.rear->next = s;
	//更新链队列（头尾指针）
	lq.rear = s;
}

bool IsEmpty(LinkQueue lq) {
	if (lq.front == lq.rear) {
		return true;
	}
	return false;
}

bool DeQueue(LinkQueue& lq, ElemType& e) {
	if (IsEmpty(lq)) {
		return false;
	}
	//先让p指向第一个元素
	LinkNode* p = lq.front->next;
	e = p->data;
	//修改指针
	lq.front->next = p->next;
	//判断是否为最后一个元素，是就让头尾指针指向头节点。
	if (lq.rear == p) {
		lq.rear = lq.front;
	}
	free(p);
	return true;
}

int main() {
	LinkQueue lq;
	InitQueue(lq);
	EnQueue(lq, 3);
	EnQueue(lq, 4);
	EnQueue(lq, 5);
	ElemType e;
	while (!IsEmpty(lq))
	{
		DeQueue(lq, e);
		printf("%2d", e);
	}
	return 0;
}