一、队列的相关概念和定义

试想一下，有的时候电脑像死机一样，鼠标点什么都没用。而过了一会却好像酒醒了一样把你刚才的操作都顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。这实际上是一种先进先出的思想，我们称之为队列。
队列的应用非常广泛：
举例：键盘输入，显示器上记事本软件的输出等等。。包括操作系统的各种准备队列，就绪队列。。都是先进先出的典型。
队列的定义：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表（First in first out，FIFO，先进先出）。

循环队列

队列作为一个线性表，也有顺序存储和链式存储两种方式。
队列顺序存储的不足：

• 首先，队列顺序存储一个固定长度的序列，并向其中添加n个元素。若再添加元素只需加到队尾即可，时间复杂度为O(1)。
• 然而，出栈时是队头出栈。因此，如果下次想再让队头出栈，则需要把所有元素往前移动一位，即把下标为1的元素移动到下标为0的地方，时间复杂度为O(n)，并且是每次出栈一个元素就要重复执行一次。
• 为避免这种情况，我们就引入两个指针front和rear分别指向队头和队尾。令front==rear时，队列为空。rear指向末尾元素的后面一位。这样可以避免队列满时也会出现front==rear的情况。

问题1：当最后一个元素插到分配地址的末尾，而前面有空位置，那么rear指针何去何从？
答：再重头开始，将rear指针插到最前面的分配的地址空间。
我们将这种队列称之为循环队列。
问题2：rear可能比front大，也可能比front小，那么如何判断？
答：两者最少相差1的内存空间（可能只相差1个位置，也可能是一圈，看rear在前面还是后面），这个时间我们就判断是满了。若队列的最大尺寸是Queuesize，那么队列满了的条件是(rear+1)%Queuesize==front（取模以后就整合了rear与front的大小前后两个位置各自的问题）。
问题3：队列长度计算公式：

• rear>front时，长度为rear-front。
• rear<front时，分两段。第一段为Queuesize-front，第二段为0+rear，合起来就是rear-front+Queuesize。
  因此通用计算长度为(rear-front+Queuesize)%Queuesize。

注意：此为顺序存储结构的方法。

链式队列

链式队列实际上就是线性表的单链表，只不过它只能尾进头出而已。尾进就用尾插法，头出可以参考一下栈的Pop（）函数。
此时，rear没有必要空出一个元素，因为链式队列存储空间一般是用不完的，除非内存已满。

二、队列的代码实现

循环队列

//SeqQueue.h

#ifndef SEQQUEUE_H_
#define SEQQUEUE_H_
const int Queuesize = 10;
class SeqQueue
{
private:
    int num[Queuesize];
    int front;
    int rear;
public:
    SeqQueue();
    ~SeqQueue();
    void EnQueue(int e);
    void DeQueue();
    int length();
    void Print();
};
#endif

//SeqQueue.cpp

#include<iostream>
#include"SeqQueue.h"
using std::cout;
using std::endl;
SeqQueue::SeqQueue()
{
    front = rear = 0;
}
SeqQueue::~SeqQueue()
{
}
void SeqQueue::EnQueue(int e)
{
    if((rear+1)%Queuesize == front)//判断是否为满队列
        return;
    num[rear] = e;//把尾部加上元素
    rear = (rear+1)%Queuesize;//尾部向后一位
}
void SeqQueue::DeQueue()
{
    if(front == rear)//判断是否为空队列
        return;
    front = (front+1)%Queuesize;//front向后一位
}
int SeqQueue::length()
{
    return (rear-front+Queuesize)%Queuesize;
}
void SeqQueue::Print()
{
    for (int i=front;i!=rear;i=(i+1)%Queuesize)
    {
        cout << num[i] << " ";
    }
    cout << endl;
    cout << "Length: " << length() << endl;
}

//Test.cpp

#include<iostream>
#include"SeqQueue.h"
using namespace std;
int main()
{
    SeqQueue S;
    for (int i=0;i<5;i++)
    {
        S.EnQueue(i);
        S.Print();
    }
    for (int i=0;i<2;i++)
    {
        S.DeQueue();
        S.Print();
    }
    return 0;
}

输出结果：

输出结果.png

链式队列回来再补。