1

だから私は単一リンクリストキューを作成しようとしています。要素を追加する関数を作成しようとしていますが、すべて問題なく追加されますが、FIFO ではなく FILO が問題です。フロントポインターとリアポインターの処理方法がわかりません。

#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();
}
4

3 に答える 3

1

現在は FIFO でも FILO bu JINO でもありません (Just in, never out)。

あなたがすることは、後端に挿入することです。ショーは後ろから前に繰り返されます。これが唯一のリンクされた方向だからです。

効果的な FIFO を使用するには、キューのフロント エンドから削除する必要があります。フロント要素を見つけることはできますが、フロント ポインターを設定するために必要な 2 番目の要素を見つける簡単な方法がないことに気付くでしょう。これは、単一のリンクされたデザインの欠点です。前面を指す要素を見つけるには、背面から前面に反復する必要があります。

  • 単一のリンクされたリストを使用すると、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()

于 2012-12-09T01:13:44.910 に答える
0

達成するには、FILO（スタックのように？）、プッシュ（追加）するとき、最後に新しい要素を追加します（リアポインターを処理します）ポップすると、リアポインターが指す要素を取り除きます。

あなたのコードでは、リア ポインターは end の後の 1 つの要素を指していますが、これは null です。したがって、プッシュには O(n) かかり、ポップには O(n) のコストがかかります。効率的ではありません。したがって、簡単に実装するには、二重リンクリストを検討する方が良い選択かもしれません。

于 2012-12-09T01:35:41.383 に答える