拇指接龍游戲中的Undo道具與STL容器deque簡(jiǎn)介

　　引子

在我的視頻課程《拇指姑娘空當(dāng)接龍》游戲（http://edu.51cto.com/course/course_id-1830.html）中，Undo道具對(duì)于游戲新手來(lái)說(shuō)應(yīng)當(dāng)是最常用道具之一。其作用類(lèi)似于下棋中的“悔棋”。因?yàn)榻育堄螒蛞笸婕以谝婆魄耙冗M(jìn)行心中分析，但是由于此游戲的復(fù)雜性（特別是到了后期較復(fù)雜的回合布局中），由于玩家預(yù)先分析不周密，可能導(dǎo)致需要“悔牌”操作；否則，整個(gè)牌局將陷于死局中（當(dāng)然，如果紅心數(shù)足夠，玩家也可以借助其他道具解救）。

　　需求

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

• 選擇什么樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最恰當(dāng)？

• 可以悔一張牌

• 可以悔系列牌（即玩家把一個(gè)系列從下部區(qū)域的某一列移動(dòng)到另一列時(shí)）

• 可以連續(xù)多次悔牌

• 悔牌后對(duì)應(yīng)順序與位置不可改變

• 最多支持多少次連續(xù)悔牌最合適

方案

　　基于上述需要，我選擇了使用了STL庫(kù)的雙端隊(duì)列－－容器deque (double-ended queue)。我創(chuàng)建了兩個(gè)deque：一個(gè)是主要容器，另一個(gè)起輔助標(biāo)記作用。

    std::deque<UndoNode> UndoDeque;//main
    std::deque<int> AuxUndoDeque;//auxiliary

　　我們的悔牌機(jī)制具體描述如下：

　　目前的設(shè)計(jì)目標(biāo)是隊(duì)列中最多容納8項(xiàng)，但是這些入隊(duì)列的項(xiàng)可能有的是單項(xiàng)，有的是小系列（需要一起操作）。

    考慮到有的系列特別長(zhǎng)（例如從13點(diǎn)到5點(diǎn)的僅僅一個(gè)系列就包含９張牌），作進(jìn)一步簡(jiǎn)化處理，方案是：

　　如果有一個(gè)系列入隊(duì)列，則先清空隊(duì)列中所有內(nèi)容，再入隊(duì)列此系列。

    為此，我們?cè)O(shè)計(jì)另一個(gè)輔助隊(duì)列AuxUndoDeque，用于記憶撤消隊(duì)列中可能成組的項(xiàng)。

　　算法描述如下：

    i.PUSH當(dāng)前要入隊(duì)列的項(xiàng)（單或者系列）; 同時(shí)，PUSH到AuxUndoDeque中相應(yīng)的標(biāo)志int
    ii.如果當(dāng)前僅有一張撲克入隊(duì)列，而且如果隊(duì)列OK（<=8) ，那么情況簡(jiǎn)單；如果>8(此前隊(duì)列內(nèi)總數(shù)已為8)，則判斷如下：
    　a. if arr[0]是一個(gè)入隊(duì)列單項(xiàng)，彈出這個(gè)單項(xiàng)即可
    　b. arr[0..k]是一個(gè)小系列，則彈出這個(gè)系列。
    iii.如果當(dāng)前入隊(duì)列的是一個(gè)系列，則復(fù)雜些，因?yàn)榭赡苄枰獜年?duì)列尾彈出不止一組（多個(gè)單項(xiàng)和多個(gè)小系列）。
    　如果上述輔助隊(duì)列中對(duì)應(yīng)參數(shù)為－1，說(shuō)明要從尾部彈出一項(xiàng)；如果是N（>1的整數(shù)），說(shuō)明要從尾部彈出N項(xiàng)（小系列）。

　　提示：

　　１，無(wú)論主隊(duì)列是出隊(duì)操作（從頭部）還是入隊(duì)操作（從尾部），相應(yīng)地，其輔助隊(duì)列也要進(jìn)行相應(yīng)的出隊(duì)和入隊(duì)操作。

　　２，輔助隊(duì)列中存儲(chǔ)一個(gè)整數(shù)，當(dāng)－１時(shí)表示主隊(duì)列中加入的是一個(gè)單項(xiàng)，如果是N>1的一個(gè)整數(shù)，則此整數(shù)表示主隊(duì)列中加入的是一個(gè)長(zhǎng)度為N的系列。

補(bǔ)充－STL容器主要操作知識(shí)

deque雙向隊(duì)列是一種雙向開(kāi)口的連續(xù)線性空間，可以高效的在頭尾兩端插入和刪除元素，deque在接口上和vector非常相似，下面列出deque的常用成員函數(shù)：

頭文件：#include<deque>

函數(shù)構(gòu)造：

          deque<Elem> c     創(chuàng)建一個(gè)空的deque。

          deque<Elem> c1(c2)     復(fù)制一個(gè)deque。

          deque<Elem> c(n)     創(chuàng)建一個(gè)deque，含有n個(gè)數(shù)據(jù)，數(shù)據(jù)均已缺省構(gòu)造產(chǎn)生。

          deque<Elem> c(n, elem)    創(chuàng)建一個(gè)含有n個(gè)elem拷貝的deque

          deque<Elem> c(beg,end)     創(chuàng)建一個(gè)以[beg;end)區(qū)間的deque

          c.~deque<Elem>()     銷(xiāo)毀所有數(shù)據(jù)，釋放內(nèi)存

成員函數(shù)：

          c.assign(beg,end)    將[beg; end)區(qū)間中的數(shù)據(jù)賦值給c。

          c.assign(n,elem)    將n個(gè)elem的拷貝賦值給c。

          c. at(idx)     傳回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。

          c.back()     傳回最后一個(gè)數(shù)據(jù)，不檢查這個(gè)數(shù)據(jù)是否存在。

          c.begin()    傳回迭代器中的第一個(gè)數(shù)據(jù)。

          c.clear()     移除容器中所有數(shù)據(jù)。

          c.empty()    判斷容器是否為空。

          c.end()    指向迭代器中的最后一個(gè)數(shù)據(jù)地址。

         c.erase(pos)     刪除pos位置的數(shù)據(jù)，傳回下一個(gè)數(shù)據(jù)的位置。

         c.erase(beg,end)     刪除[beg,end)區(qū)間的數(shù)據(jù)，傳回下一個(gè)數(shù)據(jù)的位置。

         c.front()     傳回第一個(gè)數(shù)據(jù)。

         get_allocator    使用構(gòu)造函數(shù)返回一個(gè)拷貝。

         c.insert(pos,elem)     在pos位置插入一個(gè)elem拷貝，傳回新數(shù)據(jù)位置

         c.insert(pos,n,elem)     在pos位置插入>n個(gè)elem數(shù)據(jù)。無(wú)返回值

         c.insert(pos,beg,end)    在pos位置插入在[beg,end)區(qū)間的數(shù)據(jù)。無(wú)返回值

         c.max_size()     返回容器中最大數(shù)據(jù)的數(shù)量。

         c.pop_back()     刪除最后一個(gè)數(shù)據(jù)。

         c.pop_front()    刪除頭部數(shù)據(jù)。

         c.push_back(elem)    在尾部加入一個(gè)數(shù)據(jù)。

         c.push_front(elem)    在頭部插入一個(gè)數(shù)據(jù)。

         c.rbegin()    傳回一個(gè)逆向隊(duì)列的第一個(gè)數(shù)據(jù)。

         c.rend()    傳回一個(gè)逆向隊(duì)列的最后一個(gè)數(shù)據(jù)的下一個(gè)位置。

         c.resize(num)     重新指定隊(duì)列的長(zhǎng)度。

         c.size()    返回容器中實(shí)際數(shù)據(jù)的個(gè)數(shù)。

         c.swap(c2)   將c1和c2元素互換。

         swap(c1,c2)     將c1和c2元素互換。

特點(diǎn)：

1、支持隨機(jī)訪問(wèn)，即支持[]以及at()，但是性能沒(méi)有vector好。

2、支持兩端操作，push(pop)-back(front)，但性能不及l(fā)ist。

最佳使用情況：

1、需要在兩端插入和刪除元素。

2、無(wú)需引用容器內(nèi)的元素。

3、要求容器釋放不再使用的元素。