循環隊列是一種基于數組實現的隊列,當隊列滿時,需要進行擴容操作。動態擴容的機制是在隊列滿時,創建一個新的數組,將原數組中的元素復制到新數組中,并將隊列的頭指針和尾指針重新定位到新數組中。以下是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操作中,如果隊列已滿,則會執行擴容操作,將原隊列中的元素復制到新隊列中,并更新隊列的容量和指針位置。通過動態擴容機制,可以有效地解決循環隊列容量不足的問題。