Jump to content
  • Advertisement
Sign in to follow this  
toogreat4u

Circular Linked List for Queue

This topic is 2532 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am having an issue in creating a circular linked list with a single tail pointer to be used for Queue implementation. I have a fairly decent idea of how it is done but I keep getting a compiling error when I try to enqueue an item and I am not sure what subtle point I am missing. I keep getting this error _BLOCK_TYPE_IS_VALID(pHead->nBlockUse) which I am guessing has to do with my pointers not being correct. Anyhow the nodes in the list are as follows:


struct Node
{
QueueItemType item; // QueueItemType is just an integer value for now
Node *next;
};

Node *tail;


The enqueue function look as follows:


void Queue::enqueue(QueueItemType newItem)
{
if(isEmpty())
{
tail = new Node;
tail->item = newItem;
tail->next = tail;
}
else
{
// not important right now
}
}


Anyhow I get the error after I perform the following in my main.cpp:


Queue que;

que.enqueue(1); // blows up in enqueue


I don't see what I have done incorrect and I hope someone else does see it because it makes sense to me lol. Anyhow any help is appreciated!

Share this post


Link to post
Share on other sites
Advertisement
is Node *tail a member of Queue? Is isEmpty() working. Could it be that isEmpty() checks the tail but because tail is never initialized it blows up?

Share this post


Link to post
Share on other sites

is Node *tail a member of Queue? Is isEmpty() working. Could it be that isEmpty() checks the tail but because tail is never initialized it blows up?


Yes *tail is a member of the Queue class. The isEmpty() should be working fine but I will show you the code for that just in case.


class Queue
{
public:
// stuff
private:
struct Node
{
QueueItemType item;
Node *next;
};
Node *tail;
};


The constructor and isEmpty are as follows:


Queue::Queue(): tail(NULL)
{}

bool Queue::isEmpty() const
{
return (tail == NULL);
}


see anything wrong...

Share this post


Link to post
Share on other sites
I don't see anything wrong. I put your code together and it runs without errors typedef int QueueItemType;

class Queue
{
public:
Queue();
bool isEmpty() const;
void enqueue(QueueItemType newItem);
private:
struct Node
{
QueueItemType item;
Node *next;
};
Node *tail;
};

Queue::Queue(): tail(0)
{}

bool Queue::isEmpty() const
{
return (tail == 0);
}

void Queue::enqueue(QueueItemType newItem)
{
if(isEmpty())
{
tail = new Node;
tail->item = newItem;
tail->next = tail;
}
else
{
// not important right now
}
}

int main()
{
Queue que;

que.enqueue(1);
}


Maybe the problem is other parts of the code?

Share this post


Link to post
Share on other sites

I don't see anything wrong. I put your code together and it runs without errors typedef int QueueItemType;

class Queue
{
public:
Queue();
bool isEmpty() const;
void enqueue(QueueItemType newItem);
private:
struct Node
{
QueueItemType item;
Node *next;
};
Node *tail;
};

Queue::Queue(): tail(0)
{}

bool Queue::isEmpty() const
{
return (tail == 0);
}

void Queue::enqueue(QueueItemType newItem)
{
if(isEmpty())
{
tail = new Node;
tail->item = newItem;
tail->next = tail;
}
else
{
// not important right now
}
}

int main()
{
Queue que;

que.enqueue(1);
}


Maybe the problem is other parts of the code?


Interesting... It appears that it is my destructor because if I comment its contents out I get no errors but again it looks like I am doing it correclty, grrr.


Queue::~Queue()
{
while(!isEmpty())
{
dequeue();
}
}

void Queue::dequeue()
{
if(!isEmpty())
{
Node *front = tail->next;
tail->next = front->next;

front->next = NULL;
delete front;
front = NULL;
}
}


See anything now lol, thanks for your help!

Share this post


Link to post
Share on other sites
EDIT: I got a bit confused by all these pointers but my conclusion is still correct I think.

If the list has only one element tail->next points to the same node as tail. This means that after the node has been deleted tail is a dangling pointer. tail should be set to null in this case.

Share this post


Link to post
Share on other sites
You've got to check for the case tail->next == tail, as well as some other issues, like this.
(BTW, dequeue only deletes one item, and serves no other purpose. It should probably take the tail item, remove it from the list and return that tail item. If you want to delete the whole list, just have a FreeQueue() call, that loops and deletes like dequeue() does now).

Your code, fixed:


void Queue::dequeue()
{
if(!isEmpty())
{
if (tail->next == tail)
{

// last item left
delete tail;
tail = NULL;
}
else
{
Node *temp = tail;
tail = tail->next;
delete temp;
}
}
}



The way I would do it:


void Queue::FreeQueue()
{
while(!isEmpty())
{
if (tail->next == tail)
{

// last item left
delete tail;
tail = NULL;
}
else
{
Node *temp = tail;
tail = tail->next;
delete temp;
}
}
}

// returns tail item, assumes user will free
Node *Queue::dequeue()
{
Node *retNode = tail;

// check for last item
if (tail == tail->next)
{
tail = NULL;
}
else
{
tail = tail-<next;
}
return retNode;
}

Share this post


Link to post
Share on other sites
@BeerNutts, I don't think it's a good idea to return a Node*. The user of the queue don't have to know there is a Node class, that is probably why the Node class is private. It is much better having a function returning the item of type QueueItemType. If dequeue() should return anything I don't know. It's up to toogreat4u to decide. If there is another function to access the next item you can return a QueueItemType& just like std::queue does.

Share this post


Link to post
Share on other sites
Linked list is the wrong underlying data structure for a queue. Linked list's primary benefit is that its easy and quick to pull out a node from the middle of the chain -- in other words, doing so does not require memory allocation or copying buffers. The downsides of linked lists, such as high memory overhead for small items and non-contiguous nature, are rather onerous to be suffering if you're not even using the primary advantage.

A vector is a much better underlying data structure -- its contiguous and, while it may shrink/expand and cause a buffer copy occasionally, this out to be relatively rare in a queue system unless shrinking is configured to be very aggressive.

Use a vector. Keep a head (read) and a tail (write). When head==tail, the queue is empty. When tail == vector.end, grow the vector (memory allocation and buffer copy take place here).

Of course, that assumes you want to do a queue the *right* way for educational purposes, not that you wan't to exercise a linked list for educational purposes, or that you just want to get stuff done (in which case you should be using std::queue).

Share this post


Link to post
Share on other sites
Hidden
@Ravyne, now I got curious. std::queue uses std::deque as underlying container. I wonder if std::deque is better than std::vector. std::queue can't use std::vector because it doesn't have pop_front(). Using a circular buffer strategy and std::vector could be quite good I guess, but the question is, what will perform best? I will have to make some tests.

Share this post


Link to post
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!