c++ - C++ でのトラバースキュー

Question

印刷する必要がある C++ キューがあります。最初のノードを印刷してから削除し、最初のノードを再度印刷してから 2 番目のノードにするのは簡単です。しかし、一度印刷するだけでリスト全体が消去されます...回避策として、印刷メソッドに渡した一時キューオブジェクトを作成し、最初のオブジェクトと同じことを行いました。キューを動的にするためのポインターであるため、最初からコピーされたオブジェクトからそれらを削除しても、同じデータが削除されます。私はまだポインターが苦手ですが、これを行う簡単な方法があるに違いないと確信しています。何か提案はありますか?

コードは次のとおりです。

queue2 = queue1; // Temporary queue is assigned values of main queue
queue2.printQueue(); // Temporary queue is passed to print method

これが私の印刷方法です：

int numberPrinted = 0;
while (!isEmptyQueue())
{
 cout << numberPrinted + 1 << ": " << front() << "\n";
 deleteQueue();    
 numberPrinted++;
 }

キュークラスファイル:

#ifndef H_linkedQueue
#define H_linkedQueue

#include <iostream>
#include <cassert>
#include "queueADT.h"

using namespace std;

//Definition of the node
template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;
};


template <class Type>
class linkedQueueType: public queueADT<Type>
{
public:
    bool operator==
                    (const linkedQueueType<Type>& otherQueue); 

    bool isEmptyQueue() const;
      //Function to determine whether the queue is empty. 
      //Postcondition: Returns true if the queue is empty,
      //               otherwise returns false.

    bool isFullQueue() const;
      //Function to determine whether the queue is full. 
      //Postcondition: Returns true if the queue is full,
      //               otherwise returns false.

    void initializeQueue();
      //Function to initialize the queue to an empty state.
      //Postcondition: queueFront = NULL; queueRear = NULL

    Type front() const;
      //Function to return the first element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: If the queue is empty, the program 
      //               terminates; otherwise, the first 
      //               element of the queue is returned. 

    Type back() const;
      //Function to return the last element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: If the queue is empty, the program 
      //               terminates; otherwise, the last 
      //               element of the queue is returned.

    void addQueue(const Type& queueElement);
      //Function to add queueElement to the queue.
      //Precondition: The queue exists and is not full.
      //Postcondition: The queue is changed and queueElement
      //               is added to the queue.

    void deleteQueue();
      //Function  to remove the first element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: The queue is changed and the first 
      //               element is removed from the queue.
    int numberOfNodes();
    // Return number of nodes in the queue.
    void printQueue();
    //Print the queue.

    linkedQueueType(); 
      //Default constructor

    linkedQueueType(const linkedQueueType<Type>& otherQueue); 
      //Copy constructor

    ~linkedQueueType(); 
      //Destructor

private:
    nodeType<Type> *queueFront; //pointer to the front of 
                                //the queue
    nodeType<Type> *queueRear;  //pointer to the rear of 
                                //the queue
    int count;
};

    //Default constructor
template<class Type>
linkedQueueType<Type>::linkedQueueType() 
{
    queueFront = NULL; //set front to null
    queueRear = NULL;  //set rear to null
} //end default constructor

template<class Type>
bool linkedQueueType<Type>::isEmptyQueue() const
{
    return(queueFront == NULL);
} //end 

template<class Type>
bool linkedQueueType<Type>::isFullQueue() const
{
    return false;
} //end isFullQueue

template <class Type>
void linkedQueueType<Type>::initializeQueue()
{
    nodeType<Type> *temp;

    while (queueFront!= NULL)  //while there are elements left
                               //in the queue
    {
        temp = queueFront;  //set temp to point to the 
                            //current node
        queueFront = queueFront->link;  //advance first to  
                                        //the next node
        delete temp;    //deallocate memory occupied by temp
    }

    queueRear = NULL;  //set rear to NULL
} //end initializeQueue


template <class Type>
void linkedQueueType<Type>::addQueue(const Type& newElement)
{
    nodeType<Type> *newNode;

    newNode = new nodeType<Type>;   //create the node

    newNode->info = newElement; //store the info
    newNode->link = NULL;  //initialize the link field to NULL

    if (queueFront == NULL) //if initially the queue is empty
    {
        queueFront = newNode;
        queueRear = newNode;
    }
    else        //add newNode at the end
    {
        queueRear->link = newNode;
        queueRear = queueRear->link;
    }
    count++;
}//end addQueue

template <class Type>
Type linkedQueueType<Type>::front() const
{
    assert(queueFront != NULL);
    return queueFront->info; 
} //end front

template <class Type>
Type linkedQueueType<Type>::back() const
{
    assert(queueRear!= NULL);
    return queueRear->info;
} //end back

template <class Type>
void linkedQueueType<Type>::deleteQueue()
{
    nodeType<Type> *temp;

    if (!isEmptyQueue())
    {
        temp = queueFront;  //make temp point to the 
                            //first node
        queueFront = queueFront->link; //advance queueFront 

        delete temp;    //delete the first node

        if (queueFront == NULL) //if after deletion the 
                                //queue is empty
            queueRear = NULL;   //set queueRear to NULL
        count--;
    }
    else
        cout << "Cannot remove from an empty queue" << endl;
}//end deleteQueue


    //Destructor
template <class Type>
linkedQueueType<Type>::~linkedQueueType() 
{
    //Write the definition of the destructor
} //end destructor

template <class Type> 
bool linkedQueueType<Type>::operator==
                    (const linkedQueueType<Type>& otherQueue)
{
    bool same = false;

    if (count == otherQueue.count)
        same = true;

    return same;

} //end assignment operator

    //copy constructor
template <class Type>
linkedQueueType<Type>::linkedQueueType
                 (const linkedQueueType<Type>& otherQueue) 
{
    //Write the definition of the copy constructor
}//end copy constructor
template <class Type> 
int linkedQueueType<Type>::numberOfNodes()
{
    return count;

} 

template <class Type> 
void linkedQueueType<Type>::printQueue()
{
    int numberPrinted = 0;
while (!isEmptyQueue())
{
 cout << numberPrinted + 1 << ": " << front() << "\n";
 deleteQueue();    
 numberPrinted++;
 }
}
#endif

score 3 · Accepted Answer

キューのprintQueueメソッドは、キューのプライベート内部に既にアクセスしています。パブリックインターフェイスを使用してキューを出力する代わりに、内部queueFrontポインタを使用してリストをたどり、各要素を出力します。

次のようなもの (この宿題以降の疑似コード):

for(node* n = queueFront; n; n = n->next)
{
    // Print data from node n.
}

score 2 · Accepted Answer

自分で作成したキュークラスを使用している場合は、イテレータを追加します。すでにイテレータを持っているキュークラスを使用している場合は、それを繰り返し処理して出力します。イテレータを持たないキュークラスを使用している場合は、イテレータを持つ別のキュークラスに切り替えます。

を使用している場合は、またはstd::queueに切り替えます。std::liststd::deque

両端キューを反復処理する方法を示す例があります。cplusplus.com

#include <iostream>
#include <deque>

int main ()
{
  std::deque<int> mydeque;

  for (int i=1; i<=5; i++) mydeque.push_back(i);

  std::cout << "mydeque contains:";

  std::deque<int>::iterator it = mydeque.begin();

  while (it != mydeque.end())
    std::cout << ' ' << *it++;

  std::cout << '\n';
  return 0;
}

または：

for (std::deque<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
  // print *it here

score 1 · Accepted Answer

これがどれほど便利かはわかりませんが、各ノードを次のように接続するので、次のnodeType<Type>.linkようなことをしたいかもしれません:

int numberPrinted = 1;
nodeType<Type> *temp;
if (queueFront != NULL) 
{
    temp = queueFront;
    do
    {
        cout << numberPrinted << ": " << temp->info << "\n";
        numberPrinted++;
    }while(temp->link!=NULL);
}

このようにして、キューを変更せずにポインターをたどることができます。

score 1 · Accepted Answer

キューが独自のコードであり、その要素を内部で反復処理できると仮定すると、キューにを指定してfriend ostream& operator<<(ostream&, const your_queue_type&)、要素を出力ストリームに書き込むことができます。

class Queue
{
 public:
  // methods
 friend ostream& operator<<(ostream& o, const Queue& q)
 {
   // iterate over nodes and stream them to o: o << some_node and so on
 }
};

それで

Queue q = ....;
std::cout << q << std::endl; // calls your ostream& operator<<

c++ - C++ でのトラバース キュー

5 に答える 5

Related

Reference

c++ - C++ でのトラバースキュー