从空队列中删除元素？

Question

我正在写一个抽象数据类型的优先级队列作为大学的一个任务，其他人将要使用它。我在我的类dequeue中有一个函数，它删除队列中的第一个元素并返回此元素的数据。但是，当我尝试从空队列中删除元素时，程序崩溃。我应该在这里做什么？

下面的代码，如果有帮助：

#ifndef PRIORITYQUEUE_H 
#define PRIORITYQUEUE_H 

#include <iostream> 

using namespace std; 

const int max_queue_items = 1000; 

template<class T> 
struct node{ 
    T data; 
    int priority; 
    node *next; 
}; 

template<class T> 
class PriorityQueue 
{ 
    public: 
     /* 
      Constructor that creates an empty queue. 
     */ 
     PriorityQueue(){ 
      head = NULL; 
      size = 0; 
     } 

     /* 
      Adds an element to the queue. 

      Params: 
      data - data of the element 
      priority - priority of the element 
     */ 
     bool is_empty(){ 
      if (size == 0){ 
       return true; 
      } 

      return false; 
     } 

     bool is_full(){ 
      if (size == max_queue_items){ 
       return true; 
      } 

      return false; 
     } 

     /* 
      Adds an element to thq queue. 
      It gets inserted before the first element with 
      lower priority. 
     */ 
     void enqueue(T data, int priority){ 
      node<T> * previous = NULL; 
      node<T> * now = head; 

      while (now != NULL && now->priority >= priority){ 
       previous = now; 
       now = now->next; 
      } 

      node<T> * new_element = new node<T>; 
      new_element->data = data; 
      new_element->priority = priority; 
      new_element->next = now; 

      if (previous == NULL){ 
       head = new_element; 
      } else { 
       previous->next = new_element; 
      } 

      size++; 
     } 

     /* 
      Removes the first element in the queue 
     */ 
     T dequeue(){ 
      T data; 

      if (!is_empty()){ 
       node<T> * now = head; 
       data = now->data; 
       head = head->next; 
       delete now; 

       size--; 
      } 

      return data; 
     } 

     /* 
      Returns the priority of the first element. 
      It's always the highest priority in the queue. 
     */ 
     int get_first_priority(){ 
      return head->priority; 
     } 

     /* 
      Returns the data of the first element in the queue. 
     */ 
     T get_first_value(){ 
      if (is_empty()) 
       throw 0; 

      return head->data; 
     } 

     /* 
      Returns the number of elements in the queue. 
     */ 
     int get_size(){ 
      return size; 
     } 

     /* 
      Deletes the whole queue from the memory. 
     */ 
     void flush(){ 
      node<T> * now; 

      while (head != NULL){ 
       now = head; 
       head = head->next; 
       delete now; 
       size--; 
      } 
     } 

     /* 
      Prints the whole queue following this format: 
      data(priority) 
     */ 
     void print(){ 
      node<T> * now = head; 

      while (now != NULL){ 
       cout << now->data << "(" << now->priority << ")" << endl; 
       now = now->next; 
      } 
     } 

    private: 
     node<T> * head; // Pointer to the head of the queue 
     int size; // Number of elements in the queue 
}; 

#endif // PRIORITYQUEUE_H 

Answer 1

这可能是也可能不是你的问题的根源，但我肯定会认为这是一个问题。在功能dequeue()你可能返回一个未初始化的变量（如果T是不是类型）时is_empty()回报true：

T dequeue() 
    { 
     T data; // Uninitialized if T is not a class type 

     if (!is_empty()) 
     { 
      node<T> * now = head; 

      //-------------------------------------------------------------- 
      // This initialization is skipped when `is_empty()` returns true 
      data = now->data; 
      //-------------------------------------------------------------- 

      head = head->next; 
      delete now; 

      size--; 
     } 

     return data; 
    } 

根据您通过此功能和对T类型的返回值做什么，你的程序可能会有未定义的行为（我可以想象T是一个指针类型，你稍后解除引用）。

您可能要到函数的第一行变成：

T data = T(); 

这就加强你的data对象的值初始化。如果T是一个类类型，将调用默认的构造函数。否则，data将被初始化为零。

这就要求dequeue()那么应该检查在使用它之前返回值的函数（或更好，请拨打is_empty()队列，以检查它不是空试图从它弹出一个值之前）。

时dequeue()被调用，队列为空你甚至可以考虑抛出一个异常：

T dequeue() 
{ 
    if (is_empty()) 
    { 
     // Requires including the <stdexcept> standard header 
     throw std::logic_error("Queue is empty"); 
    } 

    node<T> * now = head; 
    T data = now->data; 
    head = head->next; 
    delete now; 

    size--; 

    return data; 
} 

客户现在有责任确保dequeue()是从来没有所谓的对空队列（或他们将包裹通话到dequeue()成try/catch块来处理可能引发的异常。

另一种可能性是返回bool到客户端指示值是否已成功弹出，可能分配弹出的元素通过参考传递的参数：

bool dequeue(T& data) 
{ 
    if (is_empty()) 
    { 
     return false; 
    } 

    node<T> * now = head; 
    data = now->data; 
    head = head->next; 
    delete now; 

    size--; 

    return true; 
} 

这样，客户端负责检查函数的结果。如果函数返回false，那么data变量将被初始化为客户端初始化它的任何值。处理错误情况的职责再次转交给客户。

Answer 2

我觉得有一些问题。

首先也是最重要的是，这个类没有析构函数。如果不是所有的元素都在你的程序中出队，那么会有内存泄漏。编写析构函数或使用智能指针而不是原始指针。其次，作为@Andy Prowl（顺便说一句，谁知道如何在Twitter这样的人后@）说，应该考虑未初始化的局部变量。而T data = T()对于内置和自定义类型都适用。

第三，我认为有一个容量限制max_queue_items的队列，但没有对应的代码队列部分。

即使我认为所有这些缺陷在正常情况下都不会导致严重的故障。也许问题出现在你的代码中，调用这个类，不正确的处理对于未初始化的返回值会导致崩溃。

Answer 3

我在您看到的唯一潜在问题出列是您正在创建一个未知类型T的临时变量。如果您要在优先级队列中存储没有默认构造函数的类型的数据，您将拥有一个您的出列调用并尝试默认构造该变量时出现问题。

如果是这种情况，我建议您重新设置您的优先级队列以保存指向模板类型的指针而不是数据本身。