拇指接龍游戲中的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、要求容器釋放不再使用的元素。