用数组实现队列

叶茂林

发布于 2024-07-06 08:22:50

1040

发布于 2024-07-06 08:22:50

文章被收录于专栏：叶子的开发者社区

队列用链表实现很简单，记住链表头和链表尾就行了，每次push就往头插入，每次pop就删掉尾巴

我们这里用数组实现一下队列，基本思想是一个循环滑动的窗口，用两个变量记录队首和队尾索引

push放到队尾，pop放到队首，队尾索引和队首索引都需要循环

这里比较难的是队列容量的动态增长，申请两倍的容量后，从队首索引开始拷贝

完整代码

class Queue {
    int volume = 8;
    int _size = 0;
    int back = 0;
    int front = 0;
    int *data = nullptr;

    void grow() {
        int *temp = new int[2 * volume];
        for (int i = 0; i < volume; ++i) {
            temp[i] = data[(front + i) % volume];
        }
        delete[]data;
        data = temp;
        volume *= 2;
    }

public:
    Queue() {
        data = new int[volume];
    }

    void push(int value) {
        ++_size;
        data[back] = value;
        if (_size == volume) {
            grow();
        }
        back = (back + 1) % volume;
    }

    int pop() {
        if (empty())
            return -1;
        --_size;
        int temp=data[front];
        front=(front+1)%volume;
        return temp;
    }

    bool empty() const {
        return _size == 0;
    }

    bool size() const {
        return _size;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

索引