FIFO队列链表实现

Question

这里是一段代码，我正在尝试使用链表实现队列：

#include <iostream>
#include <cstdlib>
using namespace std;
template <class Item>
class Queue{

public:
    struct  node{
      Item item;node *next;
      node (Item x){
        item=x; next=0;
      }
    };
    typedef node* link;
    link  head, tail;

public:
    Queue(int){  head=0;}
    int empty() const {   return head==0; }
    void put(Item x){

        node* t=tail;
        tail=new node(x);
        if (head==0) head=tail;
        else   t->next=tail;
    }
    Item get(){  

        Item v=head->item;link t=head->next;
        delete head; head=tail return v;
    }

    };

int main(){
    return 0;
}

但我在指针方面遇到了问题。例如，当我写Item v = head->时，它应该显示选择项以选择项目，但它没有显示出来。在代码的其他位置，经过 -> 这个符号之后，代码也没有给我选择项来选择 item 或者 next。请帮助。

- user466534

---

你能否发布你遇到的确切问题，包括错误输出、错误信息和期望输出。另外，请使用完整的句子，你的问题很难阅读。 - Philip Potter

考虑到“它应该向我显示选择选项”：您想让您的IDE（编辑器）显示head成员列表吗？还是其他什么东西？ - phimuemue

是的，有成员，但它没有显示给我。 - user466534

好的，那么这不是“FIFO队列链表实现”的问题，而是你的编辑器出了问题。你使用的是哪个编辑器？ - phimuemue

我已经有一段时间没有使用VS了，但我知道它的IntelliSense有时候不起作用。所以尝试谷歌搜索“visual studio 2010 intellisense not working”或类似的内容。 - phimuemue

Answer 1

ON: -> 操作符可以重载，因此开发环境无法确定该如何处理它。如果您确实想要自动完成，可以进行以下操作（暂时或永久性）。

// IMPORTANT. Make sure "head" is not null before you do it!
Node &headNode(*head); // Create a reference 
headNode.next = tail; // Use TAB or CTRL+SPACE or whatever here after dot

OFF: 我已经审核了你的代码并进行了一些更正

template <class Item>
class Queue {
public:
        Queue()
        : head(0)
        , tail(0)
        { }
        bool empty() const { return head==0; }
        void put(const Item& x)
        {
                Node* t = tail;
                tail = new Node(x);
                if (head==0)
                        head = tail;
                else
                        t->next = tail;
        }
        Item get()
        {
                Item v = head->item;
                Link t = head->next;
                delete head;
                head = t;
                if(head==0)
                        tail = 0;
                return v;
        }
private:
        struct Node {
                Item item;
                Node *next;
                Node(const Item& x)
                : item(x)
                , next(0)
                {}
        };
        typedef Node* Link;
        Link head,tail;
};

• 从Queue构造函数中删除了一个名为int的无名参数
• 将node重命名为Node，将link重命名为Link，因为Item是Item，不是item，只是为了使其标准化一些
• 在Queue构造函数中初始化tail
• 在可能的情况下使用初始化器列表而不是代码
• 修复Queue::get()，如果队列变为空，则将tail设置为零
• 在Queue::put()和Queue::Node::Node()的参数列表中使用常量引用
• Node、Link、head和tail现在是私有的
• Queue::empty()从现在开始返回bool而不是int

- Notinlist

Answer 2

如果可能的话，最好重复使用现有容器。

STL 明确包含了一些容器适配器，例如一个队列容器适配器（默认基于 deque，这是最有效的选择）。

如果你不需要多态行为，那么 std::queue<Item> 是你要找的东西，它既非常高效（比你自定义的基于列表的队列更高效），而且可以避免内存管理问题。

如果你需要多态行为，则使用 std::queue< std::unique_ptr<Item> >。

- Matthieu M.

---

不要重复造轮子，除非你打算更深入地了解轮子。 - Mizipzor

我认为你过度设计了答案。他只是遇到了编辑器自动完成功能的问题。 - celavek

@cevalek：我也这么认为，但在评论之前并不清楚。有趣的是，我仍然因此获得了赞，所以我想我不是唯一一个没有发现真正问题的人。 - Matthieu M.