Thread: Help with FIFO QUEUE

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    72

    Help with FIFO QUEUE

    [QUOTE]Description

    Create a Queue class that implements a queue abstraction. A queue is a FIFO list (First In First Out queue). A simple example is waiting in line, where the first person in the line is the first served. New arrivals are added to the back of the line, the next person served is (removed) from the front of the line.

    The Queue class needs to implement the following operations:

    * adding to the queue at one end (the tail)
    * removing from the queue at the other end (the head)
    * printing all items the queue (from head to tail)
    * erasing all items in the queue (leaving the queue empty).
    * destructor to empty the queue before it's destroyed (to release all memory)

    Additions and removals always occur at the opposite ends of the queue.

    You should create the following methods in your Queue class to implement the above operationsm

    Your Queue implementation uses a companion QueueItem class to represent each element in the list. A QueueItem contains character string as the data value, a unique (among all QueueItems in a Queue) integer node identifier, and a pointer to the next QueueItem in the list. [/QUOTE}

    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;
    };

    The QueueItem member functions are very basic, just setting or getting data members of the class. All the linked list manipulation is done by the Queue class member functions.

    The Queue class member functions manipulate the linked list of QueueItem's, creating and destroying QueueItem objects as needed using the C++ new and delete operators. The Queue class member data includes a pointer to the head and and pointer to the tail of the linked list of QueueItems, and an integer node counter used to provide a unique node ID for every newly created QueueItem (incremented each time a new QueueItem is added, and passed as a parameter to the QueueItem constructor. It is never decremented).

    The following is a partial example of the Queue class; you will need to fill in the remaining methods.

    class Queue {
    public:
    Queue(); // ctor inits a new Queue
    ~Queue(); // dtor erases any remaining QueueItems
    void addItem(char *pData);
    void removeItem();
    ...
    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
    };

    The Queue class member functions should not have access to the private members of QueueItem objects. They call the public member functions of QueueItem.

    As an example, the outline of the Queue::addItem() member function is shown below. It must add a new QueueItem at the tail of the Queue, and update the mpTail pointer to point to it. The first item in the Queue is both the head and the tail of the list.:


    void Queue::addItem(char *pData)
    {
    // dynamically create and init a new QueueItem object
    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
    ...
    }
    }

    The removeItem() method removes the head QueueItem from the queue, and should release the memory using the C++ delete operator. It updates mpHead to point at the following item (if any) as the new head. If the list becomes empty, both mpHead and mpTail must be set to null (0). It does not change the value of mNodeCounter (which is always incremented when a new item is added). If called on an empty Queue, it does nothing.

    The erase() method removes all the items in the queue and should release the memory. To implement, you could loop calling removeItem() until the queue is empty.

    The Queue destructor should ensure that all items are removed from the queue. The easiest way is to call the erase() method from the destructor.
    The user code (main) never see's QueueItem objects, since they are used only for implementation inside of class Queue. main() has only the Queue object to work with. For example, the following code would create a queue with three elements, and then print it out:



    -------------------------------------------------------------------------------
    my Program:
    Code:
    //QueueItem.h
    //Declaration of class QueueItem
    
    
    #ifndef QUEUEITEM_H
    #define QUEUEITEM_H
    
    
    
    class QueueItem
    {
    public:
    QueueItem(char *pData, int id); // constructor
    void setNext(QueueItem *pItem); //set pointer to next Item
    QueueItem* getNext(); //get pointer to next Item
    int getId(); //get Id
    const char* getData(); //get data member
    
    private:
    char mData[30]; // or, use a char* if you want to dynamically alloc memory
    int mNodeID;
    QueueItem *mpNext; // pointer to another object of same type
    };//end class QueueItem
    
    #endif
    Code:
    //Queue.h
    //Declaration of class Queue
    
    //prevent multiple inclusions of header file
    #ifndef QUEUE_H
    #define QUEUE_H
    
    #include "QueueItem.h" // include definitions of class QueueItem from QueueItem.h
    
    class Queue
    {
    public:
    Queue(); // constructor
    ~Queue(); // destructor
    void addItem(char *pData);
    void removeItem();
    void eraseList();
    void printList();
    
    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
    };//end class Queue
    #endif
    Code:
    //member function definitions for class QueueItem
    
    #include <iostream> // allows program to output data
    using namespace std;
    
    #include <string>
    
    #include "QueueItem.h" // include definition of class QueueItem from QueueItem.h
    
    //QueueItem constructor
    QueueItem::QueueItem(char *pData, int id)
    {
    pData = mData;
    id = mNodeID;
    mpNext = NULL;
    
    }// end constructor
    
    void QueueItem::setNext(QueueItem *pItem)
    {
    mpNext = pItem;
    }// end setNext function
    
    
    QueueItem* QueueItem::getNext()
    {
    return mpNext;
    }//end getNext function
    
    int QueueItem::getId()
    {
    return mNodeID;
    }//end getId function
    
    const char* QueueItem::getData()
    {
    return mData;
    }//end getData function
    Code:
    //member function definitions for class Date
    #include <iostream> //allows program to output data on screen
    using std::cout;
    using std::endl;
    using namespace std;
    
    #include <iomanip>
    using std::setfill;
    using std::setw;
    
    #include <string>
    using std::string;
    using std::strcpy;
    
    #include "Queue.h" //include definition of class Queue from Queue.h
    
    
    
    //constructor
    Queue::Queue()
    {
    mpHead = NULL;
    mpTail = NULL;
    mNodeCounter = 0;
    }
    
    void Queue::addItem(char *pData)
    {
    //create and initialize new QueueItem dynamically
    QueueItem *pQI = new QueueItem(pData, ++mNodeCounter);
    
    if ( mpHead == 0 ){ //check for empty queue
    mpHead = mpTail = pQI;}
    
    else{
    // link new item onto tail of list using mpTail pointer
    
    mpTail->setNext(pQI);
    mpTail = pQI;
    
    }
    
    }//end addItem function
    
    //function removeItem
    void Queue::removeItem()
    {
    if(mpHead == NULL){
    mpHead = mpTail;}
    else{
    delete mpHead;
    mpHead = mpHead->getNext();}
    
    
    
    }//end removeItem function
    
    //Erase List
    void Queue::eraseList()
    {
    while (mpHead != 0)
    removeItem();
    mpHead = mpTail = 0;
    }//end eraseList function
    
    //prints contents of queue
    void Queue::printList()
    {
    while (mpHead != 0){
    cout << mpHead->getData() << endl;
    mpHead = mpHead->getNext();
    cout << mNodeCounter << endl;}
    }//end printList function
    
    //destructor
    Queue::~Queue()
    {
    eraseList();
    }
    ---------------------------------------
    What is wrong with my program??? it only prints 00000s. can somebody help me?
    |
    Last edited by jackfraust; 04-01-2009 at 07:23 PM.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    what's up with the indentation? you really hope someone will read your mess? work a little bit on the readability of the code then
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    It might also be a good idea to post the program (main function) that you say only prints 0's.

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Code:
    int main()
    {
    	Queue numbers;
    
    	numbers.addItem("one");
    	numbers.addItem("two");
    	numbers.addItem("three");
    	numbers.addItem("four");
    	numbers.printList();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.addItem("five");
    	numbers.addItem("six");
    	numbers.addItem("seven");
    	numbers.addItem("eight");
    	numbers.printList();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.printList();
    	numbers.eraseList();
    	numbers.addItem("nine");
    	numbers.addItem("ten");
    	numbers.addItem("eleven");
    	numbers.printList();
    	numbers.eraseList();
    	numbers.printList();
    
    	return 0;
    }
    That's the main code, its made to test out the program

  5. #5
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    in your QueuItem constructor
    pData = mData; - this should be opposite

    Code:
    delete mpHead;
    mpHead = mpHead->getNext();
    you cannot access deleted pointer

    your const correctness went out of window

    your printList changes the head pointer making it impossible to remove head or print list once again
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Quote Originally Posted by vart View Post
    in your QueuItem constructor
    pData = mData; - this should be opposite

    Code:
    delete mpHead;
    mpHead = mpHead->getNext();
    you cannot access deleted pointer

    your const correctness went out of window

    your printList changes the head pointer making it impossible to remove head or print list once again
    I changed the Queueitem constructor to:
    Code:
    QueueItem::QueueItem (char *pData, int id)
    {
    strncpy(mData, pData);
    mNodeID = id;
    mpNext = NULL;
    }
    for the removeItem function, after deleting the head shouldn't i push the next item on top??
    How does the printlist change the head pointer?

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    strncpy(mData, pData);
    this will not compile...

    and definitely will crash as you do not have a storage where to copy string

    Switch to std::string if you want to store the passed value an not just a pointer
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Quote Originally Posted by vart View Post
    strncpy(mData, pData);
    this will not compile...

    and definitely will crash as you do not have a storage where to copy string

    Switch to std::string if you want to store the passed value an not just a pointer
    mData is not a const char pointer, thats why i used
    strncpy(mData, pData, 30);
    ----------------------------------------
    what do you suggest for printlist() and removeItem()?

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by jackfraust View Post
    mData is not a const char pointer, thats why i used
    strncpy(mData, pData, 30);
    why are you using char array and not std::string?

    what do you suggest for printlist() and removeItem()?
    declare printlist as const (as it should - and fix the compiler error

    in the removeItem - take the next pointer before deleting the current node
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Quote Originally Posted by vart View Post
    why are you using char array and not std::string?


    declare printlist as const (as it should - and fix the compiler error

    in the removeItem - take the next pointer before deleting the current node
    im supposed to use char and not std::string. as for taking the next pointer, should i use mpNext or getNext() function?

    should i just leave removeitem as:

    Code:
    void Queue::removeItem()
    {	
    	delete mpHead;
    }

  11. #11
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    Quote Originally Posted by jackfraust View Post
    should i just leave removeitem as:

    Code:
    void Queue::removeItem()
    {	
    	delete mpHead;
    }
    No - if you do that on a non-empty queue you will "lose" (and leak) the rest of the queue; if you do it on an empty queue you will be trying to delete "NULL", which I suppose won't do any harm but makes no sense.

    removeItem() should check to see if the queue is empty. If so, just return. If not empty, create a local QueueItem* temp, assign mpHead to temp just to hold it temporarily, reassign mphead to point to mpHead->getNext(), then delete temp.

    You also need to make a similar correction to your printList(). You shouldn't be reassigning mpHead while you print -- after printing you will no longer have a pointer to the head of the queue. Instead use a temporary pointer to iterate through the queue (and print both the data and the id number before advancing that pointer).

  12. #12
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Quote Originally Posted by R.Stiltskin View Post
    No - if you do that on a non-empty queue you will "lose" (and leak) the rest of the queue; if you do it on an empty queue you will be trying to delete "NULL", which I suppose won't do any harm but makes no sense.

    removeItem() should check to see if the queue is empty. If so, just return. If not empty, create a local QueueItem* temp, assign mpHead to temp just to hold it temporarily, reassign mphead to point to mpHead->getNext(), then delete temp.

    You also need to make a similar correction to your printList(). You shouldn't be reassigning mpHead while you print -- after printing you will no longer have a pointer to the head of the queue. Instead use a temporary pointer to iterate through the queue (and print both the data and the id number before advancing that pointer).
    I see where you are coming from but the compiler doesn't want to let me create temporary pointers. For some reason it says unitialized local variable.

  13. #13
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    Are you trying to define a pointer or a reference?

    It won't let you do:
    Code:
    QueueItem *temp = mpHead;
    ???

    Show me what you are are trying to do.

  14. #14
    Registered User
    Join Date
    Feb 2009
    Posts
    72
    Quote Originally Posted by R.Stiltskin View Post
    Are you trying to define a pointer or a reference?

    It won't let you do:
    Code:
    QueueItem *temp = mpHead;
    ???

    Show me what you are are trying to do.
    I had to restart the compiler for it to work, don't know what's wrong with it. But i got a question though, shouldn't the nodeID also get deleted everytime the removeItem() function is called, or eraseList()?

    my int main() looks like this:
    Code:
    int main()
    {
    	numbers.addItem("one");
    	numbers.addItem("two");
    	numbers.addItem("three");
    	numbers.addItem("four");
    	numbers.printList();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.addItem("five");
    	numbers.addItem("six");
    	numbers.addItem("seven");
    	numbers.addItem("eight");
    	numbers.printList();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.removeItem();
    	numbers.printList();
    	numbers.eraseList();
    	numbers.addItem("nine");
    	numbers.addItem("ten");
    	numbers.addItem("eleven");
    	numbers.printList();
    	numbers.eraseList();
    	numbers.printList();
    
    return 0;
    }
    OUTPUT looks like this:
    one 4
    three 8
    seven 8
    nine 11

  15. #15
    Registered User
    Join Date
    Feb 2003
    Posts
    596
    Quote Originally Posted by jackfraust View Post
    my int main() looks like this:
    No, show me what you did to removeItem().

    Edit: and you also have to correct printList() as I mentioned above. Otherwise everything will be messed up after the first call to that method.


    Quote Originally Posted by jackfraust View Post
    But i got a question though, shouldn't the nodeID also get deleted everytime the removeItem() function is called, or eraseList()?
    No. You're not using dynamic allocation inside the nodes, so all you have to do is delete the node and that will automatically deal with the node's data members.
    Last edited by R.Stiltskin; 04-02-2009 at 09:34 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  2. Need help with FIFO Queue using Singly Linked Lists
    By astou in forum C++ Programming
    Replies: 6
    Last Post: 03-15-2008, 02:36 PM
  3. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM
  5. queue help
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-29-2001, 09:38 AM