C++循环队列的动态扩容机制-开发者知识库平台

C++循环队列的动态扩容机制

c++

744

2024/7/4 10:20:32

栏目: 编程语言

循环队列是一种基于数组实现的队列，当队列满时，需要进行扩容操作。动态扩容的机制是在队列满时，创建一个新的数组，将原数组中的元素复制到新数组中，并将队列的头指针和尾指针重新定位到新数组中。以下是C++实现循环队列动态扩容的示例代码：

#include <iostream>

class CircularQueue {
private:
    int* queue;
    int capacity;
    int size;
    int front;
    int rear;

public:
    CircularQueue(int capacity) {
        this->capacity = capacity;
        queue = new int[capacity];
        size = 0;
        front = 0;
        rear = -1;
    }

    void enqueue(int value) {
        if (isFull()) {
            // 扩容操作
            int newCapacity = capacity * 2;
            int* newQueue = new int[newCapacity];

            // 将原队列中的元素复制到新队列中
            for (int i = 0; i < size; i++) {
                newQueue[i] = queue[(front + i) % capacity];
            }

            delete[] queue;
            queue = newQueue;
            capacity = newCapacity;
            front = 0;
            rear = size - 1;
        }

        rear = (rear + 1) % capacity;
        queue[rear] = value;
        size++;
    }

    int dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty" << std::endl;
            return -1;
        }

        int value = queue[front];
        front = (front + 1) % capacity;
        size--;
        return value;
    }

    bool isFull() {
        return size == capacity;
    }

    bool isEmpty() {
        return size == 0;
    }
};

int main() {
    CircularQueue q(5);

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);

    // 队列已满，需要进行扩容
    q.enqueue(6);
    q.enqueue(7);

    std::cout << q.dequeue() << std::endl;
    std::cout << q.dequeue() << std::endl;

    return 0;
}

在enqueue操作中，如果队列已满，则会执行扩容操作，将原队列中的元素复制到新队列中，并更新队列的容量和指针位置。通过动态扩容机制，可以有效地解决循环队列容量不足的问题。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

C++循环队列的动态扩容机制

最新知识库

相关标签