队列

1.队列的性质（先进先出）：

• 新元素插入队尾（新来的同学站在最后面）
• 出队方案唯一（队伍买饭的先后顺序确定）
• 队首元素先出（站在前面的同学先买饭）

2.进队，出队，删除等操作的实现

#include <iostream>
#include <cassert>
using namespace std;
class Queue {
private:
    int *data;
    int head, tail, length;
public:
    Queue(int length_input) {           //构造函数
        data = new int[length_input];
        length = length_input;
        head = 0;
        tail = -1;
    }
    ~Queue() {                         //析构函数
        delete[] data;
    }
    void push(int element) {               //加入队列函数
        if (tail + 1 < length) {           //判断队列是否有位置可插入
            tail++;                         
            data[tail] = element;
        }
    }
    void output() {                       //将整个队列输出              
        for (int i = head; i <= tail; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
    int front(){                            //队首元素的输出
        assert(head<=tail);              //宏断言，判断队列是否为空，为空则终止程序
        return data[head];               //不为空，返回队首元素
    }
    void pop(){                         //删除队首元素
        assert(head<=tail);             //宏断言，判断队列是否为空，为空则终止程序
        head++;                        //不为空，head向后移动一位，表示删除队首元素
    }
};
int main() {
    Queue queue(100);
    for (int i = 1; i <= 10; i++) {
        queue.push(i);
    }
    queue.output();
    cout<<queue.front()<<endl;
    queue.pop();
    queue.output();
    return 0;
}

 3.循环队列：

前面讲到的队列实现方式有一个问题：“假上溢”。什么叫“假上溢”呢？回忆一下之前的插入队列的代码：

 void push(int element) {               //加入队列函数
         if (tail + 1 < length) {           //判断队列是否有位置可插入
             tail++;                         
             data[tail] = element;
         }
     }

当 tail 达到队列的上限后就不能在插入了，此时再插入就意味着溢出。但是 tail 达到上限后就意味着要插入的元素真的『无处可放』了么？能不能构造出一个队列无法加入元素，但队列并没有满的例子？

回忆一下删除队首元素的操作

void pop(){                         //删除队首元素
        assert(head<=tail);             //宏断言，判断队列是否为空，为空则终止程序
         head++;                        //不为空，head向后移动一位，表示删除队首元素
     }

如果一个队列在不断的执行插入、弹出、插入、弹出……那么可以想象，当执行到 tail 达到队列上限之后，便不能再插入到队列中了，而此时队列其实是空的。

对于这种存储区没有用满，而队列却发生了溢出的现象，我们称之为“假上溢”，也叫“假溢出”。

能不能想出一种解决方案，能将所有的存储区充分利用起来呢？

       循环队列，顾名思义，就是以循环的方式来存储队列。回顾一下我们之前用到的队尾标记 tail。对于循环队列，当队尾标记 tail 到达数组的上界后，如果队列内的元素个数没有达到容量上限，就跳转到数组的起始位置，也就是 0 的位置；队首标记 head 到达数组上界采取同样的处理。通过这样的方法，我们就能够最大化利用内存空间，避免“假上溢”的情况出现啦。

性质：

• 在循环队列里，如果容量没有达到上限，当队尾队首标记达到数组上界后，就跳转到数组起始位置
• 循环队列里通过统计队列里元素个数，判断能否继续往队列里插入元素

循环队列的入队，出队和遍历

#include <iostream>
#include <cassert>
using namespace std;
class Queue {
private:
    int *data;
    int head, tail, length, count;   //增加一个count用来存储当前队列中一共有多少个元素
public:
    Queue(int length_input) {
        data = new int[length_input];
        length = length_input;
        head = 0;
        tail = -1;
        count = 0;
    }
    ~Queue() {
        delete[] data;
    }
    bool push(int element) {
        if (count < length) {
            tail = (tail + 1) % length;
            data[tail] = element;
            count++;
            return true;
        } else {
            return false;
        }
    }
    void output() {
        for (int i = head; i != tail + 1; i = (i + 1) % length) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
    int front() {
        assert(count>0);
        return data[head];
    }
    void pop() {
        assert(count>0);
        head=(head+1)%length;
        count--;
    }
};
int main() {
    Queue queue(100); 
    for (int i = 1; i <= 10; i++) {
        queue.push(i);
    }
    queue.output();
    cout << queue.front() << endl;
    queue.pop();    
    queue.output();
    return 0;
}