拇指接龙游戏中的Undo道具与STL容器deque简介-创新互联
引子
在我的视频课程《拇指姑娘空当接龙》游戏（http://edu.51cto.com/course/course_id-1830.html）中，Undo道具对于游戏新手来说应当是最常用道具之一。其作用类似于下棋中的“悔棋”。因为接龙游戏要求玩家在移牌前要先进行心中分析，但是由于此游戏的复杂性（特别是到了后期较复杂的回合布局中），由于玩家预先分析不周密，可能导致需要“悔牌”操作；否则，整个牌局将陷于死局中（当然，如果红心数足够，玩家也可以借助其他道具解救）。
需求
上述Undo道具（“悔牌”操作）涉及到如下一些情况：
选择什么样的数据结构实现最恰当？
可以悔一张牌
可以悔系列牌（即玩家把一个系列从下部区域的某一列移动到另一列时）
可以连续多次悔牌
悔牌后对应顺序与位置不可改变
最多支持多少次连续悔牌最合适
方案
基于上述需要，我选择了使用了STL库的双端队列－－容器deque (double-ended queue)。我创建了两个deque：一个是主要容器，另一个起辅助标记作用。
std::dequeUndoDeque;//main std::deque 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
deque
deque
deque
c.~deque
成员函数：
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、要求容器释放不再使用的元素。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：拇指接龙游戏中的Undo道具与STL容器deque简介-创新互联
新闻来源：http://ybzwz.com/article/copiph.html
