拇指接龙游戏中的Undo道具与STL容器deque简介-创新互联

引子

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

需求

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

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

• 可以悔一张牌

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

• 可以连续多次悔牌

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

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

方案

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

    std::deque UndoDeque;//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 c    创建一个空的deque。

      deque c1(c2)   复制一个deque。

      deque c(n)   创建一个deque，含有n个数据，数据均已缺省构造产生。

      deque c(n, elem)   创建一个含有n个elem拷贝的deque

      deque c(beg,end)   创建一个以[beg;end)区间的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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。