Переполнение стека в пользовательском классе очереди
Поэтому я пытаюсь создать Очередь с одиночными связями. Я пытаюсь написать функцию для добавления элементов, и все добавляет нормально, но проблема в том, что это FILO вместо FIFO. Я не уверен, как обращаться со своими передними и задними указателями.
#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();
}
Решение
в настоящее время это не FIFO и не FILO, но 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). Это не эффективно. Поэтому рассмотрение двойного связанного списка может быть лучшим выбором для легкой реализации.
Я понял, как полностью изменить ситуацию, чтобы она теперь работала правильно. Это эффективно? Потребовалось 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";
}