Queue made with pointers in C++, questions

[John O' Meara]

Can someone explain how the function queue::store(int i) (see attachment) works for a sequence of calls to it. Or give a reference to something or give a diagram, please.
Doesn't each instant (i.e., each memory location) have its own head, tail and next pointers as well as as the data member, num? A queue made from an array has only two indices; say called head and tail, and are much easier to understand.
After the first call to the store() function, say address 0x8000 is allocated, then the pointers are pointing as indicated on the attachment, yes/no?
On the 2nd call to store(), we have: "if(tail) tail->next = item;". Which tail is it- 0x8000 or 0x8020's? And then we have: "tail->next = item;". Why not say next = item; Is it the 'next' of the instant 0x8000 or 0x8020? confused. Please help, thanks in advance for your time.

 

[Adyssa]

I haven't done much C++ I'm afraid, but a queue is a FIFO data structure (first in first out), just like a queue at a supermarket. The head is the front of the queue. The tail is the back of the queue. Each element in the queue has a pointer to the next element (and in the case of the head element, it's next pointer is NULL).

When you store an element, it becomes the new tail, and it's ->next pointer points to the old tail element.

 

[chiro]

When it sets the tail element, its setting a class specific variable that is part of the "queue" class.

What happens is that the queue knows the "last tail" and through the data structure can traverse through the list until it finds no more structures.

So in a nutshell, the class specific variable points to the "last" or "first" node of the queue and from that you can traverse through the list in which the "tail" of an intermediate node (as well as the "next" variable) will determine the structure and values of each node in the queue.

 

[rcgldr]

I don't get the example code in the pdf file. The list class should not include head and tail pointers. Only the queue class should have head and tail pointers (to list elements). The queue store function should be doing a "new list", not a "new queue" to allocate a list element and append it to a specifc instance of queue by following and updating that queue's tail pointer (and updating the head pointer if the queue was previously empty).

 

[chiro]

I don't get the example code in the pdf file. The list class should not include head and tail pointers. Only the queue class should have head and tail pointers (to list elements). The queue store function should be doing a "new list", not a "new queue" to allocate a list element and append it to a specifc instance of queue by following and updating that queue's tail pointer (and updating the head pointer if the queue was previously empty).

I think the queue class inherits a "node" class. The reason I say this is because of the public statement in the definition of the queue class.

 

[rcgldr]

I think the queue class inherits a "node" class. The reason I say this is because of the public statement in the definition of the queue class.

The issue I have is with the handwritten list class that includes head and tail pointers, in addition to the store() function allocating a queue instead of a list.

If interested, here is a link to a zip of a sample windows multi-threaded application to copy a file which uses linked lists (queues) to communicate between two threads. One thread reads a source file, the other thread writes a destination file. There's a bit of overhead for setting up the mutexes and semaphores, but the actual code in ThreadFile0() and ThreadFile1() is very simple. AppendToList() adds a list element to the end of a list and GetFirstElement() retrieves the first element from the start of a list.

http://rcgldr.net/misc/mtcopy.zip

 

[chiro]

The functions you are talking about are pure virtual. He implements those in the concrete class (queue). As for the head and tail variables, I'm pretty sure they are both inherited from the list class.

I don't agree that it's the best implementation though.

 

[rcgldr]

An list item class shouldn't have head and tail pointers. A queue class shouldn't have a next pointer. It's a bad example for using inheritence.

 

[D H]

The functions you are talking about are pure virtual. He implements those in the concrete class (queue). As for the head and tail variables, I'm pretty sure they are both inherited from the list class.

Those obviously cannot be pure virtual in class list. If they were implemented in queue they would have to be declared in class queue. The class queue only adds two new members to class list, store and retrieve (plus the default constructor, copy constructor, assignment operator, and destructor, "free" courtesy of the language).

I don't agree that it's the best implementation though.

That is putting it nicely. From the single page you copied, this book falls into the class of "do not buy under any circumstances."

An list item class shouldn't have head and tail pointers. A queue class shouldn't have a next pointer. It's a bad example for using inheritence.

Right. A list item has a next pointer; a doubly-linked list has a next and a prev pointer. A list has a head and tail. A queue can be built on top of a list, but it should hide data members such as head and tail, and should hide member functions such as insert that allow one to do non-queish things to what otherwise is a queue.

The names "store" and "retrieve" are terrible. What's wrong with the canonical names for the two operations on a queue, "enqueue" and "dequeue"?

Just to reiterate: This appears to be a terrible book. I recommend you toss it, chiro. You cannot learn C++ in 21 days. Think of it this way: Can you learn physics in 21 days?

 

[John O' Meara]

I don't get the code either, but it works. He uses this to demonstrate an application of late binding in C++. The auther also has defined a: class stack : public list {
void store(int i);
int retrieve();
};
and: class sorted : public list {
void store(int i);
int retrieve();
};
And uses all those pointers.

 

[rcgldr]

I don't get the code either, but it works.

No one was stating the code wouldn't work, only that it's a bad example of an inherited class, since there are no common variables or functions used in the two classes. The next pointer is only used by the list class, and the head and tail pointers are only used by the queue class. The store() and retrieve() functions are only used by the queue class. I don't like this sequence of code either, since it's just confusing:

    list * item;
; ...
    item = new queue;

It should be:

    list * item;
; ...
    item = new list;

 

[John O' Meara]

He says in his book that " A pointer declared as a pointer to a base class can also be used to point to any class derived from that base". And this capacity when used with virtual functions, and is what makes a virtual function interesting - and capable of supporting run-time polymorphism. I hope I have parapharsed him correctly. So I didn't think it was bad code, to put item = new queue; what I think is very confusing is the head, tail and next pointers when compared with a queue formed from an array. The pointers are clearly inherited by the derived class queue. So each instance has its own set of head, tail and next pointers, and how does he arrange them to point correctly. I mean he has head pointing to tail and tail pointing to item, how can head then give you the first element in the list?

 

[rcgldr]

After the first call to the store() function, say address 0x8000 is allocated, then the pointers are pointing as indicated on the attachment, yes/no?

On the 2nd call to store(), we have: "if(tail) tail->next = item;". Which tail is it- 0x8000 or 0x8020's? And then we have: "tail->next = item;". Why not say next = item; Is it the 'next' of the instant 0x8000 or 0x8020? confused. Please help, thanks in advance for your time.

Getting back to the original questions:

You didn't include the main() function, so I used myqueue as the name of the queue.

declare a queue

queue myqueue; // assume queue is statically allocated at 0x4000 in ram

(queue * (0x4000))->head = NULL || myqueue.head = NULL
(queue * (0x4000))->tail = NULL || myqueue.tail = NULL

Make the first call to store:

myqueue.store(1); // assume the new list item is allocated at 0x8000 in ram

(queue * (0x4000))->head = (list *(0x8000))
(queue * (0x4000))->tail = (list *(0x8000))
(list * (0x8000))->next = NULL
(list * (0x8000))->num = 1

Make the second call to store:

myqueue.store(2); // assume the new list item is allocated at 0x8020 in ram

(queue * (0x4000))->head = (list * (0x8000)
(queue * (0x4000))->tail = (list * (0x8020)
(list * (0x8000))->next = (list * (0x8020))
(list * (0x8000))->num = 1
(list * (0x8020))->next = NULL
(list * (0x8020))->num = 2

Make the third call to store:

myqueue.store(3); // assume the new list item is allocated at 0x8040 in ram

(queue * (0x4000))->head = (list * (0x8000)
(queue * (0x4000))->tail = (list * (0x8040)
(list * (0x8000))->next = (list * (0x8020))
(list * (0x8000))->num = 1
(list * (0x8020))->next = (list * (0x8040))
(list * (0x8020))->num = 2
(list * (0x8040))->next = NULL
(list * (0x8040))->num = 3

 

[John O' Meara]

What he does in main is as follows:

int main()
{
  list * p;
  queue q_ob;
  p = &q_ob;  // point to queue

  p->store(1);
  p->store(2);
  p->store(3);

  cout << "Queue: ";
  cout << p->retrieve();
  cout << p->retrieve();
  cout << p->retrieve();

  // demonstrate a stack
  stack s_ob;
  p = &s_ob;   // point to stack
  etc;
}

I forgot about giving you the main() function,sorry about that. And thanks.

 

[John O' Meara]

p is a list pointer it should be the first line in the main() function, i.e., list * p;

 

[D H]

If the code in post #14 is a true copy of the code in the text, this is yet another reason not to buy this book. That is not valid code.

 

[John O' Meara]

Yes, the code in post #14 is the code in the book for the main() function. What book would you suggest as a good book for teaching yourself C++. Thanks.

 

[D H]

Programming: Principles and Practice Using C++ by Bjarne Stroustrup.

 

[rcgldr]

In addition to buying another book for learning C++, the book you have may still be useful. Even though that book you have has some bad programming examples, it should still be useful for learning the basics of C++. You may consider part of the learning experience to edit the example programs to clean up the code. For this example, I would recommend splitting up list and queue into two separate classes (not inherited), and changing the code so that only the list class is used for items, and only the queue class is used for the queue. You might want to add an item count to the queue class, and a function to return the number of items on a queue.

Another option would be to examine (briefly as opposed to trying to fully understrand) the source code from a standard template library, such as the one included with the free version of Microsoft Visual Studio C++ express. Even the code in these STL's isn't always that great, and it sometimes seems whoever wrote these tried to make the code complex and difficult to follow, but they usually include some of the more advanced syntax used in C++. You could compare the <list> template (double linked list) with the stuff you had in your book. In the case of VS2005, whoever did the <list> template abuses a node class with previous and next pointer by also using it for a queue class, using the previous pointer as a head pointer and the next pointer as a tail pointer (at least this is commented on in the class definition).

 

[John O' Meara]

I am not expert enough to see what is bad example code. I thought that a simple list could be treated as a queue or stack or sorted list; have the list as a base class and let it be inherited by queue was a good idea; I was just confused about the way he used the pointers in the code fragrament I showed. I am sure that the book I have is still useful as you said. But I try it your way. Thank you rcgldr for your suggestions.

 

[Hurkyl]

If the code in post #14 is a true copy of the code in the text, this is yet another reason not to buy this book. That is not valid code.

Maybe I'm slow today, but I don't see anything invalid there...

 

[D H]

Maybe I'm slow today, but I don't see anything invalid there...

p* is a pointer to a list, not a queue.

We weren't shown the definition of class list, but I assume that store and retrieve are queue-specific member functions. If class list does not mention that it has (or should have, via virtual) a store or retrieve member function then those calls to p->store and p->retrieve are illegal. The compiler is not allowed to guess that this p must be a pointer to a queue and that therefore the correct calls are to queue::store and queue::retrieve.

 

[John O' Meara]

If you looked at the attachment for this thread, list is defined as an abstract class, because it has two pure virtual member functions, store() and retrieve().

 

[rcgldr]

If you looked at the attachment for this thread, list is defined as an abstract class, because it has two pure virtual member functions, store() and retrieve().

The code works, but reiterating, it's a bad example for inheritance, because there are no common variables or functions between a proper queue stucture and a proper node structure. This wiki article includes a straight forward implementation in its C example, with separate and non inherted definitions for a queue and it's nodes. The C++ example uses a fixed size array and global indexes instead of pointers, so the C code is a better example. The C# example would be more readable if you replace first with tail, last with head, and previous with next or just ignore it and stick with the C example.

http://en.wikipedia.org/wiki/Queue_(data_structure)

The C example could be enhanced by adding a count variable to queue, which would be reset to zero by init_queue(), incremented by enqueue(), decremented by dequeue(), and adding a queue_count() function that would return the count.

struct queue
{
    struct queue_node *first;
    struct queue_node *last;
    int count;
};

 

[Hurkyl]

An list item class shouldn't have head and tail pointers. A queue class shouldn't have a next pointer. It's a bad example for using inheritence.

For the record, I think it's a fine example for inheritance -- the problem is that list simply has a poor design, e.g. doing too many things at once. It needs to be broken into list and list_item, as has been suggested.

 

[rcgldr]

An list item class shouldn't have head and tail pointers. A queue class shouldn't have a next pointer. It's a bad example for using inheritence.

For the record, I think it's a fine example for inheritance -- the problem is that list simply has a poor design, e.g. doing too many things at once. It needs to be broken into list and list_item, as has been suggested.

Maybe I'm missing something here, but what is the point of inheritance if none of the members of the base class are used by the derived class? Note the list item class is really a node class.

In this case you have two classes:

A queue class with head_pointer, tail_pointer, an enqueue() function, and a dequeue() function.

A node class with a next_pointer, and some user defined object (in this case an integer).

 

[Hurkyl]

Maybe I'm missing something here, but what is the point of inheritance if none of the members of the base class are used by the derived class? Note the list item class is really a node class.

No, it's really the amalgamation (amalgamation may be too generous a word) of a node class and a semi-abstract container^* class. You're focusing too much on the presence of "next" and "num" which are for node functionality, and overlooking the presence of "store", "retrieve", "head", and "tail" which are for container functionality.

*: Meant in the general sense, rather than the STL-specific sense

 

[rcgldr]

I forgot to answer this part of the original post:

Doesn't each instance have its own head, tail and next pointers as well as as the data member, num?

Yes, which is which is why I don't like that example. Only the queue class uses the head and tail pointers, and only the node (list item) class uses a next pointer and data member. So for the queue class, the next pointer and data member are wasted space, and for the node (list item) class, the head and tail pointers are wasted space.

The rest of this post is getting a bit beyond the original topic, so perhaps this part of the thread could be split off into another thread, unless the original poster (John) would be interested in this part of the thread as well.

Note the list item class is really a node class.

No, it's really the amalgamation of a node class and a semi-abstract container class.

That's not how I see it. A container class may utilize a node class ("may" - a node class wouldn't be needed in the case of a queue that uses a circular buffer for storing objects), just like a container class may utilize basic types like pointers or integers, but I don't see an inheritance relationship between these classes and/or basic types. Back to my previous post, what is the point of inheritance if none of the members of the base class are used by the derived class?

For example, the doubly linked <list> template in the STL in VS defines four separate and non-inerhited template classes, list_node (prev and next pointers), list_ptr (ptr to object), list_val (instance of object), and the list template class itself which makes use of the other three classes. Trying to redefine these as base and derived classes doesn't make sense to me.

Assuming you did want to use inheritance between a node class and a container class, which would be the base class and which would be the inherited class? An example code fragment showing inheritance with a properly defined container class and node class instead of the example from the book would help me understand your point.

 

[Hurkyl]

Assuming you did want to use inheritance between a node class and a container class,

That's not what the example is trying to do. It's trying to use inheritance between an abstract container class and a concrete instantiation.

class push_pop_container
{
public:
    virtual void push(int x) = 0;
    virtual int pop() throws empty_exception = 0;
};

class queue : public push_pop_container
{
public:
    // implement the functions
};

class stack : public push_pop_container
{
public:
    // implement the functions
};

int main()
{
    push_pop_container *p = new queue();
    p->push(1);
    p->push(2);
    p->push(3);
    cout << p->pop() << endl;
    cout << p->pop() << endl;
    cout << p->pop() << endl;
    delete p;
    p = new stack();
    p->push(1);
    p->push(2);
    p->push(3);
    cout << p->pop() << endl;
    cout << p->pop() << endl;
    cout << p->pop() << endl;
    delete p;
}

 

[rcgldr]

That's not what the example is trying to do. It's trying to use inheritance between an abstract container class and a concrete instantiation. ... (followed by examples of this) ...

OK, I misunderstood your previous posts. Using an abstract container class as a base class, and then deriving specific types of container classes from the abstract class make sense. However in the case of list (doubly linked list), push and pop have to be clarified by suffixing them with _back or _front.

My issue was about the book using a common class for both node and container, (logically these two classes don't have any common members), and I mistakenly thought that part of the book not included in this thread was implying an inheritance relationship between node and container.

On a side note, being old school, I don't like using push and pop as function names for lists or queues, but that is what is used in the STL, and I just go with the flow on this stuff. If it were me creating the names, I would use insert or append instead of push, and extract instead of pop.