今天主要给大家介绍几种数据结构，这几种数据结构在实现原理上较为类似，我习惯称之为类list的容器。具体有list、stack以及queue。
list的节点Node首先介绍下node，也就是组成list的节点。从面向对象的角度来说节点也是就一个类，list里面包含了node对象的实例，以及操作/管理这些实例的方法。先给出一个粗糙的node的C++代码如下代码块所示。可以看出除了保有当前节点的信息，其还有指向前一个节点和后一个节点的指针。如果单独使用当然另外还需要相应的构造函数。如果是使用node组成其他的如list数据结构，也可以不需要node自己的构造函数，而完全交由list分配空间和数据，这部分可以参考《STL源码剖析》。好吧，扯得有点远了，为了讲述的简单，后面的代码都将采取简易的实现方式，如有不妥欢迎私信。
template<typename T> 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来实现）。
先进先出，其实现可以基于链表。但是也可以基于deque/vector。与stack一样若基于已有的结构，其实现是较为简单的，这里不详细叙述。
实现一个list其实从stl的源码可以看出，要真正实现一个list并不像看上去那么简单。考虑到内存分配以及构造的细节，还是比较麻烦的。这里我们主要是为了掌握list的基本结构，对其主要操作做一个了解。所以不必写那么复杂的实现（哈哈，太复杂的我也写不好，还是建议阅读源码哈）。
list的迭代器迭代器是后需几乎所有操作的基础。那么怎么组织这个迭代器呢，或者换句换说，迭代器在哪里定义呢？我们可以这么组织我们的代码：
using namespace std; template <typename Object> class List { private: struct Node { ... }; public: class const_iterator { public: ... protected: Node *current; ... friend class List<Object>; }; class iterator : public const_iterator { public: ... friend class List<Object>; }; public: List( ) { init( ); } ~List( ) //其他方法： ... ... private: int theSize; Node *head; Node *tail; void init( ) { theSize = 0; head = new Node; tail = new Node; head->next = tail; tail->prev = head; } };稍微分析一下，首先list由node一个链接一个构成，所以需要一个node类。另外不希望第三方类使用，所以是私有的。在看迭代器，迭代器是为了方便遍历list或者指代list的当前位置的。所以其本质是一个指针，而且是指向node的指针，所以可以看到const_iterator类有个指针的定义：**Node *current;**。因为有时候通过迭代器只是想单纯访问数据而已，而有时候是希望能够改变node节点的数据。所以就有了const_iterator以及iterator两套哈。我不打算在这里给出迭代器的实现细节，这部分内容有很多教材的源码都是不错的，STL源码可能复杂些不建议。推荐《数据结构与算法分析--C++语言描述(第四版)》，请参考我的GitHub。但是还是有几个细节需要提一下：
迭代器的类要是list的友元。
迭代器在某种意义上就是某种智能指针，所以重载*以及->(或者++, --)操作是必须的。
为了后续操作的方便，在list中==以及！=通常也少不了。
通常需要head(表示第一个元素的前一个位置)以及tail(最后一个元素的最后一个位置)。这是为了在遍历的时候可以用迭代器！=head以及tail来判断是否到达边界。
几个list重要操作的原理与实现现在假设我们已经有了一个功能完整的迭代器，那么接下来的操作基于迭代器就好了。
删除先给出图和代码：