我正在尝试使用循环数组实现队列。我的代码应该能够从队列中删除最小的数字。我创建了测试代码,应该输出1 2 3 4 5作为被删除的最小值,但我的实际输出是3 2 1 8 7。我不确定我的问题是找到最小值的代码不正确还是我编写实际队列的方式有问题。我怀疑两者都有问题,但我希望能得到任何建议或提示来找出我的代码中的问题。
#include <iostream>
using namespace std;
class priorityQueue
{
private:
int front;
int rear;
int size;
int *array;
public:
priorityQueue();
~priorityQueue();
void insert(int x);
//remove and return the smallest item currently in the priority queue
int extractMin();
bool empty();
};
priorityQueue::priorityQueue()
{
front = rear = -1;
size = 10;
array = new int[size];
}
priorityQueue::~priorityQueue()
{
delete[] array;
}
void priorityQueue::insert(int x)
{
//if queue is full
if ( (rear + 1)% size == front ){
return;
}
//else if queue is empty
else if ( empty() ){
rear = front = 0;
}
else
{
rear = (rear + 1) % size;
}
array[rear] = x;
}
//extract and return smallest value in queue
int priorityQueue::extractMin()
{
int minValue = array[front];
if ( empty() ){
return -1;
}
else if (front == rear){
front = rear = -1;
}
else
{
front = (front + 1) % size;
}
//find smallest value
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
minValue = array[i];
}
//return smallest value
return array[front];
}
bool priorityQueue::empty()
{
if ( (front == -1) && (rear == -1) )
return true;
else
return false;
}
int main()
{
priorityQueue myqueue;
myqueue.insert(4);
myqueue.insert(3);
myqueue.insert(2);
myqueue.insert(1);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
myqueue.insert(8);
myqueue.insert(7);
myqueue.insert(6);
myqueue.insert(5);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
system("pause");
return 0;
}
std::vector<int>
; 然后你可以删除你编写的析构函数,因为它将变得无用。一般来说,我建议你不要混合职责:一个类处理内存,一个类处理逻辑,这样两个类都会简单(并且可以独立测试)。 - Matthieu M.