数据结构第十篇——顺序队列

和栈相反，队列（queue）是一种先进先出（First In First Out,FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素、这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端称为队头(front)。

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。

在允许多道程序运行的计算机系统中，同时有借个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接收新的输出任务时，队头的作业先从队列中退出，做输出操作。凡是申请输出的作业都从队尾进入队列。

队列的操作与栈的操作类似，不同的是删除在表的头部（即队头）进行。

队列的实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方式这篇主要介绍顺序队列，链队列请转至http://www.cnblogs.com/tenjl-exv/p/7619963.html。

在队列的顺序存储结构中，与顺序栈类似，用数组存放表中元素，另外设置两个指针分别指向队头和队尾的位置。顺序队定义如下：

const int MaxQSize=50;
class Queue
{
    int front;
    int rear;
    Data QueueList[MaxQSize];
    
    public:
        Queue();                    //初始化数据成员 
        ~Queue();
        
        void EnQueue(Data item);            //入队 
        Data DeQueue();            //出队 
        Data GetFront();            //取队头元素值 
        void ClearQueue();            //清空队列 
        bool IsEmpty();                //判断空否 
        bool IsFull();                    //判断满否 
        int  Length();                 //求元素个数 
};

　　我们约定：初始化建立空队时，令front=rear=0；每当队尾插入新元素时，“尾指针增1”；每当队头删除一个元素时，“头指针增1”。因此头指针front总是指向队头元素，队尾指针rear总是指向队尾元素的下一个位置（这样设置是为了某些运算的方便，并不是唯一的方法）；判断队空的条件是队头指针和队尾指针相同。
　　随着入队出队的进行，会使整个队列整体向后移动，这样就出现了队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于队尾入，队头出的受限操作，以及为避免数据元素移动，队头队尾不固定造成的。

解决假溢出的方法有：

①固定队头，出队后，队列中的所有元素向前移动。

②固定队尾，入队时，队列中的所有元素向前移动。

③将队列的数据区看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。

　　前两种方法在入队和出队时需要移动队列中所有元素，第三种方法则不需要移动数据元素，是一种更好的方法。

循环队列的算法操作算法描述如下：

Queue::Queue()
{
    front=rear=0;
}

//入队操作 
void Queue::EnQueue(Data item)
{
    if((rear+1)%MaxQSize==front)
    {
        cout<<"队列已满"<<endl;
        exit(0);
    } 
    else
    {
        QueueList[rear]=item;
        rear=(rear+1)%MaxQSize;
    }
}

//出队操作
Data Queue::DeQueue()
{
    if(front==real)
    {
        cout<<"队列已空"<<endl;
        exit(0);
    }
    Data e=QueueList[front];
    front=(front+1)%MaxQSize;
    return e;
} 

//清空队列
void Queue::ClearQueue() 
{
    rear=front;
}

//判断空否
bool Queue::IsEmpty()
{
    if(rear==front)    return true;
    else                    return false;
} 

//判断满否
bool Queue::IsFull()
{
    if((rear+1)%MaxQSize==front)    return true;
    else                                    return false;
} 

//取队头元素值
inline Data Queue::GetFront()
{
    return QueueList[front];
} 

//析构函数
inline Queue::~Queue()
{
    return (rear-front+MaxQSize)%MaxQSize;
} 

以上操作都与队列中元素个数无关，时间复杂度为O(1)。
v、