I am new to programming and currently trying to learn data structures. I am currently trying to implement an array of queues of type array, however when deallocating memory using the delete [] queues statement, the program runs into a Heap corruption error. The issue seem to deal with the inner for loop + while loop, but I'm a bit confused. I have looked at other existing questions, which point me to a memory allocation problem. However, when I fill the queue array up to size N/2 I still run into the Heap corruption error. What is triggering this issue?
void queue_client(){
int M = 2;
int N = 10;
//create an array of queues
Queue_array<int>* queues = new Queue_array<int>[M];
//initialize each queue in the array of queues
for (int i = 0; i < N; i++) {
queues[i].set_array(N);
}
for (int i = 0; i < N; i++){
//randonly pick number to select and put in queue
int in = rand() % M, out = rand() % M;
queues[in].put(i);
std::cout << i << " in" <<std::endl;
//if current queues is not empty pop element out
if (!queues[out].empty()) {
std::cout << queues[out].get() << " out" << std::endl;
}
for (int k = 0; k < M; k++) {
//Queue_array<int> q = queues[k];
std::cout << k << ": ";
while (!queues[k].empty()) {
std::cout << queues[k].get() << " ";
}
}
}
//deallocate memory from array queue
delete[] queues;
}
Attached is the queue array class. The issue seems to be with my queue_array class, possibly the destructor?
#include<iostream>
template <class Item>
class Queue_array
{
private:
Item* q;
int N, head, tail;
void deleteList() {
delete [] q;
std::cout << "destructor" << std::endl;
}
public:
Queue_array(int maxN);
Queue_array();
~Queue_array();
Queue_array& operator=(Queue_array& rhs);
int empty();
void put(Item item);
Item get();
void print_elements();
int error(int);
bool search_element(Item);
int get_size();
void set_array(int);
};
template <class Item>
Queue_array<Item>::Queue_array(int maxN) {
q = new Item[maxN+1];
N = maxN+1;
head = N;
tail = 0;
}
template <class Item>
Queue_array<Item>::Queue_array() {
q = 0;
N = 0;
head = N;
tail = 0;
}
template <class Item>
Queue_array<Item>::~Queue_array() {
std::cout << "destructor invoked" << std::endl;
deleteList();
}
template <class Item>
Queue_array<Item>& Queue_array<Item>::operator=(Queue_array& rhs) {
//if both are the same queues return the queue
if (this == &rhs) {
return *this;
}
//clear all elements in current queue
deleteList();
this->set_array(rhs.get_size());
//pop all elements from rhs and put into current queue
while (!rhs.empty()) {
put(rhs.get());
}
return *this;
}
template<class Item>
void Queue_array<Item>::set_array(int val) {
N = val+1;
q = new Item[val+1];
head = N;
tail = 0;
}
template <class Item>
int Queue_array<Item>::empty() {
return (head % N == tail);
}
template<class Item>
void Queue_array<Item>::put(Item item) {
if (!error(2))
{
q[tail++] = item;
tail = tail % N;
}
}
template<class Item>
Item Queue_array<Item>::get() {
if (!error(1))
{
head = head % N;
return q[head++];
}
}
template<class Item>
void Queue_array<Item>::print_elements() {
std::cout <<"-----------------------" <<std::endl;
if (tail > head) {
//std::cout << "Head < Tail ";
for (int i = head; i < tail; i++) {
std::cout << q[i] << " ";
}
std::cout << std::endl;
}
else {
//std::cout << "Tail < Head ";
int i;
//if tail is less than head, that means array indexes has wrapped around.
//break print loops into two halves, from head to N and 0 to tails
for (i = head; i < N; i++) {
std::cout << q[i] << " ";
}
for (i = 0; i < tail; i++) {
std::cout << q[i] << " ";
}
std::cout << std::endl;
}
std::cout << "-----------------------" <<std::endl;
}
template<class Item>
int Queue_array<Item>::error(int mode) {
//if all elements are popped and head = tail
if (empty() && (mode==1)) {
//if first element is detected return 0
if (head == N) {
return 0;
}
else {
std::cout << "Error, queue is empty." << std::endl;
return 1;
}
}
//if tail wraps back to head (tail leads head, queue is full)
else if ((((tail%N) +1) == head) && (mode ==2)) {
//if tail is at last node, don't insert node
std::cout << "Error, queue is full." << std::endl;
return 1;
}
else {
return 0;
}
}
template<class Item>
bool Queue_array<Item>::search_element(Item x) {
int start = head;
if (start == N)
start = 0;
for (int i = start; i <= tail; i++) {
if (q[i] == x) {
return 1;
}
}
return 0;
}
template<class Item>
int Queue_array<Item>::get_size() {
return N;
}
I made tested the queue array and the destructor is being invoked correctly. The test client simply puts N int values in each of the M Queues.
void test_4_71() {
//test if destructor is working.
int M = 2;
int N = 10;
//create an array of queues
Queue_array<int>* queues = new Queue_array<int>[M];
//initialize each queue in the array of queues
for (int i = 0; i < M; i++) {
queues[i].set_array(N);
}
//push 0,1,2,...10 to arrays 1 and 2
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
queues[i].put(j);
std::cout << i << " in" << std::endl;
}
//pop all elements from arrays 1 and 2
for (int i = 0; i < M; i++) {
while (!queues[i].empty()) {
std::cout << queues[i].get() << " ";
}
std::cout << std::endl;
}
//deallocate memory from array queue
delete[]queues;
//std::cout << queues[0].get() << "test get" << std::endl;
}
