拇指接龙游戏中的Undo道具与STL容器deque简介

　　引子

在我的视频课程《拇指姑娘空当接龙》游戏（http://edu.51cto.com/course/course_id-1830.html）中，Undo道具对于游戏新手来说应当是最常用道具之一。其作用类似于下棋中的“悔棋”。因为接龙游戏要求玩家在移牌前要先进行心中分析，但是由于此游戏的复杂性（特别是到了后期较复杂的回合布局中），由于玩家预先分析不周密，可能导致需要“悔牌”操作；否则，整个牌局将陷于死局中（当然，如果红心数足够，玩家也可以借助其他道具解救）。

　　需求

上述Undo道具（“悔牌”操作）涉及到如下一些情况：

• 选择什么样的数据结构实现最恰当？

• 可以悔一张牌

• 可以悔系列牌（即玩家把一个系列从下部区域的某一列移动到另一列时）

• 可以连续多次悔牌

• 悔牌后对应顺序与位置不可改变

• 最多支持多少次连续悔牌最合适

方案

　　基于上述需要，我选择了使用了STL库的双端队列－－容器deque (double-ended queue)。我创建了两个deque：一个是主要容器，另一个起辅助标记作用。

    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、要求容器释放不再使用的元素。