2021-09-12 leetcode 数据结构队列 622.设计循环队列 c++

2023-01-16 08:10:30

队列简介

队列属于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;
}

码农公寓