代码之家 › 专栏 › 技术社区 › Blake Killnine

遍历C中的队列++

traversal queue c++

2

Blake Killnine · 技术社区 · 12 年前

我有一个C++队列需要打印。很容易打印第一个节点,然后删除它,然后再次打印第一个结点,这将是第二个结点。但这会抹去整个列表,只为了打印一次。。。作为一种变通方法,我创建了一个临时队列对象,并将其传递给我的打印方法,并做了与第一个对象相同的事情,这将非常棒,只是它使用指针使队列动态,因此从第一个对象复制的任何对象中删除它们仍然是删除相同的数据。我还不擅长指点,但我相信一定有一种简单的方法可以做到这一点,有什么建议吗?

这是代码:

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

5 回复 | 直到 12 年前

1

3

Mark B 12 年前

您的队列 printQueue 方法已经可以访问队列的私有内部。不用公共接口打印队列,只需使用内部 queueFront 指针并遍历列表,打印每个元素。

类似于(本作业后的伪代码):

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

2

David Schwartz 12 年前

如果您使用的是自己编写的队列类,请在其中添加迭代器。如果您使用已经有迭代器的队列类时,请对其进行迭代以打印它。如果您所使用的队列类没有迭代器,请切换到其他有迭代机的队列类。

如果您正在使用 std::queue 切换到 std::list 或 std::deque .

有 an example 在…上 cplusplus.com 它显示了如何在deque中迭代:

#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

3

1

juanchopanza 12 年前

如果队列是您自己的代码,并且假设您可以在内部迭代它的元素,那么您可以给它一个 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<<

4

1

Hooman 12 年前

我不知道这有多有用,但由于您使用将每个节点附加到下一个节点 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);
}

这样,您就可以在不更改队列的情况下只跟踪指针。

5

0

sundavar 4 年前

这里有一种简单的方法,只需一个指针和一个while循环

while(pointer != NULL) pointer.info pointer = pointer.next