隊列(Queue)是一種運算受限的線性表插入在表的一端進行而刪除在表的另一端進行允許刪除的一端稱為隊頭(front)允許插入的一端稱為隊尾(rear) 隊列的操作原則是先進先出的又稱作FIFO表(First In First Out) 隊列也有順序存儲和鏈式存儲兩種存儲結構
隊列的基本運算有六種
·置空隊InitQueue(Q)
·判隊空QueueEmpty(Q)
·判隊滿QueueFull(Q)
·入隊EnQueue(Qx)
·出隊DeQueue(Q)
·取隊頭元素QueueFront(Q)
順序隊列的假上溢現象由於頭尾指針不斷前移超出向量空間這時整個向量空間及隊列是空的卻產生了上溢現象
為了克服假上溢現象引入循環向量的概念是把向量空間形成一個頭尾相接的環形這時隊列稱循環隊列
判定循環隊列是空還是滿方法有三種
·一種是另設一個布爾變量來判斷
·第二種是少用一個元素空間入隊時先測試((rear+)%m = front)? 滿空
·第三種就是用一個計數器記錄隊列中的元素的總數
隊列的鏈式存儲結構稱為鏈隊列一個鏈隊列就是一個操作受限的單鏈表為了便於在表尾進行插入(入隊)的操作在表尾增加一個尾指針一個鏈隊列就由一個頭指針和一個尾指針唯一地確定鏈隊列不存在隊滿和上溢的問題在鏈隊列的出隊算法中要注意當原隊中只有一個結點時出隊後要同進修改頭尾指針並使隊列變空
[] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22847.html