队列相关知识整理

一. 队列简介

队列也是一种特殊的线性表
队列只允许在表的一段插入，另一端删除，而栈只允许在表的末端入和删除
队列中允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）
队列是先进先出，而栈是先进后出
队列的表示也有两种方法：基于数组的存储表示和基于链表的存储表示（常用）

二. 基于数组的存储表示

2.1 实现步骤

为了充分利用数组的存储空间，避免假溢出的等现象的发生。这里采用循环数列，所谓循环数列，就是把数组的前端和后端连接起来，形成一个环形的表。虽然用if和else也可以实现循环队列，但是我们用取余的方法能更好的实现：

出队的时候，队头指针进1（也是队顶）：

front = (front + 1) % maxSize;//maxSize 为数组的最大长度

入队的时候，队尾指针进1（也是队底）：

real = (real + 1) % maxSize;

队列初始化：

front = real = 0;

判断队列是否为空的条件：

front == real;

判断队列是否为满的条件：

注意，因为是循环数列，所以如果第n + 1个元素入队的时候，front和rear的值是相同的，但是上面我们front == real 是用来判断队列是否为空的条件，两者就会产生矛盾，为了避免这种情况的发生，我们让rear指到front的前一个位置就人为队已经满了，这样虽然数组中有一个空间是浪费的，但是能区别于对空的条件

（real + 1） % maxSize == front；

2.2 完整代码：

#include<iostream>
using namespace std;
class Queue
{
private:
    int *e;//创建一个指针，用于指向数组
    int size;//数组的最大长度
    int front,rear;
public:
    Queue(int sz = 10)
    {
        e = new int [10];
        size = sz;
        front = rear = 0;
    }
    ~Queue()
    {
        delete[] e;
    }
    bool enQueue(int x);//入队
    bool deQueue(int &x);//出队
    bool isEmpty()//判断队列是否为空
    {
        return front == rear;
    }
    bool isFull()//判断队列是否为满
    {
        return (rear + 1) % size == front;
    }
    bool getTop(int &x);//获取队顶的元素
};

bool Queue :: getTop(int &x)
{
    if(isEmpty()) return false;
    x = e[(front + 1) % size];
    return true;
}

bool Queue :: enQueue(int x)
{
    if(isFull()) return false;
    rear = (rear + 1) % size;
    e[rear] = x;
//注意上面入队的方法，rear先加1，再入队，有的书中是先入队再加1，本质上是一样的
//因为循环数列需要空出一个位置，先加1再入队，空的是第0个位置，先入队再加1，空的是最后一个位置
//下面的出队的方法同理
    return true;
}

bool Queue :: deQueue(int &x)
{
    if(isEmpty()) return false;
    front = (front + 1) % size;
    x = e[front];
    return true;
}

int main()
{
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    int x;
    while(! q.isEmpty())
    {
        q.deQueue(x);
        cout << x;
    }

    return 0;
}