Queue, Deque və Circular Queue

Queue (növbə) — FIFO (First In, First Out) prinsipi ilə işləyən kolleksiyadır: birinci girən birinci çıxır. Zehni model — kassa növbəsi.

Əsas əməliyyatlar, hamısı O(1) olmalıdır:

• enqueue(x) — sona element əlavə et
• dequeue() — əvvəldən element çıxar və qaytar
• peek()/front() — əvvəldəkinə bax
• isEmpty(), size

Stack ilə fərqi yalnız hansı ucdan çıxarıldığındadır: stack-də əlavə və çıxarma eyni ucdan (LIFO), queue-da isə əks uclardan (FIFO). Bu kiçik fərq alqoritmlərin xarakterini tamamilə dəyişir — məsələn, eyni gəzinti kodunda stack-i queue ilə əvəz etsən, DFS BFS-ə çevrilir.

Sadə massiv niyə pis növbədir. Ən çox rast gəlinən səhv array.push() + array.shift() cütlüyüdür.

push amortized O(1)-dir, amma shift `O(n)`: birinci element silinəndə qalan bütün elementlər bir addım sola sürüşməlidir, çünki massiv ardıcıl yaddaşdadır. Nəticədə n elementi növbədən keçirmək O(n²) olur — 100 000 elementlik növbədə bu, açıq-aşkar görünən yavaşlamadır.

İki düzgün həll var:

• Linked list — head-dən silmək, tail-ə əlavə etmək; hər ikisi O(1), sürüşdürmə yoxdur
• Circular buffer (dairəvi bufer) — sabit ölçülü massiv üzərində head və tail indeksləri saxlanılır; element silinəndə sürüşdürmə əvəzinə sadəcə head irəli sürüşür və massivin sonuna çatanda başa qayıdır ((head + 1) % capacity). Boş yerlər yenidən istifadə olunur, cache lokallığı isə massivdəki kimi qalır.

Müasir kitabxanaların ArrayDeque tipi məhz circular buffer üzərində qurulub — buna görə praktikada növbə üçün ən yaxşı default seçim odur.

Deque (double-ended queue, "dek" kimi oxunur) — hər iki ucda O(1) əlavə və silmə imkanı verən strukturdur. Bir deque eyni zamanda həm stack, həm queue kimi işlədilə bilər, ona görə müasir kitabxanalarda ayrıca Stack sinfi əvəzinə ArrayDeque təklif olunur.

Circular queue isə sabit tutumlu variantdır: bufer dolanda ya yeni element rədd edilir, ya da ən köhnə element üstünə yazılır (ring buffer). Bu davranış qəsdən seçilir — yaddaş sərfinə zəmanət verir.

Real istifadə sahələri:

• BFS — qraf və ağacda səviyyə-səviyyə gəzinti; ən qısa yolu tapmaq. Queue olmadan BFS yazmaq mümkün deyil.
• Task queue / job queue — arxa fon işləri, mesaj brokerləri (RabbitMQ, Kafka mahiyyətcə paylanmış növbələrdir), printer növbəsi
• Rate limiting — sliding window alqoritmində son n saniyədəki sorğuların vaxt möhürləri deque-də saxlanılır: yeni sorğu sona əlavə olunur, pəncərədən çıxmış köhnə vaxtlar əvvəldən silinir
• Producer-consumer — thread-lər arasında bufer
• Sliding window maximum — monotonic deque ilə O(n) həll
• Audio/video buferləri, sensor datası, dairəvi loglar — sabit ölçülü ring buffer