一.队列以及其链式存储的介绍
二. 题目复现及分析
三. 代码展示（c++）
1. 队列：
属于线性表的一种，它的特殊点在于具有先进先出的特点（只允许在表头删除元素，表尾进行插入元素）。
同样的，它也有两种存储方式：顺序存储和链式存储。今天我们所完成的这道题就是使用队列的链式存储。如下图1所示：
图1
（1）front、next、rear 为队列结点类型的指针，指向队列节点。
（2）front、next分别为（一直）指向这一队列链表的头结点和尾节点。
（3）一般的，我们会多设置一个不存放data头结点。让front指针指向它，它指向下一个存放data的结点（首元结点），如图2，本题便用这种形式。
图2
2.学习中难理解点：
（1）为什么要设头指针front和尾指针rear？
因为队列要具有先进先出的特点，先入队的元素越靠近头部，因此可以直接利用头指针删除第一个结点；同样的可以直接利用尾指针添加结点。
（2）每个结点包括了什么？
一个存放数据data元素的数据域；一个存放该结点类型的指针next（指向下一个结点），用于联系每个结点的关系用以组成整个链表。
3.具体入队出队初始化操作在代码展示那注释
R7-6 队列操作 (20 分)
请实现一个MyQueue类，实现出队，入队，求队列长度.
实现入队函数 void push(int x); 实现出队函数 int pop(); 实现求队列长度函数 int size();
每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ，接下去n行每行一个数字，表示一种操作： 1 x ： 表示从队尾插入x，0<=x<=2^31-1。 2 ： 表示队首元素出队。 3 ： 表示求队列长度。
对于操作2,若队列为空，则输出 “Invalid”,否则请输出队首元素。 对于操作3，请输出队列长度。 每个输出项最后换行。
5
3
2
1 100
3
2（题目中还要求结尾无空行，但是我试过有空行还是会通过，所有我的代码没有考虑结尾无空行。如果要考虑进去，可以从它的操作次数n下手，当n==0时输出不带空格。）
0
Invalid
1
100#include<iostream>
using namespace std;
/*
队列Queue类，封装了队列结点、指向队头和队尾的指针以及队列的一些操作；
*/
class Queue {
private:
//队列结点
typedef struct QNode{
int data;
struct QNode*next;
}QNode,*Qpointer;
//指向队头和队尾的指针结构体
typedef struct {
Qpointer front;
Qpointer rear;
int size;
}LinkQueue;
private:
//声明一个队列指针结构体
LinkQueue linkq;
public:
//构造队列（初始化）
Queue() {
linkq.front=new QNode;//开辟一个队列结点（此时为头结点）类型内存，让linkq的头指针指向该内存
linkq.rear=linkq.front;//让尾指针暂时指向头指针
linkq.front->next=NULL;//头节点next置NULL
linkq.size=0;//初始化队列长度为0；
}
//入队
void push(int x) {
//以下三行为开辟一个新队列结点，存放入队元素，同时next置NULL
QNode* p=new QNode;
p->data=x;
p->next=NULL;
//以下三行为将这个新结点接入队列链的尾部（此时这个新节点和队列链没有 任何关系）
linkq.rear->next=p;/*因为rear指针总指向最后一个结点，因此rear.next为最后一个结点的next指针。
这一步目的是将队列链尾结点指向新的结点，让新结点成为尾结点。*/
//另外，判断队空的条件就是rear是否指向front指针（front始终不动，指向第一个结点）
linkq.rear=p;//因为新结点成为了尾结点，rear指针自然的要更新其指向的结点，去指向这个新结点
linkq.size++;//每没入队一个结点，则长度加一；
}
//出队
int pop(bool& status) {
status=true;//这个status引用为了检查是否队空
int elem;
if(linkq.front==linkq.rear)//队空,status为false
{
status=false;
return -1;//结束
}
//若非空
QNode *q;//声明一个结点指针
q=linkq.front->next;/*让q指针指向该队链第一个存放data的结点,目的是方便取这个出队结点的data及判别该节点是否是
尾结点（front指向第一个结点即头结点，头节点的下一个元素才是存放data的结点）*/
//因为出队第一个存放data的结点，因此只要将front头指针指向该结点，而指向出队结点的下一个结点就行了
linkq.front->next=linkq.front->next->next;
if(linkq.rear==q)//队空
{
/*若要删除的结点恰好是尾结点，删除之后队链便没有了存放data的结点，为队空。因此我们
要让队尾rear指针重新指向front指向的存储位置（回到初始化时的状态）*/
linkq.rear=linkq.front;
}
elem=q->data;//返回出队结点的data
delete q;//释放出队结点的内存
linkq.size--;//队长度减一
return elem;
}
int getSize()//返回队列长度
{
return linkq.size;
}
};
int main()
{
Queue Q;//实例化一个Queue对象，并初始化Q
bool status;
int N;//控制操作次数
int frontelem;
int elem;
int choice;
cin>>N;
while(N--)
{
cin>>choice;
if(choice==1)
{
cin>>elem;
Q.push(elem);
}
else if(choice==2)
{
frontelem=Q.pop(status);
if(status)//判断是否队空
cout<<frontelem<<endl;
else
cout<<"Invalid"<<endl;
}
else if(choice==3)
{
cout<<Q.getSize()<<endl;
}
}
}