​ 队列也一个存储同一类型数据元素的线性表但是操作受限，和栈不同的是，队列是在一端存储，在另一端删除，通俗来讲就好像你排队打饭，只能在队首打饭，在队尾排队。特点就是先进先出（FIFO），而不同于栈的先进后出。

队列的顺序实现

定义
1
2
3
4
5
#define MaxSize 10//定义队列中元素的最大个数
typedef struct{
	ElemType data[MaxSizel;//用静态数组存放队列元素
	int front,rear;//队头指针和队尾指针
}SqQueue;

这里可以加入一个size来记录队列中的元素个数，便于判断队满。

初始化及判断
1
2
3
4
5
6
7
8
9
10
11
12
13
//初始化队列
void InitQueue(SqQueue &Q){
	//初始时队头、队尾指针指向0
	Q.rear=Q.front=0;
}
    
//判断队列是否为空
bool QueueEmpty(SqQueue &Q){
	if(Q.rear==Q.front)
		return true;
	else
		return false;
}
入队操作
1
2
3
4
5
6
7
8
9
//入队
bool EnQueue(SqQueue &Q,ElemType x){
	if（队列已满）
		return false;//队满则报错

	Q.data[Q.rear]=x;//将x插入队尾
	Q.rear=(Q.rear+1)%MaxSize;//队尾指针后移
	return true;
}

取模加一是因为在队头释放掉一部分，同时队尾指针指向MaxSize时，队列实际上是没有存满的，取模加一让其重新指向对头的空闲部分。

出队操作
1
2
3
4
5
6
7
8
9
//出队
（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front)//判断队空
	return false;//队空则报错
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize//队头指针后移
	return true;
}
查
1
2
3
4
5
6
7
//获得队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){
	if(Q.rear==Q.front)
		return false;//队空则报错
	x=Q.data[Q.front];
	return true;
}

队列的链式实现

​ 链式实现的队列几乎和链表一样，只是限制了增删元素的方式，也就其实是一个阉割版本的链表。

定义
1
2
3
4
5
6
7
typedef struct LinkNode{//链式队列结点
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{//链式队列
	LinkNode *front,*rear;//队列的队头和队尾指针
}LinkQueue;

同样也有带头节点和不带头节点的方式，各种操作的实现方式结合链表，较简单，我这里就不再赘述了，（其实是懒得写了）。