前言
队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表**。队列是一种先进先出(First Input First Ouput)，的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。**
既然是线性表，那么就可以分为顺序存储结构和链式存储结构。
队列存储结构的实现有以下两种方式：
顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；
本文将在链队列的基础上实现队列子系统，题目如下：
1.设计一个选择式菜单。
2.设计一个整型数据元素的链队列。
3.编写入队、出队、读队首元素、显示队列中全部元素的程序。
4.编写求解报数问题的应用程序，要求给出他们的出列顺序。
注：所谓报数问题，设n个人站成一排，从左到右的编号分别为1～n，从左到右报数“1,2,3,1,2,3”，数到“1”和“2”的人出列，数到“3”的人立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。
如：n＝10时，初始序列为1 2 3 4 5 6 7 8 9 10，
出列顺序为1 2 4 5 7 8 10 3 9 6。
一、顺序队列
由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如图所示
1：顺序队列入队
由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素(首先出队数据的位置)和队尾(最后出队数据的后一个位置)元素所在数组位置的下标。
在上图的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。
例如，在上图的基础上将 {1,2,3,4} 用顺序队列存储的实现操作如下图所示：
在上图的基础上，我们知道出队其实就是top指针指向下一个数据，如下图所示：
当然，如果接着插入数据5，6，那么假设这个数组只能容纳5个数据，那么数据6就溢出了，但是明明数组下标0，1，2的空间都还没存放元素，因此由于头铁而直接把数据插入在数组后面造成的溢出称为“假溢出”，因为我们可以把数据6放在a[0]位置，这样就解决了假溢出的问题，那么应该如何做到才可以解决这个问题呢，没错，让数组尾和数组头连接，也就是后面满了，再从头开始。这样的顺序存储结构称为循环队列。
紧接着入队a6，将它放置再下标为0处，此时rear指针指向下标为1处，如下图所示：
但是发现如果我们继续填充数据，那么就会出现下图的情况：
但是rear=front的条件是队列为空时设定的，那么我们可以修改队列为满时的条件，我们可以保留一个元素空间，也就是说，队列满的时候，数组中还有一个空闲单元，如下图：
由于rear可能比front大，也可能比front小，所以尽管他们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为Size，那么队列满的条件就是(rear+1)%Size==front,（取模"%"的目的就是为了整合rear和front大小为一个问题)。比如上左图，(4+1)%5==0成立，如上右图，(1+1)%5==2成立，因此队列满，如果不符合这个条件，那么队列不满(可以自己实验)。
另外,当rear>front时，此时队列长度为rear-front，但是如果rear<front，队列长度应该分为两段，一段是Size-front(据图可以计算处下标2到下标5是3个元素)，另一段是rear-0(rear下标减去0下标，就可以知道rear到0有多少个元素了，如下图可以得出是1个)，因此通用的计算队列长度的公式为：
(rear-front+Size)&Size。
介绍完了基本概念以及基本写法，接下来就是如何写出顺序队列的代码。
我们可以将顺序队列的代码分为几个实现：
1：队列初始化 2：队列插入数据 3：队列删除数据 4：队列求长
5：返回队列头元素 6：显示队列全部元素
2：顺序队列出队
出队较为简单，这是由于出队的一定是队首指向的元素，因此只需将队首指向的元素指向下一个要出队的元素即可。直接看代码中的DeQueue()函数即可
3：完整代码
#pragma once #include<iostream> #include <cstdio> #include<cstdlib> typedef int Status; typedef int ElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 5 #define make (struct student*)malloc(sizeof(struct student)); using namespace std; int status = 0;//全局状态标志位 如果执行了销毁队列操作则置1 typedef struct queue { ElemType data[MAXSIZE]; int front; int rear; }Queue; void menu(void) { cout << "********************" << endl; cout << "*1 ……入队 *" << endl; cout << "*2 ……出队 *" << endl; cout << "*3 ……读队首元素 *" << endl; cout << "*4 ……显示 *" << endl; cout << "*5 ……销毁队列 *" << endl; cout << "*0 ……退出 *" << endl; cout << "********************" << endl; } Queue* InitQueue(Queue* q) //队列初始化 { q->front = 0; q->rear = 0; return q; } Status DestoryQueue(Queue* q)//销毁队列 { if (q) { free(q); cout << "删除成功" << endl; status = 1; return OK; } else { cout << "队列未创建" << endl; return ERROR; } } Queue* ClearQueue(Queue* q) //清空队列 { if (q) { free(q); cout << "清空成功" << endl; Queue* head = (Queue*)malloc(sizeof(Queue)); return head; } else { cout << "未存在队列" << endl; cout << "请先创建一个队列" << endl; exit(0); } } Status GetHead(const Queue* q, ElemType* e)//返回队列头 { if ((q) && (q->front != q->rear))//队列非空 { cout << "队头元素是" << q->data[q->front] << endl; *e = q->data[q->front]; return OK; } else { cout << "队列为空或队列不存在" << endl; return ERROR; } } Status EndQueue(Queue* q, ElemType e)//队尾插入元素 最多能插入MAXSIZE-1个数据 { if ((q->rear + 1) % MAXSIZE == q->front)//队列满 { cout << "队列已满" << endl; return ERROR; } q->data[q->rear] = e; q->rear = (q->rear + 1) % MAXSIZE;//指针后移 cout << "插入成功" << endl; return OK; } Status DeQueue(Queue* q, ElemType* e)//删除队头元素 { if (q && (q->front == q->rear)) { cout << "队列为空" << endl; return ERROR; } *e = q->data[q->front]; cout << "队头元素为" << *e << endl; q->front = (q->front + 1) % MAXSIZE; //头指向下一个数据 return OK; } int QueueLength(const Queue q)//获得队列长 { return (MAXSIZE - q.front + q.rear) % MAXSIZE; cout << "长度为" << (MAXSIZE - q.front + q.rear) % MAXSIZE << endl; } void ShowQueue(Queue q)//显示所有数据 { if (status==0)//还未执行销毁操作 { int i = 0; cout << "长度" << (MAXSIZE - q.front + q.rear) % MAXSIZE << endl; while ((q.front) % MAXSIZE != q.rear) { cout << "第" << i++ << "个数据是" << q.data[q.front++] << endl; } } else { cout << "队列不存在" << endl; exit(-1); } } int main() { int choose; ElemType e; menu(); Queue* head = (Queue*)malloc(sizeof(Queue)); InitQueue(head); while (1) { cout << "请选择功能" << endl; cin >> choose; switch (choose) { case 1: { cout << "输入要入队的数据" << endl; cin >> e; EndQueue(head, e); break; } case 2: { DeQueue(head, &e); break; } case 3: { GetHead(head, &e); break; } case 4: { ShowQueue(*head); break; } case 5: { DestoryQueue(head); break; } case 0: { cout << "感谢使用，bye！" << endl; exit(0); break; } default: break; } } }
4：运行结果
