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ı
[redaktə | mənbəni redaktə et]- enqueue — yeni elementin növbəyə əlavə olunması. Bu əməliyyat zamanı element sıranın sonunda yerləşdirilir.[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.
- front (və ya peek) – Növbənin ilk elementinə baxmaq (çıxarmadan).
- isEmpty — növbənin boş olub-olmadığını yoxlayır.
- isFull — (Statik növbələr üçün) növbənin tam dolu olub-olmadığını yoxlayır.
İstifadə sahələri
[redaktə | mənbəni redaktə et]- 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
[redaktə | mənbəni redaktə et]- 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ı
[redaktə | mənbəni redaktə et]Massiv
[redaktə | mənbəni redaktə et]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
[redaktə | mənbəni redaktə et]- ↑ "Queue (Java Platform SE 7)". Docs.oracle.com. 2014-03-26. 2018-03-09 tarixində arxivləşdirilib. İstifadə tarixi: 2014-05-22.
- ↑ "Array (Ruby 3.1)". 2021-12-25. 2023-05-23 tarixində arxivləşdirilib. İstifadə tarixi: 2022-05-11.
- ↑ Okasaki, Chris. "Purely Functional Data Structures" (PDF). 2023-12-07 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2024-10-25.
- ↑ 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
[redaktə | mənbəni redaktə et]- 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.