Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Queue made with pointers in C++, questions

  1. Jul 11, 2011 #1
    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.
     

    Attached Files:

  2. jcsd
  3. Jul 11, 2011 #2
    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.
     
  4. Jul 11, 2011 #3

    chiro

    User Avatar
    Science Advisor

    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.
     
  5. Jul 12, 2011 #4

    rcgldr

    User Avatar
    Homework Helper

    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).
     
    Last edited: Jul 12, 2011
  6. Jul 12, 2011 #5

    chiro

    User Avatar
    Science Advisor

    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.
     
  7. Jul 12, 2011 #6

    rcgldr

    User Avatar
    Homework Helper

    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
     
    Last edited: Jul 12, 2011
  8. Jul 12, 2011 #7

    chiro

    User Avatar
    Science Advisor

    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.
     
  9. Jul 12, 2011 #8

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Jul 12, 2011
  10. Jul 12, 2011 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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).

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

    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?
     
  11. Jul 12, 2011 #10
    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.
     
  12. Jul 12, 2011 #11

    rcgldr

    User Avatar
    Homework Helper

    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:

    Code (Text):

        list * item;
    ; ...
        item = new queue;
     
    It should be:

    Code (Text):

        list * item;
    ; ...
        item = new list;
     
     
    Last edited: Jul 12, 2011
  13. Jul 12, 2011 #12
    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?
     
  14. Jul 12, 2011 #13

    rcgldr

    User Avatar
    Homework Helper

    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
     
    Last edited: Jul 12, 2011
  15. Jul 12, 2011 #14
    What he does in main is as follows:
    Code (Text):

    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.
     
    Last edited by a moderator: Jul 12, 2011
  16. Jul 12, 2011 #15
    p is a list pointer it should be the first line in the main() function, i.e., list * p;
     
  17. Jul 12, 2011 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  18. Jul 13, 2011 #17
    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.
     
  19. Jul 13, 2011 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Programming: Principles and Practice Using C++ by Bjarne Stroustrup.
     
  20. Jul 14, 2011 #19

    rcgldr

    User Avatar
    Homework Helper

    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).
     
    Last edited: Jul 14, 2011
  21. Jul 14, 2011 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Queue made with pointers in C++, questions
  1. Pointer question (Replies: 2)

Loading...