Making A Queue

This is a discussion on Making A Queue within the C++ Programming forums, part of the General Programming Boards category; Hi guys, so I'm making a queue, but having a bit of trouble... The problem is with the way my ...

  1. #1
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230

    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!
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  2. #2
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    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.
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,893
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    Alright well I think I'll implement a linked-list and have the features you mentioned anon, cheers for the help both of you
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 02:55 AM
  3. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM
  5. queue help
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-29-2001, 08:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21