引子

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

需求

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

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

• 可以悔一張牌

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

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

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

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

方案

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

    std::deque UndoDeque;//main
    std::deque AuxUndoDeque;//auxiliary

我們的悔牌機制具體描述如下：

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

   考慮到有的系列特別長（例如從13點到5點的僅僅一個系列就包含９張牌），作進一步簡化處理，方案是：

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

   為此，我們設(shè)計另一個輔助隊列AuxUndoDeque，用于記憶撤消隊列中可能成組的項。

算法描述如下：

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

提示：

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

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

補充－STL容器主要操作知識

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

頭文件：#include

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

     deque c    創(chuàng)建一個空的deque。

      deque c1(c2)   復(fù)制一個deque。

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

      deque c(n, elem)   創(chuàng)建一個含有n個elem拷貝的deque

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

      c.~deque()   銷毀所有數(shù)據(jù)，釋放內(nèi)存

成員函數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     c.resize(num)   重新指定隊列的長度。

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

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

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

特點：

1、支持隨機訪問，即支持[]以及at()，但是性能沒有vector好。

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

最佳使用情況：

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

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。