假溢出

系統作為佇列用的存儲區還沒有滿,但佇列卻發生了溢出,我們把這種現象稱為"假溢出"。

舉例

設順序存儲佇列用一維數組q[m]表示，其中m為佇列中元素個數，佇列中元素在向量中的下標從0到m-1。

設隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當front等於-1時隊空，rear等於m-1時為隊滿。由於佇列的性質（“刪除”在隊頭而“插入”在隊尾），所以當隊尾指針rear等於m-1時，若front不等於-1，則佇列中仍有空閒單元，所以佇列並不是真滿。這時若再有入隊操作，會造成假“溢出”。

解決辦法

一是將佇列元素向前“平移”（占用0至rear-front-1）；

二是將佇列看成首尾相連，即循環佇列（0..m-1）。

在循環佇列下，仍定義front=rear時為隊空，而判斷隊滿則用兩種辦法，一是用“犧牲一個單元”，即rear+1=front（準確記是（rear+1）%m=front，m是佇列容量）時為隊滿。

另一種解法是“設標記”方法，如設標記tag，tag等於0情況下，若刪除時導致front=rear為隊空；tag=1情況下，若因插入導致front=rear則為隊滿。