实现一个队列

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"的多重定义 - 没有成功.

编辑:当编译器给出错误消息时,它会打开来自I-not-know-where的locale_facets.tcc文件,并说明错误在以下函数中的第2497行:

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

有没有人有任何见解？

Answer 1

由于这是家庭作业,这里有一些关于队列的信息以及如何实现队列.

队列是标准的抽象数据类型.它有几个与之相关的属性:

1. 它是一种线性数据结构 - 所有组件都排成一条直线.
2. 它有一个增长/衰减规则 - 从两端添加和删除队列.
3. 知道它们如何构建不应该是使用它们不可或缺的因为它们具有可用的公共接口.

可以使用顺序数组或链接列表对队列进行建模.
如果您正在使用数组,则需要考虑一些因素,因为您在一个方向上增长,因此最终会耗尽数组.然后你可以做出一些选择(转变与成长).如果您选择返回到数组的开头(环绕),则必须确保头部和尾部不重叠.如果您选择简单地增加队列,则会浪费大量内存.

如果您使用的是Linked-List,则可以在任何位置插入,队列将从尾部增长并从头部缩小.您也不必担心填写列表并且必须包装/移动元素或增长.

但是,您决定实现队列,请记住Queues应提供一些使用队列的通用接口.这里有些例子:

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

您可能希望将其他操作添加到队列中(在C++中,您可能需要在队列的前端/后端使用迭代器),但是如何构建队列不应对其提供的操作产生影响.

但是,根据您希望如何使用队列,有更好的方法来构建它.通常的权衡是插入/移除时间与搜索时间的关系.这是一个不错的参考.

Answer 2

如果您的赋值与队列实现没有直接关系,那么您可能希望std::queue在C++中使用内置类:

#include <queue>

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