Növbə (proqramlaşdırma)

Növbə (ing. Queue) — proqramlaşdırmada verilənlər strukturudur və məlumatların müəyyən qaydada saxlanması və işlənməsi üçün istifadə olunur.^[1] Növbə, FIFO (ing. First In, First Out) prinsipi əsasında işləyir, yəni ilk daxil olan element ilk çıxır. Bu struktur adətən, məlumatların ardıcıl emalı tələb olunduğu hallarda istifadə olunur, məsələn, işlərin, proseslərin və ya sorğuların sıralanması üçün.

Növbə əməliyyatları

1. enqueue — yeni elementin növbəyə əlavə olunması. Bu əməliyyat zamanı element sıranın sonunda yerləşdirilir.^[2]
2. dequeue — növbədəki ilk elementin çıxarılması. Bu əməliyyat zamanı ilk daxil olan element növbədən çıxarılır.
3. front (və ya peek) – Növbənin ilk elementinə baxmaq (çıxarmadan).
4. isEmpty — növbənin boş olub-olmadığını yoxlayır.
5. isFull — (Statik növbələr üçün) növbənin tam dolu olub-olmadığını yoxlayır.

İstifadə sahələri

• Proseslərin idarə olunması — məsələn, əməliyyat sistemlərində proseslərin ardıcıl işlənməsi üçün.
• Verilənlərin stream emalı — real vaxt verilənlərin emalı və ya emalı gözləyən sorğuların idarə olunması.
• İnternet serverlərində sorğu idarəsi — gələn sorğuların düzgün ardıcıllıqla idarə olunması və cavablandırılması.^[3]

Növləri

• Sadə növbə — ənənəvi FIFO prinsipi ilə işləyir.
• Dairəvi növbə — boş yerin yenidən istifadəsi üçün dairəvi struktura malikdir.
• Prioritetli növbə — elementlər müəyyən prioritetə görə növbəyə əlavə edilir.
• İkili sonlu növbə (deque) — həm başlanğıcda, həm də sonunda əməliyyatların icra oluna biləcəyi növbədir.

Növbənin həyata keçirilməsi yolları

Massiv

Tipik olaraq, start növbənin başına, end isə növbəyə yeni element daxil olduqda doldurulacaq elementə işarə edir. Növbəyə element əlavə edərkən yeni növbə elementinə q[end] yazılır və sonu bir azaldılır. Əgər end-in dəyəri 1-dən kiçik olarsa, o zaman bir növ massivdən keçirilir və dəyişənin qiyməti n-ə bərabər olur. Elementin növbədən çıxarılması da eyni şəkildə həyata keçirilir:^[4] q[start] elementi növbədən çıxarıldıqdan sonra start dəyişəni 1 azalır. Belə alqoritmlərlə n-dən bir xana həmişə boş qalacaq (növbədən bəri n elementi boş elementdən ayırmaq mümkün deyil), bu, alqoritmlərin sadəliyi ilə kompensasiya olunur.

İstinadlar

1. "Queue (Java Platform SE 7)". Docs.oracle.com. 2014-03-26. 2018-03-09 tarixində arxivləşdirilib. İstifadə tarixi: 2014-05-22.
2. "Array (Ruby 3.1)". 2021-12-25. 2023-05-23 tarixində arxivləşdirilib. İstifadə tarixi: 2022-05-11.
3. Okasaki, Chris. "Purely Functional Data Structures" (PDF). 2023-12-07 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2024-10-25.
4. Hood, Robert; Melville, Robert. "Real-time queue operations in pure Lisp". Information Processing Letters. 13 (2). November 1981: 50–54. doi:10.1016/0020-0190(81)90030-2. hdl:1813/6273.

Ədəbiyyat

• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Dequeues, pp. 238–243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp. 200–204.
• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp. 386–390.
• Adam Drozdek. Data Structures and Algorithms in C++, Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp. 137–169.

Xarici keçidlər

• STL Quick Reference
• VBScript implementation of stack, queue, deque, and Red-Black Tree