队列简介

队列属于FIFO数据结构
入队-enqueue：新元素始终添在队列末尾
出队-dequeue：移除第head指向元素

队列有顺序队列和链式队列

顺序队列

顺序队列简介

顺序队列采用数组存储队列中的元素，使用两个指针尾指针(rear)和头指针（front）分别指向队列的队头和队尾。

顺序队列的实现

该代码只能实现基本的入队出队

#include <iostream>

class MyQueue {
    private:
        vector<int> data;       
        int p_start;            
    public:
        MyQueue() {
        	p_start = 0;
        }
        bool enQueue(int x) {//入队
            data.push_back(x);
            return true;
        }
        bool deQueue() {//出队
            if (isEmpty()) {
                return false;
            }
            p_start++;
            return true;
        };
 
};

Problem：顺序队列，随着指针移动，空间复杂度增大
Solution：使用循环队列

循环队列

循环队列简介

使用固定大小的数组和两个指针来指向起始位置和结束位置。 以重用被浪费的存储空间。

循环队列实例

现向队列中入队 23

将tail向后移一位，由于循环回到第一位，可得：tail = (tail+1)%len (len为data数组长度）
将23存放，得：data[tail] = 23

循环队列实现具体思路

对应leetcode 622.设计循环队列

增添 count 变量—记录队列中元素的个数。
当count == len, 队列满 （len为data数组长度）
当count == 0 ,队列空

至于head,tail如何循环：当head，tail索引达到数组上限时，使用除余操作，使得索引值循环
除余操作：head = (head+1)%len; tail同理

循环队列的实现

在返回rear的值时，需要注意tail的位置。
由于是每次入队之后，tail再向后一个移动，所以返回rear时，返回的是data[tail-1]，若tail回到0，此时返回的是数组最后一个值，即data[len-1]

class MyCircularQueue {
private:
    vector<int> data;
    int head = 0;
    int tail = 0;
    int count = 0;
    int len;
public:
    MyCircularQueue(int k) {
        data.resize(k);
        len = data.size();
    }
    bool enQueue(int value) {
        if(isFull())
            return false;
        data[tail] = value;
        count++;
        tail++;
        tail %= len;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty())
            return false;
        head = (head + 1) % len;
        count--;
        return true;
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return data[head];
    }
    
    int Rear() {
        if(isEmpty())
            return -1;
        return tail == 0 ? data[len-1] : data[tail-1]; 
    }
    
    bool isEmpty() {
        return count == 0;
    }
    
    bool isFull() {
        return count == len;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

内置队列库常见操作示例

#include <iostream>

int main() {
    // 1. 初始化队列
    queue<int> q;
    // 2. Push new element. 入队
    q.push(5);
    q.push(13);
    q.push(8);
    q.push(6);
    // 3. 检查是否为空
    if (q.empty()) {
        cout << "Queue is empty!" << endl;
        return 0;
    }
    // 4. 出队
    q.pop();
    // 5. 获取头元素
    cout << "The first element is: " << q.front() << endl;
    // 6. 获取尾元素
    cout << "The last element is: " << q.back() << endl;
    // 7. 获取此时队列长度
    cout << "The size is: " << q.size() << endl;
}

链式队列

链式队列简介

链式队列：操作受限的单向链表

链式队列构造

链式队列 = 单向链表+front指针+rear指针
以下是链式队列构造的实现

typedef struct QNode//声明链式队列的节点
{
    int data;//数据域
    struct QNode *next; //指针域（指针域和结点的地址类型相同）
}Node;
typedef struct QueuePoint// 声明链式队列的首尾指针
{
    Node *front;
    Node *rear;
}Queue;

链式队列入队的实现

step1: 队列初始化（将头节点放入队列中）头节点不存储数据，使队首指针和队尾指针都指向头节点

step2:使rear指向新建的节点，front不变仍然指向头节点

代码实现如下

//step1：队列初始化
typedef struct QNode//声明链式队列的节点
{
    int data;//数据域
    struct QNode *next; //指针域（指针域和节点的地址类型相同）
}QNode;
typedef struct Queue// 声明链式队列的首尾指针
{
    Node *front;
    Node *rear;
}Queue;
//step2:入队
QNode* enQueue(QNode *rear,int data){
	//1.将入队元素存为新节点
    QNode *enElem=(QNode*)malloc(sizeof(QNode)); 
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与现rear建立关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    return rear;
}

链式队列出队的实现

step1:front指针始终指向头节点，头节点的指针域指向出队节点的后一节点
step2:将出队的节点用free（）函数释放掉

代码实现如下

void DeQueue(QNode * front,QNode * rear){
    if (front->next==nullptr) {
        return ;
    }
    //step1
    QNode * p=front->next;
    front->next=p->next;
    if (rear==p) {
        rear=front;
    }
    //step2
    free(p);
}