用链表实现的C++队列

Question

晚上好。我一直在尝试在C++中实现队列类，以之前创建的链表类为基础。 链式链表：

#include <cstddef>
#include <iostream>
#include <cstdio>

using namespace std;

template <class T>
class LinkedList {

public:
    LinkedList() {
        head = NULL;
    }
    ~LinkedList() {
        MakeEmpty();
    }

    struct Node {
        T value;
        Node *next;
    };

    Node* getHead() {
        return head;
    }

    void Print();
    void Insert();
    void MakeEmpty();

private:
    Node *head;     // Head of the linked list.
};

队列类：

#include "LinkedList.h"

template <class T>
class Queue {

public:
    Queue() {
        LinkedList<T>::Node *tnode = Q.getHead();
    }

    ~Queue() {
        Q.MakeEmpty();
    }

    void Enqueue( T x ) {
        LinkedList<T>::Node *cnode = Q.getHead();

        //Find the last element of Q
        while( cnode -> next != NULL ) {
            cnode = cnode -> next;
        }
        //Add x to the end of the queue
        Q.Insert( x );
    }

    void Dequeue() {
        LinkedList<T>::Node *hnode = Q.getHead();
        //Rest of function
    }

    void Print() {
        Q.PrintList();
    }

private:
    LinkedList<T> Q;
};

你可能已经注意到，我正在将它们制作成模板类。编译时，系统提示Queue类的构造函数中找不到tnode变量。有什么建议可以解决这个问题吗？

编辑1：我收到的错误信息如下：

RCQueue.h: 在构造函数‘Queue::Queue()’中：
RCQueue.h:8:28: error: ‘tnode’ was not declared in this scope LinkedList::Node *tnode = Q.getHead();

我的构造函数的主要目的是将LinkedList类中的“head”指针初始化为NULL。我还想知道如何声明在另一个模板类中声明的结构体变量。

- lalaman

Answer 1

Enqueue Algorithm :
1. Create a newNode with data and address.
2. if queue i.e front is empty   
i.  front = newnode;   
ii. rear  = newnode;
3. Else 
i.rear->next = newnode;    
ii.rear = newnode;

Dequeue Algorithm :
1. if queue is i.e front is NULL      printf("\nQueue is Empty \n");
2. Else next element turn into front        
i.  struct node *temp = front ;  
ii. front = front->next;   
iii.free(temp);  

C++实现：

     #include <bits/stdc++.h>
      using namespace std;

      struct node
      {
        int data;
        node *next;
      };

      node *front = NULL;
      node *rear =NULL;


     void Enque(int data)
     {
           node *newnode = new node;
           newnode->data = data;
           newnode ->next = NULL;


           if(front==NULL) 
           {
               front=newnode;
               rear=newnode;
           }

           else
           {
              rear->next = newnode;
              rear = newnode;
           }
      }





    void Deque()
    {
       struct node *temp;

       if (front == NULL)
       {
         printf("\nQueue is Empty \n");
         return;
       }

       else
       {
           temp = front;
           front = front->next;
           if(front == NULL)  rear = NULL;
           free(temp);
       }
     }


    void display()
    {
        node *temp=front;
        if(front==NULL)
        {
          printf("\nQueue is Empty \n");
        }

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

- rashedcs

---

我已经编辑了我的帖子......@ Marcus Müller请检查我的答案，看看它是否正确或错误。 - rashedcs

Answer 2

您需要在Queue内引用的LinkedList中的每个Node类型前加上typename，因为它依赖于模板参数T。具体来说，

template <class T>
class Queue {

public:
    Queue() {
        typename LinkedList<T>::Node *tnode = Q.getHead();
    }

    ~Queue() {
        Q.MakeEmpty();
    }

    void Enqueue( T x ) {
        typename LinkedList<T>::Node *cnode = Q.getHead();

        //Find the last element of Q
        while( cnode -> next != NULL ) {
            cnode = cnode -> next;
        }
        //Add x to the end of the queue
        Q.Insert( x );
    }

    void Dequeue() {
        typename LinkedList<T>::Node *hnode = Q.getHead();
        //Rest of function
    }

    void Print() {
        Q.PrintList();
    }

private:
    LinkedList<T> Q;
};

注意在使用LinkedList<T>::Node之前添加typename的添加。

当然，你也会听到对于LinkedList中缺少定义的MakeEmpty()在你的Queue类中被调用的抱怨，所以只需添加一个定义即可。

关于为什么需要typename的更多信息，this post解释得非常清楚。

- Alejandro

---

谢谢Alejandro。我很感激你的回答，以及提供的链接。 - lalaman

我很高兴能够帮助！ - Alejandro