[数据结构与算法]2021-09-18 队列

**

数据结构是相互之间存在一定联系或关系的数据元素的几何，直白地讲，就是研究数据的存储方式。

队列

**

先入先出的数据结构（FIFO）

今天是2021年9月18日，记录一下今天所学。

特点

队列是一个先入先出的数据结构，就和排队（或是流水线）一样，先到先得。

队列有两种操作：
（1）插入（insert）操作也称作入队（enqueue）操作，新元素始终被添加到队列的末尾。
（2）删除（delet）操作也称作出队（dequeue）操作，移除第一个元素，一般都会有一个指针指向的队列中最前面的元素。

今天所学到的是 循环队列：

使用一个固定大小的数组和两个指针，两个指针分别指向队列的起始位置和结束位置。

关键点：如何判断队列是空的还是满的？

总共有3种方法：

1.少用一个存储位置，即牺牲一个存储单元

队列为空时：Q.rear == Q.front
队列为满时：(Q.rear + 1) % maxsize == Q.front
maxsize-队列长度

2.设置一个标记位

设置初始标记：bool flag = false;

当入队时，Q.rear向后移动，flag = true
当出队时，Q.front向后移动，flag = false

队列为空时：Q.rear == Q.front && flag == false
队列为满时：Q.rear == Q.front && flag == true

3.计数count——队列中有效元素个数

初始：count = 0
入队：count += 1
出队： count -=1

count为0时，队列为空
count与队列的长度maxsize比较，相等时队列为满

代码：

class MyCircularQueue {
private:
    vector<int> array;
    int size;
    int head, tail; 
    bool flag = false;
public:
    MyCircularQueue(int k) {
        array.reserve(k);
        size = k;
        head = 0;
        tail = 0;
    }
    
    bool enQueue(int value) {
        if(isFull()){
            return false;
        } else {
            array[tail] = value;
            flag = true;
            tail = (tail + 1) % size;
            return true;
        }
    }
    
    bool deQueue() {
        if(isEmpty()){
            return false;
        } else {
            head = (head + 1) % size;
            flag = false;
            return true;
        }
    }
    
    int Front() {
        if(isEmpty()){
            return -1;
        } else {
            return array[head];
        }
    }
    
    int Rear() {
        if(isEmpty()){
            return -1;
        } else {
            return array[(tail - 1 + size)%size];
        }
    }
    
    bool isEmpty() {
        if (head == tail && flag == false){
            return true;
        } else {
            return false;
        }
    }
    
    bool isFull() {
        if (head == tail && flag == true){
            return true;
        } else {
            return false;
        }
    }
};

补充：vector是容器，与其他容器不同，其内存空间只会增长，不会减少，且使用时，可以用变量定义其长度。它的reserve（k）方法，是将vector的容量扩充至k

参考引用：
[1]: https://leetcode-cn.com/leetbook/read/queue-stack/k6zxm/
[2]: https://blog.csdn.net/lilililililiki/article/details/104317286?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link
[3]: https://www.cnblogs.com/Nonono-nw/p/3462183.html