今天主要给大家介绍几种数据结构，这几种数据结构在实现原理上较为类似，我习惯称之为类list的容器。具体有list、stack以及queue。 list的节点Node 首先介绍下node，也就是组成list的节点。从面向对象的角度来说节点也是就一个类，list里面包含了node对象的实例，以及操作/管理这些实例的方法。先给出一个粗糙的node的C++代码如下代码块所示。可以看出除了保有当前节点的信息，其还有指向前一个节点和后一个节点的指针。如果单独使用当然另外还需要相应的构造函数。如果是使用node组成其他的如list数据结构，也可以不需要node自己的构造函数，而完全交由list分配空间和数据，这部分可以参考《STL源码剖析》。好吧，扯得有点远了，为了讲述的简单，后面的代码都将采取简易的实现方式，如有不妥欢迎私信。 template struct Node { typedef void * void_pointer; void_pointer prev; void_pointer next; T data; Node(T data){ this->data = data; prev = nullptr; next = nullptr; } }; Node构成的数据结构有哪些 说完了node，那么由node(或其变体)作为基本单元的数据结构有哪些呢？当然首先有list(链表)，其次stack(栈)以及queue(队列)也是哈。list是双向链接的，头和尾都可以插入和删除node，当然中间插入删除也是可以的。而stack则是先进后出的队列，啥意思呢，也就是说：插入和删除都是针对最顶层的node的；queue则不同，它是先进先出的，和我们日常排队买东西是一样的原理。接下来分别介绍。 list 先来个图感性认识一下： 其实看了图之后也就无需多言了哈，不就是node一个链接一个么。嘿，简单！！！ stack 那stack呢，更加简单啦。只要将双向的链表换成单向的链表就可以实现了哈。在表的前端插入来实施push操作，通过删除表的前端元素来完成pop操作。top操作知识考察表前端元素并返回它的值。（当然stack也可以用基于vector来实现）。 queue 先进先出，其实现可以基于链表。但是也可以基于deque/vector。与stack一样若基于已有的结构，其实现是较为简单的，这里不详细叙述。 实现一个list 其实从stl的源码可以看出，要真正实现一个list并不像看上去那么简单。考虑到内存分配以及构造的细节，还是比较麻烦的。这里我们主要是为了掌握list的基本结构，对其主要操作做一个了解。所以不必写那么复杂的实现（哈哈，太复杂的我也写不好，还是建议阅读源码哈）。 list的迭代器 迭代器是后需几乎所有操作的基础。那么怎么组织这个迭代器呢，或者换句换说，迭代器在哪里定义呢？我们可以这么组织我们的代码： using namespace std; template class List { private: struct Node { ... }; public: class const_iterator { public: ... protected: Node *current; ... friend class List