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

有效

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

技術領域

本發明涉及數據訪問技術領域，特別涉及一種隊列的訪問方法及裝置。

背景技術

在進行數據訪問技術的過程中，隊列作為一種數據結構，由于其FIFO(First Input First Output，先進先出)的特性，被應用于許多場合中，如算法的設計等。其中，在對隊列進行訪問時，為了提高資源利用率及程序運行的速度，多數情況下程序在邏輯意義上被分割為數個線程，采用多線程并發機制，通過多線程對隊列進行訪問。

相關技術中提供了一種隊列的訪問方法，在該方法中，當線程A需要訪問隊列時，會先對該隊列加鎖，線程A直到訪問隊列結束后，才會將鎖進行解除。按照上述訪問方式，線程A在訪問隊列的過程中，若又到來了一個新的線程B需要對隊列進行訪問，由于鎖并未解除，此時線程B不能對隊列進行訪問，也就不能對隊列中相關變量進行修改。

在實現本發明的過程中，發明人發現相關技術至少存在以下問題：

在使用加鎖的方法實現多個線程對隊列進行訪問時，一個線程訪問隊列，對該隊列加鎖，若另一個線程需要對隊列進行訪問，由于該隊列已經加鎖，此時該線程會由運行狀態變為等待狀態，并進行上下文切換。而進行上下文切換的過程需要占用的資源較多，且耗費時間較長。另外，占用隊列的線程若未及時解鎖，可能會造成其它需要訪問該隊列的線程等待較長時間，因此，通過加鎖的方法實現隊列的訪問時，效率不高。

發明內容

為了解決現有技術的問題，本發明實施例提供了一種隊列的訪問方法及裝置。所述技術方案如下：

一方面，提供了一種隊列的訪問方法，所述方法包括：

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

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

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

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

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

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

另一方面，提供了一種隊列的訪問裝置，所述裝置包括：

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

第一獲取模塊，用于獲取所述隊尾指針變量的值；

第一判斷模塊，用于判斷獲取到的值所指向的第一節點中包含的指針變量的值是否為空；

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

所述裝置還包括：

第二獲取模塊，用于獲取所述隊頭指針變量的值；

第二判斷模塊，用于判斷獲取到的值所指向的偽節點中包含的指針變量的值是否為空；