Original Post
Hi, I'm trying to implement a queue class in C++ for my data structures course. The program seems to run fine, but on exit, Visual C++ tells me: Windows has triggered a breakpoint in exp.exe. This may be due to a corruption of the heap, which indicates a bug in exp.exe or any of the DLLs it has loaded. I can't figure out why this is happening. My guess would be that there's a problem with the part of the code that reallocates more memory for the data structure when the user adds more elements than the queue could originally hold (this is in the push function below). Here's my class: Queue.h And here's a little test program, which works as expected (though it doesn't test all functionality of the class): main.cpp Thank you, I would really appreciate your help! [Edited by - v0dKA on April 23, 2009 1:11:26 AM]
#pragma once
#include <stdexcept>
#include <iostream>
template<class T>
class Queue
{
public:
Queue(void);
~Queue(void);
/**
* IsEmpty - Returns true if the queue has no elements.
*/
bool IsEmpty() const;
/**
* size - Returns the number of elements in the queue.
*/
int size() const;
/**
* front - Returns the oldest element in the queue, without
* removing the element from the queue.
*/
T& front() const;
/**
* back - Returns the most recently added element in the queue,
* without removing it from the queue.
*/
T& back() const;
/**
* pop - Dequeues the oldest element in the queue.
*/
void pop();
/**
* push - Adds a new element to the back of the queue.
* @theElement: the element to be added.
*/
void push(const T& theElement);
// TEMPORARILY PUBLIC, FOR DEBUGGING
/**
* capacity - The number of elements the queue can currently
* hold based on the amount of memory allocated to it.
* Distinct from the number of elements actually in
* the queue.
*/
unsigned int capacity;
private:
/**
* The number of elements actually in the queue (as opposed
* to capacity).
*/
unsigned int q_size;
/**
* The elements of the queue itself.
*/
T *theQueue;
/*
* Points to the current start and end of the queue.
*/
T *q_front, *q_rear;
};
template<class T>
Queue<T>::Queue(void)
{
capacity = 10;
theQueue = new T[capacity];
q_size = 0;
q_front = theQueue;
q_rear = theQueue + (capacity-1);
}
template<class T>
Queue<T>::~Queue(void)
{
delete [] theQueue;
}
template<class T>
bool Queue<T>::IsEmpty() const
{
return (q_size == 0);
}
template<class T>
int Queue<T>::size() const
{
return q_size;
}
template<class T>
T& Queue<T>::front() const
{
if (q_size <= 0)
throw std::out_of_range("Attempted to retrieve front item of an empty queue.");
return *q_front;
}
template<class T>
T& Queue<T>::back() const
{
if (q_size <= 0)
throw std::out_of_range("Attempted to retrieve rear item of an empty queue.");
return *q_rear;
}
template<class T>
void Queue<T>::pop()
{
if (q_size <= 0)
{
std::cout << "Warning: pop() called on empty queue. Ignoring request." << std::endl;
return;
}
T *t_front = theQueue + q_front;
delete t_front;
--q_size;
++q_front;
if (q_front - theQueue >= (int)capacity)
q_front = theQueue;
}
template<class T>
void Queue<T>::push(const T& theElement)
{
if (q_size == capacity)
{
// Allocate more capacity.
capacity *= 2;
T *newQueue = new T[capacity];
memcpy(newQueue, theQueue, q_size*sizeof(T));
unsigned int frontOffset = q_front - theQueue;
delete [] theQueue;
theQueue = newQueue;
q_front = theQueue + frontOffset;
}
++q_size;
++q_rear;
if (q_rear - theQueue >= (int)capacity)
q_rear = theQueue;
*q_rear = theElement;
}
#include <iostream>
#include "Queue.h"
using namespace std;
void printinfo(Queue<int>& q)
{
cout << "Front=" << q.front()
<< ", Back=" << q.back()
<< ", Size=" << q.size()
<< ", Capacity=" << q.capacity
<< endl;
}
int main()
{
Queue<int> queue;
queue.push(1);
printinfo(queue);
queue.push(2);
printinfo(queue);
queue.push(3);
printinfo(queue);
queue.push(4);
printinfo(queue);
queue.push(5);
printinfo(queue);
queue.push(6);
printinfo(queue);
queue.push(7);
printinfo(queue);
queue.push(8);
printinfo(queue);
queue.push(9);
printinfo(queue);
queue.push(10);
printinfo(queue);
queue.push(11);
printinfo(queue);
queue.push(12);
printinfo(queue);
cin.get();
return 0;
}