Sign in to follow this  
toogreat4u

Circular Linked List for Queue

Recommended Posts

toogreat4u    127
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:

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

Node *tail;
[/code]

The enqueue function look as follows:

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

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

[code]
Queue que;

que.enqueue(1); // blows up in enqueue
[/code]

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
Wooh    1088
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
toogreat4u    127
[quote name='Wooh' timestamp='1313076289' post='4847714']
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?
[/quote]

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.

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

The constructor and isEmpty are as follows:

[code]
Queue::Queue(): tail(NULL)
{}

bool Queue::isEmpty() const
{
return (tail == NULL);
}
[/code]

see anything wrong...

Share this post


Link to post
Share on other sites
Wooh    1088
I don't see anything wrong. I put your code together and it runs without errors [code]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);
}
[/code]

Maybe the problem is other parts of the code?

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='Wooh' timestamp='1313077644' post='4847725']
I don't see anything wrong. I put your code together and it runs without errors [code]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);
}
[/code]

Maybe the problem is other parts of the code?
[/quote]

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.

[code]
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;
}
}
[/code]

See anything now lol, thanks for your help!

Share this post


Link to post
Share on other sites
Wooh    1088
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
BeerNutts    4400
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:
[code]

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;
}
}
}
[/code]


The way I would do it:

[code]
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;
}
[/code]

Share this post


Link to post
Share on other sites
Wooh    1088
@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
Ravyne    14300
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
Wooh    1088
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
way2lazy2care    790
[quote name='Wooh' timestamp='1313102765' post='4847980']
@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.
[/quote]

The actual error message you're getting is because you are trying to write to memory that is already written to or invalid in some other way. Still looking through your code, but that might give you some ideas.

edit: maybe it has to do with queue not being initialized? double edit: nah that shouldn't be it.

triple edit: I think it has to do with "[color="#000000"][color="#1C2837"][font="CourierNew, monospace"][size="2"][color="#000000"][color="#000000"]tail [/color][/color][/size][/font][/color][/color][color="#666600"][color="#1C2837"][font="CourierNew, monospace"][size="2"][color="#666600"][color="#666600"]=[/color][/color][/size][/font][/color][/color][color="#000000"][color="#1C2837"][font="CourierNew, monospace"][size="2"] [/size][/font][/color][/color][color="#000088"][color="#1C2837"][font="CourierNew, monospace"][size="2"][color="#000088"][color="#000088"]new[/color][/color][/size][/font][/color][/color][color="#000000"][color="#1C2837"][font="CourierNew, monospace"][size="2"] [/size][/font][/color][/color][color="#660066"][color="#1C2837"][font="CourierNew, monospace"][size="2"][color="#660066"][color="#660066"]Node[/color][/color][/size][/font][/color][/color][font="CourierNew, monospace"][color="#1C2837"][size="2"];[/size][/color][/font][font="Arial"][size="2"]" This calls the default constructor on Node, which calls the default constructor on everything else including the Node* inside Node, which does not exist. If you define a default constructor in Node that doesn't try to call a constructor for a pointer that might fix it. You might want to do that anyway so you can pass in the item and maybe the pointer.[/size][/font]

Share this post


Link to post
Share on other sites
BeerNutts    4400
[quote name='Wooh' timestamp='1313098008' post='4847932']
@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.
[/quote]

Yeah, true, I was just pointing out dequeue really doesn't do anything useful by itself.

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='Ravyne' timestamp='1313100515' post='4847962']
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).
[/quote]

I agree with your statement however this little exercise is for my own educational benefit, it comes from a data abstraction book and they ask that you build this kind of internal structure for the Queue. Thanks for your response as I enjoy hearing how this *really* should be done. I would normally just use std::queue but I am trying to go with the flow of the book. Thanks!

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='Wooh' timestamp='1313098008' post='4847932']
@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.
[/quote]

I do have a second dequeue function that has this type of function call:

void Queue::dequeue(QueueItemType& dataItem);

Where the dataItem is the item that is being deleted. Thanks!

Share this post


Link to post
Share on other sites
Antheus    2409
[quote name='toogreat4u' timestamp='1313156099' post='4848215']
I do have a second dequeue function that has this type of function call:

void Queue::dequeue(QueueItemType& dataItem);

Where the dataItem is the item that is being deleted. Thanks!
[/quote]

What does it return if the queue is empty?

[quote] it comes from a data abstraction book and they ask that you build this kind of internal structure for the Queue[/quote]

Sadly, just like with OO and many other concepts, books simply teach the wrong things. They try to teach acadmic CS which fails hard in real world due to specifics of a language and ignores crucial real world issues.

Any book that teaches data structures in C++ and does not use STL interface is simply wrong. And even those aren't perfect. There is a reason why STL doesn't provide tree structure, for example. And I have yet to see any such example do anything about running out of memory or dealing with overflow. CS doesn't deal with such irrelevant details but that just pushes designs into wrong direction.

It's so much more ironic considering CS likes to talk of O(n) when n goes to infinity, while none of the algorithms presented can even deal with 32-bit address space limitation. So from CS point of view, all such implementations tend to be O(1) - they work in constant amortized time, since there is a perfect upper bound on n, invalidating most of properties "proven" for such data structures.

It's similar to mathematicians working with Pi, but using 3 as its value and "ignore the trivial implementation details".

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='Antheus' timestamp='1313156480' post='4848219']
[quote name='toogreat4u' timestamp='1313156099' post='4848215']
I do have a second dequeue function that has this type of function call:

void Queue::dequeue(QueueItemType& dataItem);

Where the dataItem is the item that is being deleted. Thanks!
[/quote]

What does it return if the queue is empty?

[quote] it comes from a data abstraction book and they ask that you build this kind of internal structure for the Queue[/quote]

Sadly, just like with OO and many other concepts, books simply teach the wrong things. They try to teach acadmic CS which fails hard in real world due to specifics of a language and ignores crucial real world issues.

Any book that teaches data structures in C++ and does not use STL interface is simply wrong. And even those aren't perfect. There is a reason why STL doesn't provide tree structure, for example. And I have yet to see any such example do anything about running out of memory or dealing with overflow. CS doesn't deal with such irrelevant details but that just pushes designs into wrong direction.

It's so much more ironic considering CS likes to talk of O(n) when n goes to infinity, while none of the algorithms presented can even deal with 32-bit address space limitation. So from CS point of view, all such implementations tend to be O(1) - they work in constant amortized time, since there is a perfect upper bound on n, invalidating most of properties "proven" for such data structures.

It's similar to mathematicians working with Pi, but using 3 as its value and "ignore the trivial implementation details".
[/quote]

Yeah I couldn't agree more with your statement. I graduated 2 years ago with a Computer Science degree and I have been a developer for little over a year now and I can't explain how frustrating it is to see 90% of what I learned in school is irrelevant in the work force. The only thing I will say that the CS has given me is a much deeper understanding of what is going on behind the scenes and measuring a functions/programs efficiency. The school I went to we were never allowed to use STLs period so everything we wrote came from scratch, however I have been asked several times to produce a Queue/Stack/Binary Tree/Double Linked List for the 'test' question during an interview.

The dequeue currently just returns garabage value but I have used a throw clause before and that would be the appropriate way to handle this type of dequeue attempt I think.

The following is how I would handle it with a throw statement:

[code]
void Queue::dequeue(QueueItemType &dataItem) throw(QueueException)
{
if(isEmpty())
{
throw QueueException("Empty queue, can not dequeue");
}
// else dequeue this sucka!!
}
[/code]

Share this post


Link to post
Share on other sites
Antheus    2409
[quote name='toogreat4u' timestamp='1313168268' post='4848307']
The following is how I would handle it with a throw statement:

[code]void Queue::dequeue(QueueItemType &dataItem) throw(QueueException)
{
if(isEmpty())
{
throw QueueException("Empty queue, can not dequeue");
}
// else dequeue this sucka!!
}
[/code]
[/quote]

[code]bool tryDequeue(QueueItemType & out) {
if (isEmpty()) return false;
...
return true;
}[/code]

[quote] to see 90% of what I learned in school is irrelevant in the work force[/quote]

That's a different problem. In same way many electronic shops specifically do not want or reject EEs. They want technicians, not engineers. University education is completely redundant for majority of software jobs and efficient companies have long ago perfected 3 week programming courses that result in more suitable workforce regardless of education.

What CS teaches is similar to physics and "frictionless vacuum" problems. It serves as a basis, but schools fail to expand that into actually useful examples and impact on problems being solved in real world.


My point was - books that teach algorithms should either cover the whole shebang, theory to real world or ignore everything and say: Here is std::dequeue, deal with it. The middle-ground is mostly just a ton of confusion that ends up in endless and unproductive half-work.

Share this post


Link to post
Share on other sites
BeerNutts    4400
[quote name='toogreat4u' timestamp='1313168268' post='4848307']

Yeah I couldn't agree more with your statement. I graduated 2 years ago with a Computer Science degree and I have been a developer for little over a year now and I can't explain how frustrating it is to see 90% of what I learned in school is irrelevant in the work force.
[/quote]

I'm quite surprised you graduated from a University with a Computer Science degree and you can't do this Circular Linked-list. That's not much of an endorsement for your school.

In my 1st CS class, we wrote Circular Lists in Pseudo-code, my 2nd Class we did it in Pascal, and my 3rd, we did it in C. That was 1 year of CS, with 3 more to go.

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='BeerNutts' timestamp='1313172990' post='4848345']
[quote name='toogreat4u' timestamp='1313168268' post='4848307']
Yeah I couldn't agree more with your statement. I graduated 2 years ago with a Computer Science degree and I have been a developer for little over a year now and I can't explain how frustrating it is to see 90% of what I learned in school is irrelevant in the work force.
[/quote]

I'm quite surprised you graduated from a University with a Computer Science degree and you can't do this Circular Linked-list. That's not much of an endorsement for your school.

In my 1st CS class, we wrote Circular Lists in Pseudo-code, my 2nd Class we did it in Pascal, and my 3rd, we did it in C. That was 1 year of CS, with 3 more to go.


[/quote]

I am quite certain that I did implement a circular linked list at some point during my time in college. I just have not had a need to implement these structures in quite some time so I decided to bust out the old books and refresh my memory on how all the behind the scenes stuff works. The University that I went to we spent most of our time going over theories and algorithm design more so then coding. I think for major universities that is pretty common. I mostly work with the Qt API now so a lot of the data structures are available through their libraries and all I have to do is know which one is the most efficient for what I am trying to do. I agree that I am a weaker programmer then most of my peers but I was always much stronger at the Math stuff then most :).

Share this post


Link to post
Share on other sites
way2lazy2care    790
[quote name='toogreat4u' timestamp='1313174291' post='4848358']
I am quite certain that I did implement a circular linked list at some point during my time in college. I just have not had a need to implement these structures in quite some time so I decided to bust out the old books and refresh my memory on how all the behind the scenes stuff works. The University that I went to we spent most of our time going over theories and algorithm design more so then coding. I think for major universities that is pretty common. I mostly work with the Qt API now so a lot of the data structures are available through their libraries and all I have to do is know which one is the most efficient for what I am trying to do. I agree that I am a weaker programmer then most of my peers but I was always much stronger at the Math stuff then most :).
[/quote]
Did you actually solve the problem in the op yet or did you just give up on it?

Share this post


Link to post
Share on other sites
toogreat4u    127
[quote name='way2lazy2care' timestamp='1313176367' post='4848373']
[quote name='toogreat4u' timestamp='1313174291' post='4848358']
I am quite certain that I did implement a circular linked list at some point during my time in college. I just have not had a need to implement these structures in quite some time so I decided to bust out the old books and refresh my memory on how all the behind the scenes stuff works. The University that I went to we spent most of our time going over theories and algorithm design more so then coding. I think for major universities that is pretty common. I mostly work with the Qt API now so a lot of the data structures are available through their libraries and all I have to do is know which one is the most efficient for what I am trying to do. I agree that I am a weaker programmer then most of my peers but I was always much stronger at the Math stuff then most :).
[/quote]
Did you actually solve the problem in the op yet or did you just give up on it?
[/quote]

Yes I have actually, I saw what I was doing wrong when I wasn't accounting for the special case of when tail == tail->next. I also found an error in the enqueue() function because I was not allocating the pointers correctly. The final dequeue and enqueue is as follows:

[code]
void Queue::dequeue()
{
if(!isEmpty())
{
if(tail->next == tail)
{
tail->next = NULL;
delete tail;
tail = NULL;
}
else
{
Node *front = tail->next;
tail->next = front->next;
front->next = NULL;
delete front;
front = NULL;
}
}
else
{
cout << "Can not dequeue from queue, queue is empty\n";
}
}

void Queue::enqueue(QueueItemType newItem)
{
if(isEmpty())
{
tail = new Node;
tail->item = newItem;
tail->next = tail;
}
else
{
Node *newPtr = new Node;
newPtr->item = newItem;
newPtr->next = tail->next;
tail->next = newPtr;
tail = newPtr;
}
}
[/code]

So in simple yes I have with the help of people in this forum :). The main mistake I made was forgetting to account for the special case of tail->next == tail. Thanks!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this