引子
在我的视频课程《拇指姑娘空当接龙》游戏（http://edu.51cto.com/course/course_id-1830.html）中，Undo道具对于游戏新手来说应当是最常用道具之一。其作用类似于下棋中的“悔棋”。因为接龙游戏要求玩家在移牌前要先进行心中分析，但是由于此游戏的复杂性（特别是到了后期较复杂的回合布局中），由于玩家预先分析不周密，可能导致需要“悔牌”操作；否则，整个牌局将陷于死局中（当然，如果红心数足够，玩家也可以借助其他道具解救）。
需求
上述Undo道具（“悔牌”操作）涉及到如下一些情况：
-
选择什么样的数据结构实现最恰当？
-
可以悔一张牌
-
可以悔系列牌（即玩家把一个系列从下部区域的某一列移动到另一列时）
-
可以连续多次悔牌
-
悔牌后对应顺序与位置不可改变
-
最多支持多少次连续悔牌最合适
方案
基于上述需要，我选择了使用了STL库的双端队列－－容器deque (double-ended queue)。我创建了两个deque：一个是主要容器，另一个起辅助标记作用。
|
1
2
|
std::deque<UndoNode> UndoDeque;
//main
std::deque<
int
> AuxUndoDeque;
//auxiliary
|
我们的悔牌机制具体描述如下：
目前的设计目标是队列中最多容纳8项，但是这些入队列的项可能有的是单项，有的是小系列（需要一起操作）。
考虑到有的系列特别长（例如从13点到5点的仅仅一个系列就包含９张牌），作进一步简化处理，方案是：
如果有一个系列入队列，则先清空队列中所有内容，再入队列此系列。
为此，我们设计另一个辅助队列AuxUndoDeque，用于记忆撤消队列中可能成组的项。
算法描述如下：
i.PUSH当前要入队列的项（单或者系列）; 同时，PUSH到AuxUndoDeque中相应的标志int
ii.如果当前仅有一张扑克入队列，而且如果队列OK（<=8) ，那么情况简单；如果>8(此前队列内总数已为8)，则判断如下：
a. if arr[0]是一个入队列单项，弹出这个单项即可
b. arr[0..k]是一个小系列，则弹出这个系列。
iii.如果当前入队列的是一个系列，则复杂些，因为可能需要从队列尾弹出不止一组（多个单项和多个小系列）。
如果上述辅助队列中对应参数为－1，说明要从尾部弹出一项；如果是N（>1的整数），说明要从尾部弹出N项（小系列）。
提示：
１，无论主队列是出队操作（从头部）还是入队操作（从尾部），相应地，其辅助队列也要进行相应的出队和入队操作。
２，辅助队列中存储一个整数，当－１时表示主队列中加入的是一个单项，如果是N>1的一个整数，则此整数表示主队列中加入的是一个长度为N的系列。
补充－STL容器主要操作知识
deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成员函数：
头文件：#include<deque>
函数构造：
deque<Elem> c 创建一个空的deque。
deque<Elem> c1(c2) 复制一个deque。
deque<Elem> c(n) 创建一个deque，含有n个数据，数据均已缺省构造产生。
deque<Elem> c(n, elem) 创建一个含有n个elem拷贝的deque
deque<Elem> c(beg,end) 创建一个以[beg;end)区间的deque
c.~deque<Elem>() 销毁所有数据，释放内存
成员函数：
c.assign(beg,end) 将[beg; end)区间中的数据赋值给c。
c.assign(n,elem) 将n个elem的拷贝赋值给c。
c. at(idx) 传回索引idx所指的数据，如果idx越界，抛出out_of_range。
c.back() 传回最后一个数据，不检查这个数据是否存在。
c.begin() 传回迭代器中的第一个数据。
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos) 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() 传回第一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem) 在pos位置插入一个elem拷贝，传回新数据位置
c.insert(pos,n,elem) 在pos位置插入>n个elem数据。无返回值
c.insert(pos,beg,end) 在pos位置插入在[beg,end)区间的数据。无返回值
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.pop_front() 删除头部数据。
c.push_back(elem) 在尾部加入一个数据。
c.push_front(elem) 在头部插入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.size() 返回容器中实际数据的个数。
c.swap(c2) 将c1和c2元素互换。
swap(c1,c2) 将c1和c2元素互换。
特点：
1、支持随机访问，即支持[]以及at()，但是性能没有vector好。
2、支持两端操作，push(pop)-back(front)，但性能不及list。
最佳使用情况：
1、需要在两端插入和删除元素。
2、无需引用容器内的元素。
3、要求容器释放不再使用的元素。
本文转自朱先忠老师51CTO博客，原文链接：http://blog.51cto.com/zhuxianzhong/1546356 ，如需转载请自行联系原作者
