数据结构《21》----2014 WAP 初试题----Immutable queue - L.J.SHOU的专栏 - 博客频道 - CSDN.NET

数据结构《21》----2014 WAP 初试题----Immutable queue - L.J.SHOU的专栏 - 博客频道 - CSDN.NET

2014 WAP初试题----实现一个不可变的队列：

看似很简单。。实则，不同的版本效率的差距可能是巨大的。。甚至难以想象。。

之前用STL库的queue进行了对比，差别非常大。。

用上一篇文章的immutable stack 来实现 immutable queue.

其实就是用两个栈实现队列，具体的思想可以参考 编程之美。。

注意：代码中析构函数那一段代码的目的主要是为了避免析构函数递归调用时递归深度太大。。

通过将链表后序的节点的智能指针复制到局部的vector中，通过vector的析构函数自动调用成员的析构函数的规则来实现。。

可能有点绕，大家可以仔细琢磨以下。。

附加题:

实现一个reverse操作（这道题据说坑了不少同学，其实非常地简单，一句话就能搞定）

Read full article from 数据结构《21》----2014 WAP 初试题----Immutable queue - L.J.SHOU的专栏 - 博客频道 - CSDN.NET