Növbə "ilk gələn ilk çıxır" (FIFO) qaydasıdır: element sona əlavə olunur, əvvəldən çıxarılır. Sadə görünür, amma sadəlövh reallaşdırma gizli O(n) ödəniş edir. Bu dərsdə siyahı, əlaqəli siyahı və dairəvi bufer üzərində üç düzgün reallaşdırma quracağıq.
Əməliyyatlar
Növbə ADT-nin əsas əməliyyatları: enqueue(x), dequeue(), peek(), is_empty(). Məqsəd hər əməliyyatı O(1)-də yerinə yetirməkdir. Stekdən fərqli olaraq, əlavə və çıxarma əks uclarda baş verir, ona görə siyahının yalnız bir ucu kifayət etmir.
Niyə list.pop(0) pisdir
Python-un list-i massivdir (massiv yaddaşı). İlk elementi çıxaranda qalan n - 1 element bir xana sola sürüşür. Aşağıda taymersiz, sürüşmələri əllə sayan model var; n dəfə pop(0) cəmi O(n²) verir. Daxili əməliyyatların qiyməti üçün bu cədvələ baxın.
def pop_front_moves(items):
moves = 0
for i in range(1, len(items)):
items[i - 1] = items[i]
moves += 1
items.pop()
return moves
for n in (10, 100, 1000):
print(n, pop_front_moves(list(range(n))))10 9
100 99
1000 999