FIFO实现

Question

在实现FIFO时，我使用了以下结构：

struct Node
{
    T info_;
    Node* link_;
    Node(T info, Node* link=0): info_(info), link_(link)
    {}
};

我认为这是很多STL容器的一个众所周知的技巧(例如List)。这是一个好的实践吗？当你说Node有一个类型为指针的成员时，这对编译器意味着什么？这是一种无限循环吗？

最后，如果这是一个糟糕的实践，我将如何实现更好的FIFO。

编辑:各位，这一切都是关于实现的。我对STL库非常熟悉，并且了解很多库中的容器。我只是想和那些能给出好的实现或好的建议的人讨论一下。

Answer 1

在C和C++中，指向被声明类型的对象的指针都很好。这是基于这样一个事实:指针是固定大小的对象(例如，在32位平台上总是32位整数)，因此您不需要知道所指向类型的完整大小。

事实上，您甚至不需要完整的类型声明来声明指针。一个转发声明就足够了：

class A; // forward declared type

struct B
{
    A* pa; //< pointer to A - perfectly legal
};

当然，您需要在实际访问成员时的作用域中有一个完整的声明：

#include <A.hpp> // bring in full declaration of class A
...
B b;
b.pa = &a; // address of some instance of A
...
b.pa->func(); // invoke A's member function - this needs full declaration

有关先入先出的信息，请查看std::queue。std::list、std::deque和std::vector都可以用于此目的，但也提供了其他功能。

Answer 2

这是一个好的实践吗？

我看不出有什么特别的问题。

当你说Node有一个指针类型为其类型的成员时，对编译器意味着什么？

一个类存储指向同一个类的对象的指针并没有什么问题。

最后，如果这是一个糟糕的做法，我如何才能实现更好的

。

我会使用std::queue ;)

Answer 3

显然，您正在使用链表作为队列的底层实现。这并没有什么特别糟糕的地方。

仅供参考，就实现而言，std::queue本身使用std::deque作为其底层实现。deque是一种更复杂的数据结构，它由经过巧妙管理的动态数组块组成。它最终比链表更好，因为：

使用链表的

1. ，每次插入都意味着你必须进行昂贵的动态内存分配。使用动态数组则不需要。只在缓冲区必须增长时才分配内存。
2. 数组元素是连续的，这意味着元素访问可以很容易地缓存在硬件中。