1、在計算機程式設計中經常使用佇列,一個典型的例子就是作業系統產生的作業佇列,如果作業系統使用的不是優先順序排程,那麼作業按照進入系統的順序進行處理。顯然,隨著作業的進入和離開系統,佇列逐漸右移。這意味著隊尾最終等於max_queque_size-1(最大佇列長度-1),說明佇列已滿。這就是“假溢位”現象。
2、此時,需要重新計算對頭(front)和隊尾(rear)指標,使其處在正確的位置上,而且移動的時間開銷很大,特別是當佇列中包含大量元素時。為了得到一種有效的儲存表示,引入了迴圈佇列,因此,迴圈佇列克服了“假溢位”的現象。
3、一般約定,迴圈佇列儲存的容量為max_queue_size-1,這是為了避免front和rear指向同一處,從而無法判斷隊滿還是隊空,而計算指標可使用%max_queue_size運算,避免指標越來越大。這樣,在入隊前,讓尾指標+1,若等於頭指標,則隊滿。出隊時,若頭指標等於尾指標,則隊空。
4、可以另設一個變數,每出隊一個元素對其-1,入隊一個元素對其+1,這樣也可以判斷隊滿和隊空。
1、在計算機程式設計中經常使用佇列,一個典型的例子就是作業系統產生的作業佇列,如果作業系統使用的不是優先順序排程,那麼作業按照進入系統的順序進行處理。顯然,隨著作業的進入和離開系統,佇列逐漸右移。這意味著隊尾最終等於max_queque_size-1(最大佇列長度-1),說明佇列已滿。這就是“假溢位”現象。
2、此時,需要重新計算對頭(front)和隊尾(rear)指標,使其處在正確的位置上,而且移動的時間開銷很大,特別是當佇列中包含大量元素時。為了得到一種有效的儲存表示,引入了迴圈佇列,因此,迴圈佇列克服了“假溢位”的現象。
3、一般約定,迴圈佇列儲存的容量為max_queue_size-1,這是為了避免front和rear指向同一處,從而無法判斷隊滿還是隊空,而計算指標可使用%max_queue_size運算,避免指標越來越大。這樣,在入隊前,讓尾指標+1,若等於頭指標,則隊滿。出隊時,若頭指標等於尾指標,則隊空。
4、可以另設一個變數,每出隊一個元素對其-1,入隊一個元素對其+1,這樣也可以判斷隊滿和隊空。