Need help with FIFO Queue using Singly Linked Lists

Let me preface this by saying that this IS a homework assignment but I'm not looking for someone to code this for me. I am just having a really difficult time sorting through all of this and I've been everywhere on the internet and I have 4 C++ books sitting in front of me and the lecture notes have not been particularly helpful. This program is supposed to use class Queue to manipulate data and class QueueItem to store the data. It is incomplete because the assignment is more complicated than this particluar problem, but I'm not concerned with all of that until I can get the basic structure down. The code below compiles, although it prints what appear so to be an octal memory address, rather than the char string "test". I'm trying to step through the code bit by bit so many fuctions are not included. My question is this: How do I pass "test" to function Queue::addItem(char *pData, ++mNodeCounter). I'm struggling because pData and the char mData[30] array belong to different classes and char mData[30] is private. Again, I'm not looking for someone to code the entire program for me, I just need a clarification on how to pass "test" to a function and store it and/or a little explanation of what is going on in the Queue implementation as far as storing data. I'm trying to learn how to do this correctly for future assignments, but again I've been through countless resources and I have found little in the way of instruction involving using this many pointers and classes to write a FIFO queue. Thank you in advance for your help.

Code:

---

#include <iostream>
#include <cstring>
using namespace std;
     
     
    class QueueItem {
    public:
        QueueItem(char *pData, int id);  // ctor
        void setNext(QueueItem *pItem);
        QueueItem* getNext();
        int getId();
        const char* getData();
    private:
        char mData[30];  // or, use a char* if you want to dynamically alloc memory
        int mNodeID;
        QueueItem * mpNext;
    }; 

    QueueItem::QueueItem(char *pData, int id)
    {
      id = mNodeID;
       
        }
   
    class Queue {
    public:
        Queue();                        // ctor inits a new Queue
        ~Queue();                      // dtor erases any remaining QueueItems
        void addItem(char *pData);
        void removeItem();
        void print();
        void erase();
       
    private:
        QueueItem *mpHead; // always points to first QueueItem in the list
        QueueItem *mpTail; // always points to the last QueueItem in the list
        int mNodeCounter;  // always increasing for a unique id to assign to each new QueueItem
    };
   


    Queue::Queue()  {
   
        mpHead = NULL;
        mpTail = NULL;
   
}
    void Queue::addItem(char *pData)
  {
    // dynamically create and init a new QueueItem
    QueueItem *pQI = new QueueItem(pData, ++mNodeCounter);

    if (0 == mpHead)  // chk for empty queue
      mpHead = mpTail = pQI;
    else
    {
      // link new item onto tail of list using mpTail pointer
      mpTail = pQI;
    }
  }
 
    void Queue::removeItem()
    {
        delete mpHead;
}
     
 
    void Queue::print()
    {
        cout << mpHead << endl;
        cout << mNodeCounter << endl;
}
 
    Queue::~Queue()
    {}
   
   
    int main()    {
        Queue myQueue;
        myQueue.addItem("test");
        myQueue.print();
       
        getchar();
       
}

---

Well in your print function you're trying to do this:

Code:

---

cout << mphead << endl;

---

unfortunately, mphead is a pointer, so you'll have to say this instead:

Code:

---

cout << mphead->getdata() << endl;

---

I won't comment on the the rest of the code since the like you said, you didn't post all of the functions.

Edit: Probably better than what I just said is to overload the operator<< so you can specify there exactly what you want to print out, then you can simply refer to the object, and you wouldn't even need to use pointer syntax. Here's an example:

Code:

---

class myObj{

friend std::ostream& operator<<( std::ostream& output, const myObject& m_obj ){

       

        output << m_obj.data1 << m_obj.data_2;

        return output;

        }

public:

    //...

private:

    //...
};

---

Also, If QueueItem is an object declared outside of Queue (it's not a private class of Queue) then it might be less confusing to either make it a private class of Queue or declare Queue a friend class of QueueItem, then you eliminate the need for the setNext and getNext functions.

This allows you to directly refer to the next pointer within Queue like:

Code:

---


QueueItem *curr = mpHead;

curr->next = something;

---

HINT: It doesn't look like your doing anything with the next pointer in your add or remove functions, you'll need to do something with it...

Actually, that does help a lot. I was reading some of the other posts and ran across a sarcastic post to a pretty annoying person, but it actually helped me. I'm printing the actual memory address of the mpHead pointer. As I said, I really am just trying to get some explanations of the processes involved here. I'm taking this class at the college level online at Umass, but I could really use some actual explanations like you provided. Along those lines, the getdata() function was provided by the instructor, but it isn't being passed any values. That's why I have to use mpHead->getData() in the print function, right? What I really don't get is how to pass the data to the getData function, since it is a member of QueueItem and MyQueue.additem("test") refers to class Queue. Again, the instructor provided the MyQueue.addItem() function, so it isn't like I could change that to getData(). Am I missing something or am I on the right track?

Well getData()'s implementation should (or already does) look something like this:

Code:

---

const char* QueueItem::getData(){

    return data;
}

---

If that's the case then because mpHead is a pointer you have to use the pointer syntax like I said:

Code:

---

mpHead->getData();

---

Because code is being provided by the instructor, and you're not allowed to change it, it looks like you will definitely need to use the above syntax.


And yes: you were printing the address of the mpHead pointer. My example (mphead->getdata() ) should take care of that.

Yeah, that hint is kinda where I've been having trouble. I think I'm starting to see what you're getting at though. I knew I needed the QueueItem * mpNext; but I wasn't sure what to do with it. I think I was confusing it with getNext. See, the program is supposed to be a FIFO and then it should add 4 items, remove 2 items, print the list with the node id, remove 4 items, print out list and node id again, erase the queue, add 2 items, print out the list, erase the list, and print out the list (which won't do anything because it will be empty). That much I can do, because those are just repetitious function calls. My biggest hurdle has been trying to figure out exactly how to get the items in to the queue correctly in the first place. That's where I was missing the mpNext pointer. I'm going to write that in as soon as I get back from my second job (Working fulltime, plus Saturday evening and taking 12 credits is really wearing me down!) Thanks for your help! I'll be checking the board again when I get home.

Here's an example of a singly-linked-list i wrote up quickly the other day:

http://cboard.cprogramming.com/showt...=100265&page=2

Note how the "next" pointer is used to manipulate the list.

To understand more of how a queue works and what functionality it has check this out on the standard queue:

STL Queue

Now that I have some more time, let's analyze what you have here a little more in depth:

1. I'm guessing that your assignment is something like you are given this QueueItem class, and you need to make a Queue container of these items, yes?

2. You said:

Quote:

---

Along those lines, the getdata() function was provided by the instructor, but it isn't being passed any values. That's why I have to use mpHead->getData() in the print function, right?

---

No. The reason you need to say mpHead->getData() is because getData() is how you "get the data". const char* data is a private member of the QueueItem class, therefore the only way to "get the data" is to use the public function getdata() that was provided for you. "mpHead->getdata()" is simply the syntax used for a pointer to access the getdata() function.

That's how classes work. They have private data associated with them, and a public interface which allows a user to use the class. Pointers to a class can also do the same things as objects.

Example:

Code:

---


MyObj object;
object.setData("I'm an object");






MyObj *object_pointer;          // Declare pointer to MyObj.

object_pointer = new MyObj();    // Create an instance MyObj

object_pointer->setData("I'm a pointer to an object");    // Use a member function with pointer syntax

---

Note that the first two lines show the creation of an actual instance of the class MyObj, and the last three lines show how to use a pointer to MyObj objects.

A pointer does one thing, it points. What does it point to? Whatever type you declare it as. An int *ptr, points to integers, QueueItem *qptr, points to objects of type "QueueItem". The great thing about pointers, is we can tell them to point to something else (as long as it's the same type). This is important for "linkable" data structures such as linked-lists, stacks, queues, dequeues, etc.

These types of data structures require a pointer to which refers to the "next" item in the list, stack, queue, etc. The next pointer itself is a private member of the class. This means that each item in the queue, has a next pointer. And what does it point to? The next item.

To help you visualize this:

Code:

---


// Items in the queue:

[5]->[15]->[97]->[12]->[39]->NULL

---

So, just by looking at that we know that whatever object this is in the queue has private members that are an integer and a next pointer. The class for the above might look like:

Code:

---

class integerClass{

    public:

        // ...

    private:

        int data;
        integerClass *next;
};

---

Now, let's review quickly how classes work. How can we "get the data" for this class? We simply provide the function in the public interface like this:

Code:

---

class integerClass{

    public:

        int get_integer_data(){ return data; };

    private:

        int data;
        integerClass *next;
};

---

We can just as easily provide a "get" function for any private data. The only thing you need to do is write the function like you would any function, with the correct return type. So if we wanted to return the next pointer, we could say:

Code:

---

integerClass* get_next(){ return next; };

---

note, we don't need to pass anything to these functions. Because both the private and public sections of any class are in fact a part of that class, they automatically have access to their own data.

Now, mpHead and mpTail are both pointers to QueueItems the same way mpNext is a pointer to QueueItems. They're exactly the same in every respect, except that every QueueItem has a next pointer, and only the Queue itself has mpHead and mpTail. Consider this:

Code:

---


mpHead->getData();

mpHead->next->getData();

mpHead->next->next->next->getData();

mpTail->getData();

---

are all legal expressions, though I wouldn't recommend chaining like that.

Let's apply those above expression to the queue illustration i made earlier:

Code:

---

// Everything in the queue:
[5]->[15]->[97]->[12]->[39]->NULL

// Okay, the HEAD is 5 and the TAIL is 39

// so the above expressions return like this:

mpHead->getData(); // returns 5

mpHead->next->getData(); // returns 15

mpHead->next->next->next->getData(); // returns 12

mpTail->getData(); // returns 39

---

So the whole point of the next pointer is to refer to the next object. This is necessary to even construct a cohesive structure like queue.

As I said, check out my linked-list example that I provided the link for. Although it's not a queue, all the information you would need to construct a queue is there.