用数组实现队列

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

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

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

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

完整代码

代码语言：javascript复制

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;
    }
};

索引 int 队列 链表 数组

0 人点赞