Пользовательский класс очереди C++

в настоящее время это ни FIFO, ни FILO bu JINO (только вход, никогда выход).

то, что вы делаете, это вставить на задний конец. и ваше шоу повторяется сзади вперед, потому что это единственное связанное направление.

для эффективного FIFO вам потребуется удаление из начала вашей очереди. вы заметите, что вы можете найти передний элемент, но у вас нет простого способа найти второй элемент, необходимый для установки переднего указателя. это недостаток вашего односвязного дизайна, вам нужно выполнять итерацию от задней части к передней, чтобы найти элемент, указывающий на передний план.

• с одним связанным списком вы можете сделать FILO (на самом деле, скорее всего, с именем LIFO или стеком)
• для FIFO двусвязный список был бы лучшим дизайном.

если вы хотите придерживаться одного связанного списка, вы можете сделать некоторую рекурсию. вы устраняете передний указатель, потому что он бесполезен.

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

аналогично вы могли бы написать remove()

для достижения FILO (например, STACK?), При нажатии (добавлении) добавьте новый элемент в конец (вы будете иметь дело с задним указателем). Когда всплывает, избавьтесь от элемента, на который указывает задний указатель.

В вашем коде ваш задний указатель указывает на один элемент после конца, который равен нулю. Таким образом, push требует O(n), а pop стоит O(n). Это не эффективно. Поэтому рассмотрение двойного связанного списка может быть лучшим выбором для простой реализации.

Я понял, как перевернуть все это, чтобы теперь все работало правильно. Это эффективно? Для запуска main потребовалось 1,06 мс.

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