循环队列 | 而我独缺 你一生的了解
Cobb 558 0

注意 /* 重点突出: 在循环队列中,动态开辟值得再次关注 动态开辟思路: 不能直接拷贝,因为可能是一个圈,要从front开始一个一个拷贝到新的节点里 */

知识储备

// C语言中: NULL --> (void*)0 // C++ 中 : NULL --> 0 int data = NULL; 无法区分空指针和整数 0 // C++11 空指针优化: nullptr


#include <iostream>

using namespace std;

class Queue
{

public:

    // 构造, 默认参数
    Queue(int size = 20)
    {
        this->que_ = new int[size];
        this->front_ = 0;
        this->rear_ = 0;
        this->capacity_ = size;
    }
    // 析构
    ~Queue()
    {
        // 释放 重置
        delete[] this->que_;
        this->que_ = nullptr;
    }

    // 入队
    void Push(int val)
    {
        // 判断队列不满的情况下才可入队     加1取模
        if ((this->rear_ + 1) % this->capacity_ == this->front_)
        {
            // 2倍扩容
            Expand(2 * this->capacity_);
        }
        // 入队
        this->que_[this->rear_] = val;
        // 队尾走向下一个位置
        this->rear_ = (this->rear_ + 1) % capacity_;
    }

    // 出队
    void Pop()
    {
        if (this->Empty())
            return;
        this->front_ = (this->front_ + 1) % this->capacity_;
    }

    // 获取队头元素
    int Front()
    {
        // front_ 就是队头,直接取
        return this->que_[this->front_];
    }

    // 队空
    bool Empty()
    {
        // 头尾相同为空
        return this->front_ == this->rear_;
    }

    // 队满
    bool Full()
    {
        return this->front_ == (this->rear_ + 1) % this->capacity_;
    }

private:
    void Expand(int size)
    {
        // 申请一片原来2倍的空间,初始化为0
        int* p = new int[size] {};

        // 从头拷贝到新数组里
        int i = 0;  // 新数组
        int j = this->front_; // 旧数组
        for (; j != this->rear_; i++, j = (this->front_ + 1) % this->capacity_)
        {
            if (Empty())
            {
                p[i] = this->que_[j];
            }
        }

        delete[]this->que_;

        this->que_ = p;
        this->front_ = 0;
        this->rear_ = i;
        // 容量相应的扩大相应的倍
        this->capacity_ = size;
    }
private:
    // 指向指针的数组,队头,队尾,容量
    int* que_;
    int front_;
    int rear_;
    int capacity_;
};

int main()
{
    Queue que;
    que.Push(12);
    que.Push(23);
    que.Push(24);
    que.Push(64);
    que.Push(54);
    que.Push(76);
    que.Push(67);

    while (!que.Empty())
    {
        cout << que.Front() << endl;
        que.Pop();
    }

}

评论区