Custom Queue Class C++

Question

So I'm trying to create a Singly-linked-list Queue. I'm trying to write a function to add elements, and everything adds fine, but the problem is that its FILO instead of FIFO. I'm not sure how to handle my front and rear pointers.

#include <iostream>
#include <string>
using namespace std;

class Queue{
    public:
        Queue();
       //~Queue();
       void add(const string & item);
       //string remove();
      // unsigned items() const;
       void show() const;
    private:
        struct Node{
            string data;
            Node *next;
        };
        Node *rear;
        Node *front;
        unsigned elements;
};

Queue::Queue():elements(0),rear(NULL),front(NULL){}

//Queue::~Queue(){

//}

void Queue::add(const string & item){
    Node *t=new Node;
    t->data=item;
    t->next=rear;
    if(front==NULL)
        front=t;
    rear=t;
    elements++;

}

void  Queue::show() const{

    Node *p=rear;
    for(; p->next!=rear; p=p->next){
        cout<<" "<<p->data;
    }
    cout<<"\n";
}
int main(){
    Queue obj;
    obj.add("I");
    obj.add("Am");
    obj.add("Super");
    obj.add("Cool");
    obj.show();
}

Answer 1

I figured out how to reverse the entire thing so it works properly now. Is it efficient? It took 1.06ms to run main.

    #include <iostream>
    #include <string>
    using namespace std;
    bool die(const string &msg);

    class Queue{
        public:
            Queue();
           ~Queue();
           void add(const string & item);
           string remove();
           unsigned items() const;
           void show() const;
        private:
            struct Node{
                string data;
                Node *next;
            };
            Node *rear;
            Node *front;
            unsigned elements;
    };

    Queue::Queue():elements(0),rear(NULL),front(NULL){}

    Queue::~Queue(){
     unsigned el=items();
     for(unsigned i=0; i<el; i++)
      remove();
    }
    unsigned Queue::items()const{
        return elements;
    }

    string Queue::remove(){
        if(front==NULL) die("underflow");
        Node *t=front;
        string data=t->data;
        front=t->next;
        delete t;
        elements--;
        return data;
    }
    void Queue::add(const string &item){
     Node *t=new Node;
     t->data=item;
     t->next=NULL;
     if(front==NULL)
        front=t;
     else{
        Node *t2=rear;
        t2->next=t;
     }
     rear=t;
     elements++;
    }

    void  Queue::show() const{
        Node *t=front;
        for(unsigned i=0; i<items(); i++, t=t->next)
            cout<<t->data<<'\n';
    }

    bool die(const string &msg){
        cout<<"Error: "<<msg;
        exit(EXIT_FAILURE);
    }

    int main(){
        Queue obj;
        obj.show();
        obj.add("poo");
        obj.add("cra");
        obj.add("bil");
        obj.add("shi");
        obj.show();
        cout<<obj.remove()<<"\n";
        cout<<obj.remove()<<"\n";
        cout<<obj.remove()<<"\n";
        cout<<obj.remove()<<"\n";
    }

Answer 2

to achieve, FILO(like STACK?), When push(add), append your new element at the end( you will deal with rear pointer) When pop, get rid of the element that rear pointer points to.

In you code, your rear pointer points to one element after end, which is null. So push takes O(n), and also pop cost O(n). Its not efficient. So considering double linked list may be better choice for easy implementation.

Answer 3

currently it is neither FIFO nor FILO bu JINO (just in, never out).

what you do is to insert on the rear end. and your show does iterate from rear to front, because thats the only linked direction.

for an effective FIFO you would need a remove from the front end of your queue. you will notice, that you can find the front element, but you have no easy way to find the second element that is needed to set the front pointer. this is the drawback of your single linked design, you have to iterate from the rear to the front to find the element pointing to front.

• with a single linked list you can do a FILO (actually more likely named LIFO or stack)
• for a FIFO a double linked list would be the better design.

---

if you want to stick to a single linked list you could do some recursion. you eliminate the front pointer cause it is useless.

void  Queue::show_one(Node *p) const{
    if (p->next!=rear) {    // i kept the test for p->next!=rear
                            // either fix add or test for p->next!=NULL
        show_one(p->next);
    }
    cout<<" "<<p->data;
}

void  Queue::show() const{
    show_one(rear);
    cout<<"\n";
}

likewise you could write a remove()