1.逻辑结构2.物理结构
2.1 顺序队列2.2 链式队列 3.抽象数据类型
3.1 循环队列3.2 链式队列 4.队列的应用
4.1 队列在层次遍历中的应用4.2 队列在计算机系统中的应用 5. 结语
1.逻辑结构1.1 队列：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
1.2 队列是一种先进先出的线性表，允许插入的一段称为队尾，允许删除的一端称为队头。
1.3 插入通常称为入队，删除通常称为出队。
2.物理结构 2.1 顺序队列2.1.1 用一段连续的区域存储数据。队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。
#define OK 1
#define ERROR 0
#define Status int
#define ElemType int
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int front;//队头指针
int rear; //队尾指针
}SqQueue;
2.1.2 循环队列
普通的顺序队列存在一个问题，当不断入队出队时，front和rear都在增大，当rear=MaxSize 时队列好像已经满了，其实并没有，因为front此时并不是指向0。
举例子，如下图，1，2，3，4，5，6，7，8，9，10，11依次入队，1，2，3，4，5出队。此时rear已经=11就是MaxSize。但是栈中前五格仍然是可用的。
若此时入队元素，会产生“假溢出”。为了避免这种现象我们引出循环队列。
当指针位置=MaxSize-1时，它下个位置就是0。具体实现方法请看后面的抽象数据类型。此处物理结构与普通顺序队列一模一样。
2.2 链式队列2.2.1
通常使用带头结点的链表构造链式队列，front指向头节点，front->next是队头元素，rear指向最后一个节点，rear->data即是队尾元素。
#define OK 1
#define ERROR 0
#define Status int
#define ElemType int
typedef struct LNode{ //链表数据节点
ElemType data;
LNode* next;
}LNode;
typedef struct { //链式队列
LNode* front;
LNode* rear;
}linkQueue;
2.2.2 双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列。我们可以很形象的理解为两个栈的栈底和一起，并且联通了。也可以理解为一个队列，队头队尾都可以插入和删除。
输出受限的双端队列：一边可以插入删除，一边只能插入。
输入受限的双端队列：一边可以插入删除，一边只能删除。
相关问题大家查找书籍视频，因为一般不会涉及这样的结构。
3.抽象数据类型 3.1 循环队列(前言：由于普通队列和循环队列的物理结构一样，循环队列更加实用，而且操作差不多，只是判空和判满条件不一样，所以此处我们实现循环队列)
3.1.1 初始化循环队列与队列判空
Status initRSqQueue(SqQueue& Q) {
Q.front = Q.rear = 0;
return OK;
}
Status RSqQueueEmpty(SqQueue Q) {
if (Q.front == Q.rear)
return OK;
else return ERROR;
}
3.1.2 队列判满
Status RSqQueueFull(SqQueue Q) {
if ((Q.rear + 1) % MaxSize == Q.front)//取余实现循环
return OK;
else return ERROR;
}
3.1.3 入队列
Status EnRSqQueue(SqQueue& Q, ElemType e) {
if (RSqQueueFull(Q)) return ERROR;
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % MaxSize; //取余实现循环
return OK;
}
3.1.4 出队列
Status DeRSqQueue(SqQueue& Q, ElemType &e) {
if (RSqQueueEmpty(Q) == OK)
return ERROR;
e = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return OK;
}
3.1.5 取队头元素
Status GetRSqQueueHead(SqQueue& Q, ElemType &e) {
if (RSqQueueEmpty(Q) == OK)
return ERROR;
e = Q.data[Q.front];
return OK;
}
3.1.6 打印队列
Status RSqQueuePrint(SqQueue Q) {//形参，不是原来的Q
ElemType e;
while (!RSqQueueEmpty(Q)) {
DeRSqQueue(Q, e);
cout << e;
cout << "t";
}
cout << "t打印结束" << endl;
return OK;
}
3.1.7 实验
int main() {
SqQueue Q;
ElemType e;
initRSqQueue(Q);
cout << "请输入元素(9999停止输入)：" << endl;
cin >> e;
while (e != 9999) {
EnRSqQueue(Q, e);
cin >> e;
}
RSqQueuePrint(Q);
}
3.2 链式队列
3.2.1 初始化队列
Status initlinkQueue(linkQueue& Q) {
Q.front = Q.rear = (LNode*)malloc(sizeof(LNode));//头节点
if (!Q.front) {
cout << "申请空间错误" << endl;
exit(1);
}
Q.front->next = NULL;
return OK;
}
3.2.2 队列判空
Status linkQueueEmpty(linkQueue Q) {
if (Q.front == Q.rear)
return OK;
else return ERROR;
}
3.2.3 入队列
Status EnlinkQueue(linkQueue& Q, ElemType e) {
LNode* s = NULL;
s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
return OK;
}
3.2.3 出队列
Status DelinkQueue(linkQueue& Q, ElemType &e) {
LNode* p = NULL;
if (linkQueueEmpty(Q)) return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;//删除节点
if (p == Q.rear) {//最后一个节点
Q.rear = Q.front;
}
free(p); //释放p节点空间
return OK;
}
3.2.4 打印队列
Status linkQueuePrint(linkQueue Q) {
ElemType e;
while (!linkQueueEmpty(Q)) {
DelinkQueue(Q, e);
cout << e;
cout << "t";
}
cout << "打印完成" << endl;
return OK;
}
3.2.5 实验
int main() {
linkQueue Q;
ElemType e;
initlinkQueue(Q);
cout << "请输入元素(9999停止输入)：" << endl;
cin >> e;
while (e != 9999) {
EnlinkQueue(Q, e);
cin >> e;
}
linkQueuePrint(Q);
}
4.队列的应用
4.1 队列在层次遍历中的应用
在二叉树章节我们再仔细学习。
4.2 队列在计算机系统中的应用例如在操作系统中的各种资源分配，排队等。学习过操作系统的同学一定很了解。此处了解即可，不会用我们敲代码的。
5. 结语通过前面几节的学习，如果代码都亲手敲了一次，一定会觉得这一节非常简单吧。至少我明显的感觉出，我敲出来的代码几乎都不会产生编译错误了，而前几节敲完还要去debug。继续努力！
