從空隊列中刪除元素？

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的臨時變量。如果您要在優先級隊列中存儲沒有默認構造函數的類型的數據，您將擁有一個您的出列調用並嘗試默認構造該變量時出現問題。

如果是這種情況，我建議您重新設置您的優先級隊列以保存指向模板類型的指針而不是數據本身。