[發明專利]隊列的訪問方法及裝置

有效

• 申請號: 201410033780.X
• 申請日: 2014-01-23
• 公開（公告）號: CN103793267B
• 公開（公告）日: 2017-07-21
• 發明（設計）人: 賀輝超
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 北京三高永信知識產權代理有限責任公司11138
• 代理人: 羅振安

1.一種隊列訪問方法，其特征在于，所述隊列中至少包含一個第一節點、隊尾指針變量和隊頭指針變量，所述隊尾指針變量的值用于指向所述隊列的尾節點，所述尾節點為第一節點，所述隊頭指針變量的值用于指向偽節點，所述偽節點在所述隊列之外，所述隊列包含的每個第一節點中至少包含一個指針變量，所述指針變量的值用于指向當前所在節點所連接的下一個節點，尾節點包含的指針變量的值為空，所述方法包括：

創建待加入所述隊列的第二節點，所述第二節點包括值為空的指針變量；

獲取所述隊尾指針變量的值，并判斷獲取到的值所指向的第一節點中包含的指針變量的值是否為空；

若獲取到的值所指向的第一節點中包含的指針變量的值為非空，則確定所述隊尾指針變量的值被更新，獲取所述隊尾指針變量更新后的值，直至判斷所述隊尾指針變量更新后的值所指向的第一節點中包含的指針變量的值為空，將所述第二節點加入所述隊列，并將獲取到的值所指向的第一節點包含的指針變量的值指向所述第二節點；

獲取所述隊頭指針變量的值，并判斷獲取到的值所指向的偽節點中包含的指針變量的值是否為空；

若所述偽節點中包含的指針變量的值為非空，則在兩個不同的時間點上分別獲取所述隊頭指針變量的值，并判斷兩次獲取到的所述隊頭指針變量的值是否相同；若兩次獲取到的所述隊頭指針變量的值不同，則確定所述偽節點被更新，重新在兩個不同的時間點上分別獲取所述隊頭指針變量的值，直至判斷兩次獲取到的所述隊頭指針變量的值相同，釋放被更新的偽節點，并將所述被更新的偽節點中包含的指針變量的值所指向的節點作為新的偽節點，所述新的偽節點不屬于所述隊列；或者，

若所述偽節點中包含的指針變量的值為非空，則在兩個不同的時間點上分別獲取所述偽節點中包含的指針變量的值，并判斷兩次獲取到的所述偽節點中包含的指針變量的值是否相同；若兩次獲取到的所述偽節點中包含的指針變量的值不同，則確定所述偽節點的下一個節點被更新，重新在兩個不同的時間點上分別獲取所述偽節點中包含的指針變量的值，直至判斷兩次獲取到的所述偽節點中包含的指針變量的值相同，刪除所述偽節點中包含的指針變量的值所指向的節點。

2.根據權利要求1所述的方法，其特征在于，所述將所述第二節點加入所述隊列，并將獲取到的值所指向的第一節點包含的指針變量的值指向所述第二節點之后，還包括：

將所述隊尾指針變量的值更新為指向所述第二節點的值。

3.根據權利要求1所述的方法，其特征在于，所述將所述偽節點中包含的指針變量的值所指向的節點更新為新的偽節點之后，還包括：

將所述隊頭指針變量的值更新為指向所述新的偽節點的值。

4.根據權利要求1所述的方法，其特征在于，所述刪除所述偽節點中包含的指針變量的值所指向的節點之后，還包括：

將所述偽節點中包含的指針變量的值指向被刪除的節點的下一個節點。

5.根據權利要求1所述的方法，其特征在于，所述判斷獲取到的偽節點中包含的指針變量的值是否為空之后，還包括：

若所述隊頭指針變量的值所指向的偽節點中包含的指針變量的值為空，則返回刪除節點失敗的提示。