c++ - 关于在 C++ 模板化队列中实现 put() 函数的建议？

Question

我正在尝试实现一个不允许更改头文件定义的队列，如下所示:

class PQueue
{
  private:

    struct Node
    {
      EType Item;
      unsigned Priority;
      unsigned Identifier;
      Node * Pred;
      Node * Succ;
    };

    Node * Head;    // Pointer to head of chain (front)
    Node * Tail;    // Pointer to tail of chain (back)

  public:

    // Initialize pqueue to empty
    //
    PQueue();

    // De-initialize pqueue
    //
    ~PQueue();

    // Re-initialize pqueue to empty
    //
    void reset();

    // Initialize pqueue using existing pqueue
    //
    PQueue( const PQueue<EType>& );

    // Assign into pqueue from other pqueue
    //
    PQueue<EType>& operator=( const PQueue<EType>& );

    // Display attributes and contents of pqueue
    // (from front to back, or back to front)
    //
    void display( ostream&, Direction ) const;

    // Return number of items in pqueue
    //
    unsigned length() const;

    // Return copy of item at front of pqueue (unless pqueue is empty)
    //
    bool front( EType& ) const;

    // Return copy of item at back of pqueue (unless pqueue is empty)
    //
    bool back( EType& ) const;

    // Insert one item (with specified priority) into pqueue (if possible)
    //
    bool put( const EType&, unsigned );

    // Remove item with highest priority from pqueue (unless pqueue is empty)
    //
    bool get( EType& );

    // Discard item with specified identifier from pqueue (if possible)
    //
    bool discard( unsigned );
};

到目前为止，我有这些构造函数和析构函数:

template <typename EType> PQueue::PQueue() {
    Head->Pred = NULL;
    Tail->Succ = NULL;
    Tail->Pred=Head;
    Head->Succ=Tail;
} 

template <typename EType> PQueue::~PQueue() {
    reset();
    delete Head;
    Head = NULL;
    delete Tail;
    Tail = NULL;
}

现在我卡在 put() 上了，我不知道从哪里开始，有什么帮助吗？

Answer 1

您应该分配一个节点，并将其挂接到列表中。

像这样:

   template <typename EType>
   bool PQueue::put( const EType& et, unsigned pri ) {
      Node *p = new Node ();
      p->Item = et;
      p->priority = pri;
// now hook it into the list
   p->pred = NULL;
   head = p;
   }

但是，这还不够，因为您没有在构造函数中正确初始化 head 和 tail；以至于我无法判断您是在创建单向链表还是双向链表。在您当前的代码中，您的代码就像 head 和 tail 指向实际节点一样，但我看不到这些节点在哪里(或创建)。

此外，您的一些代码是在 EType 上模板化的，而其他部分则不是。您需要保持一致。