Thread: Making A Queue

Hi guys, so I'm making a queue, but having a bit of trouble... The problem is with the way my pop() function works. What I want it to do is return the array's 0th element, and then increase the address the array holds by 1, which would change the 0th element to the 1st element. Unfortunately I'm not very good at explaining it, so I hope you understand what I'm trying to say, I'll give a brief example so you guys actually know what I'm trying to do.

Say I have a pointer to an int:

Code:

int * pArray;
pArray = new int[100];

Say the 0th, 1st, 2nd elements of that array contain these values:

Code:

pArray[0] = 5;
pArray[1] = 10;
pArray[2] = 15;

This is my code:

Code:

return *this->pArray++;

Or another way:

Code:

return this->pArray++[0];

Anyway they both actually work, but they give crash errors. I took a screenshot, here's the link: http://img128.imageshack.us/my.php?image=wtfpu2.jpg

And here's the actual program code:

Code:

#include <iostream>
#include <cstdio>

using namespace std;

class queue {

public:
	queue();
	~queue() { delete pArray; }
	void push(int);
	int pop();

private:
	int * pArray;
	int count;

};

queue::queue() {

	pArray = new int[100];
	count = 0; 

}

void queue::push(int val) {

	this->pArray[count] = val;
	this->count++;

}

int queue::pop() {

		return *this->pArray++;

};



int main() {
	
	queue q;
	int val = 0;
	int amount = 0;

	cout << "Queue Program. Enter 4 numbers:\n\n";
	for (int x = 0; x < 5; x++) {
		cout << "#" << x+1 << ": ";
		cin >> val;
		cin.ignore();
		q.push(val);
	}

	cout << "How many items do you wish to pop: ";
	cin >> amount;

	if (amount > 0 && amount <= 5) {
		while (amount) {
			cout << q.pop() << endl;
			--amount;
		}
	}

	else cout << "Incorrect pop number.";

}

Cheers for the help!

Ok so I know the problem, since I'm changing the pointer/array, then calling delete on it, it's deleting a wrong block of memory. It's skipping memory that it's supposed to delete, because delete obviously deletes from the start of the pointer. And the block of memory was assigned a few addresses back. Is there any way around this? Aka a pointer to the first element, then make delete delete memory from that position or something? Alternatively I could use something like this:

Code:

int Queue::pop() {

		this->x++;
		this->pArray[0] = pArray[x-1];
		return this->pArray[0];

};

But that's ugly, and I'd prefer to fix my previous solution. Cheers.

Firstly, you should use delete[] pArray, not delete pArray.

Now, the problem with incrementing pArray itself is that you then change the very pointer that you want to use for delete[] pArray. Instead, keep the index of the front of the queue, and increment that instead.

Alternatively, you can do what std::queue does: use another container (e.g., std::list) to implement the queue. This relieves your queue class of the burden of manual memory management.

It is not very easy with an array, and you probably need to store more data about the queue. E.g the members might be:

Code:

    int* buffer; //the actual dynamic array
    int* begin; //points to the head where popping occurs, initially == buffer
    int* end; //points to the end where pushed values go, initially == buffer
    int* max; //points to one-past-end of buffer, used to avoid going out of bounds

And then in pop and push you need to make sure that the following conditions are met:

Code:

    void push(int n)
    {
        assert(end != max); //must have more room available
        //...
    }
    int pop()
    {
        assert(begin != end); //must not be empty
        //...
    }

Of course, if you run out of room while pushing, asserting might not be the correct behaviour. Instead you should probably try to make more room, by copying things around to the beginning of the buffer if begin != buffer (i.e items have been popped and there's empty unused space), or by allocating a larger buffer if that is not possible.

In addition, your queue needs a copy constructor and an overloaded assignment operator (otherwise you'll leak memory/cause double deletes if a queue is copied/assigned).

Alright well I think I'll implement a linked-list and have the features you mentioned anon, cheers for the help both of you