实现一个队列。

Question

我有一个队列类（取自WordPress）如下所示：

#include<iostream.h>

class Queue
    {
    private:
     int data;
     Queue*next;
    public:
     void Enque(int);
     int Deque();
    }*head,*tail;    

    void Queue::enque(int data)
    {
     Queue *temp;
    temp=new Queue;
    temp->data=data;
    temp->next=NULL;
    if(heads==NULL)
     heads=temp;
    else
    tail->next=temp;
    tail=temp;
    }

    int Queue::deque()
    {
    Queue* temp;//
    temp=heads;
    heads=heads->next;
    return temp->data;
    }

我正在尝试弄清楚编译器为什么告诉我有“head”和“tail”的多个定义，但一直没有成功。

编辑：当编译器给出错误消息时，它会打开一个来自不知道哪里的locale_facets.tcc文件，并说错误在以下函数的第2497行：

bool
 __verify_grouping(const char* __grouping, size_t __grouping_size,
        const string& __grouping_tmp)

有没有人有任何见解？

- Meir

---

@Meir - 你为什么不能使用标准队列，非要自己实现呢？听起来有点奇怪，队列是一个非常基本和常见的标准库。 - Yuval Adam

你能发布整个队列类吗？ - Uri

那不是一个队列类，那只是队列类中的一个函数...实际上没有变量“head”，也没有声明“tail”，所以很难帮助你。另外，为什么要使用这个队列实现...你应该阅读所有关于使用队列的其他问题的帖子。 - Tom

请解释为什么您不能使用std queue，但是为什么您可以从WordPress中复制一个。 - Tom

糟糕，我现在添加了类的声明。@Tom-虽然我知道C++包含内置队列，但我仍想让这个实现起来。 - Meir

Answer 1

由于这是作业，以下是有关队列及如何实现队列的一些信息。

队列是一种标准的抽象数据类型，具有以下属性：

1. 它是线性数据结构，所有组件都按直线排列。 2. 它有增长/衰减规则，队列从相反的两端添加和删除。 3. 对它们的构造方式的了解不应该是使用它们的必要条件，因为它们有可用的公共接口。

队列可以使用顺序数组或链表进行建模。如果您使用数组，有一些需要考虑的事情，因为您只能向一个方向增长，所以最终会用完数组。然后您需要做出一些选择（移位与增长）。如果您选择将其移回数组的开头（环绕），则必须确保头部和尾部不重叠。如果您选择简单地增加队列，则会浪费很多内存。

如果您使用链表，可以在任何位置插入，队列将从尾部增长并从头部缩小。您也不必担心填满列表并不得不包裹/移动元素或增长。

无论您决定如何实现队列，都要记住队列应该提供一些通用的接口来使用它。以下是一些例子：

1. enqueue - 在队列的后面（尾部）插入一个元素
2. dequeue - 从非空队列的前面（头部）删除一个元素。
3. empty - 返回队列是否为空
4. size - 返回队列的大小

您可能希望添加其他操作到您的队列中（在C++中，您可能需要一个迭代器来访问队列的前/后），但是您构建队列的方式不应影响它所提供的操作。

然而，根据您想要使用队列的方式，有更好的构建方法。通常的权衡是插入/删除时间与搜索时间之间的差异。这里是一个不错的参考。

- Nick Presta

Answer 2

如果你的任务并不直接涉及队列实现，你可以使用C++中内置的std::queue类：

#include <queue>

void test() {
    std::queue<int> myQueue;
    myQueue.push(10);
    if (myQueue.size())
        myQueue.pop(); 
}

- Mehrdad Afshari

Answer 3

为什么不直接使用C++标准库中的队列？

#include <queue>

using namespace std;

int main() {
    queue<int> Q;

    Q.push(1);
    Q.push(2);
    Q.push(3);

    Q.top(); // 1
    Q.top(); // 1 again, we need to pop
    Q.pop(); // void

    Q.top(); // 2
    Q.pop();

    Q.top(); // 3
    Q.pop();

    Q.empty(); // true
    return 0;
}

- Jasiu

---

你是不是想写 top 而不是 pop？感谢你的回答，这是我见过最直接的一个。 - James MV

Answer 4

有几个问题需要解决：

• 您的方法声明为Enqueue和Dequeue，但定义为enqueue和dequeue：C++是大小写敏感的。
• 您的方法引用“heads”，这似乎不存在，是否应该是“head”？

- kdt

---

我猜你之所以没有留下评论是因为你不能评论...因此我只给了你一个+1，这样你就可以更接近评论了，因为那是一个很好的评论。 - Tom

Answer 5

如果你需要用于BFS...只需使用deque。

#include <deque>

using namespace std;

void BFS() {
    deque<GraphNode*> to_visit;
    to_visit.push_back(start_node);
    while (!to_visit.empty()) {
        GraphNode* current = to_visit.front();
        current->visit(&to_visit);  // enqueues more nodes to visit with push_back
        to_visit.pop_front();
    }
}

GraphNode::visit 方法应该完成所有的“工作”，并将更多节点添加到队列中以进行访问。您所需的唯一方法是 push_back()、front() 和 pop_front()。

这就是我一直使用的方法。希望这可以帮助到您。

- Tom

Answer 6

看起来你的问题 可能 与以下原因有关：

class Queue {
  // blah
} *head, * tail;

正在定义一个Queue类，并声明head和tail为类型Queue*。它们看起来不像是类的成员，但实际上它们应该是。

- Tom