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!
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.
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.
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)
{
@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.
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).
@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.
