18. Dynamic — dinamik ma'lumotlar strukturalari

Barcha masalalarda bog'langan ro'yxat (linked list), stek yoki navbat kabi dinamik strukturalar ishlatiladi. Tugunni Python klassi sifatida yozing (masalan class Node: — value va next maydonlari bilan); bo'sh havola None bilan ifodalanadi. Masalada boshqacha aytilmasa, tayyor list yoki collections.deque dan emas, o'zingiz yozgan tugunlardan foydalaning.

Bog'langan ro'yxat — asosiy amallar

1. N ta butun sondan iborat bog'langan ro'yxat yarating (oxiriga qo'shish orqali) va uni ekranga chiqaring.
Misol: N = 4: 5 3 8 1 → 5 → 3 → 8 → 1

2. Bog'langan ro'yxat berilgan. Uning elementlari sonini (uzunligini) aniqlang.
Misol: 4 → 7 → 1 → 3

3. Bog'langan ro'yxat berilgan. Uning barcha elementlari yig'indisini toping.
Misol: 4 → 7 → 1 → 12

4. Bog'langan ro'yxat berilgan. Ro'yxat boshiga yangi element qo'shing.
Misol: 2 → 3, X = 9 → 9 → 2 → 3

5. Bog'langan ro'yxat va X soni berilgan. X ni ro'yxatdan qidirib, bor-yo'qligini aniqlang.
Misol: 4 → 7 → 1, X = 7 → bor; X = 5 → yo'q

6. Bog'langan ro'yxat va X soni berilgan. X qiymatiga ega birinchi elementni ro'yxatdan o'chiring.
Misol: 4 → 7 → 1 → 7, X = 7 → 4 → 1 → 7

7. Bog'langan ro'yxat berilgan. Uni teskari tartibga o'tkazing (qayta bog'lash orqali, yangi ro'yxat yaratmasdan).
Misol: 1 → 2 → 3 → 3 → 2 → 1

8. Bog'langan ro'yxat berilgan. Uning eng katta va eng kichik elementini toping.
Misol: 4 → 9 → 1 → 6 → eng katta 9, eng kichik 1

9. Bog'langan ro'yxat berilgan. Ro'yxatning o'rtasidagi elementni (bir marta o'tish bilan, ikkita ko'rsatkich — sekin va tez — usulida) toping.
Misol: 1 → 2 → 3 → 4 → 5 → 3; 1 → 2 → 3 → 4 → 3

Murakkabroq ro'yxat amallari

10. Bog'langan ro'yxat berilgan. Undagi juft qiymatli elementlarni o'chiring.
Misol: 1 → 2 → 3 → 4 → 5 → 1 → 3 → 5

11. Ikkita saralangan bog'langan ro'yxat berilgan. Ularni birlashtirib, yagona saralangan ro'yxat hosil qiling.
Misol: 1 → 4 → 9 va 2 → 3 → 10 → 1 → 2 → 3 → 4 → 9 → 10

12. Bog'langan ro'yxat berilgan. Undagi takrorlanuvchi elementlarni olib tashlang (har bir qiymat bir marta qolsin).
Misol: 1 → 2 → 2 → 3 → 1 → 1 → 2 → 3

13. Bog'langan ro'yxat berilgan. Uni ikkita (juft va toq indeksli elementlar) ro'yxatga ajrating.
Misol: 10 → 11 → 12 → 13 → 14 → toq o'rinlar 10 → 12 → 14, juft o'rinlar 11 → 13

14. Bog'langan ro'yxat berilgan. Ro'yxatda halqa (sikl) borligini (bir tugun o'ziga qaytib bog'lanishini) aniqlang.
Misol: 1 → 2 → 3, oxirgi tugun 2-tugunga bog'langan → halqa bor; oddiy 1 → 2 → 3 → halqa yo'q

15. Bog'langan ro'yxat va K soni berilgan. Ro'yxatni K tadan elementli bloklarga bo'lib, har bir blokni teskari tartibga o'tkazing.
Misol: 1 → 2 → 3 → 4 → 5, K = 2 → 2 → 1 → 4 → 3 → 5

16. Bog'langan ro'yxat berilgan. N-o'rindan elementni ro'yxatdan o'chiring.
Misol: 10 → 20 → 30 → 40, N = 3 → 10 → 20 → 40

17. Bog'langan ro'yxat berilgan. Berilgan pozitsiyaga yangi element qo'shing.
Misol: 10 → 20 → 30, o'rin 2, X = 15 → 10 → 15 → 20 → 30

18. Bog'langan ro'yxat berilgan. Uni saralang (istalgan saralash usuli bilan).
Misol: 4 → 1 → 3 → 1 → 3 → 4

19. Bog'langan ro'yxat berilgan. Palindrom (ro'yxat qiymatlari palindrom tashkil qilishi) ekanligini tekshiring.
Misol: 1 → 2 → 1 → ha; 1 → 2 → 3 → yo'q

20. Ikkita bir tomonlama bog'langan ro'yxat biror tugundan boshlab umumiy dumga ega. Ular kesishadigan birinchi tugunni toping.
Misol: A: 1 → 2 → 8 → 9, B: 5 → 8 → 9 (8 → 9 umumiy) → 8

21. Bog'langan ro'yxat va K soni berilgan. Ro'yxatni bir marta aylanib chiqib, oxiridan K-elementni toping.
Misol: 1 → 2 → 3 → 4 → 5, K = 2 → 4

22. Bog'langan ro'yxat va X soni berilgan. Ro'yxatni ikki qismga ajrating: avval X dan kichik elementlar, so'ng qolganlari (har bir qismda nisbiy tartib saqlansin).
Misol: 3 → 8 → 1 → 5 → 2, X = 4 → 3 → 1 → 2 → 8 → 5

23. Ikkita bog'langan ro'yxat berilgan. Ikkalasida ham uchraydigan elementlardan iborat yangi ro'yxat hosil qiling (takrorlanishlarsiz).
Misol: 1 → 2 → 3 → 4 va 3 → 4 → 5 → 3 → 3 → 4

24. Bog'langan ro'yxat berilgan. Uni birlashtirish orqali saralash (merge sort) usulida saralang.
Misol: 4 → 2 → 7 → 1 → 1 → 2 → 4 → 7

Stek (stack)

25. Stek tuzilmasini yarating. Unga N ta son qo'shib (push), so'ng ularni olib (pop) teskari tartibda chiqaring.
Misol: N = 3: 1 2 3 → 3 2 1

26. Stekni bog'langan ro'yxat asosida amalga oshiring: push (qo'shish), pop (olish), peek (tepadagi elementni ko'rish) va is_empty (bo'shligini tekshirish) amallarini yozing.
Misol: push(1), push(2), push(3), peek() → 3, pop() → 3, is_empty() → False

27. Stek berilgan. Undagi elementlar soni va yig'indisini toping; stek oxirida dastlabki holatiga qaytarilsin (yordamchi stekdan foydalaning).
Misol: stek [1 2 3 4] (tepasi o'ngda) → soni 4, yig'indi 10, stek [1 2 3 4] holicha qoladi

28. Ikkita stek berilgan. Birinchi stekning barcha elementlarini ikkinchisiga ko'chiring: a) tartibi teskari bo'ladigan qilib; b) tartibi saqlanadigan qilib.
Misol: [1 2 3] → a) [3 2 1]; b) [1 2 3]

29. Stek berilgan. Undagi barcha manfiy elementlarni olib tashlang; qolgan elementlarning tartibi saqlansin.
Misol: [3 -1 4 -5 2] → [3 4 2]

30. Infiks ko'rinishdagi arifmetik ifodani (masalan "(3+4)*2") stek yordamida postfiks ko'rinishga ("3 4 + 2 *") o'tkazing.
Misol: (3+4)*2 → 3 4 + 2 *; 3+4*2 → 3 4 2 * +

31. Stek yordamida berilgan sonni ikkilik (binar) sanoq sistemasiga o'tkazing.
Misol: 13 → 1101

32. Postfiks (teskari polish) ifodani stek yordamida hisoblang (masalan "3 4 + 2 *").
Misol: 3 4 + 2 * → 14

33. Ikkita stek yordamida navbat (queue) ni amalga oshiring: element qo'shish va olish amallarini yozing.
Misol: push(1), push(2), push(3), dequeue() → 1, dequeue() → 2

34. Satrda uch xil qavslar — (), [], {} — berilgan. Stek yordamida qavslar to'g'ri joylashganligini tekshiring (masalan «([]{})» to'g'ri, «([)]» noto'g'ri).
Misol: ([]{}) → True; ([)] → False

35. Oddiy stek amallaridan tashqari, joriy eng kichik elementni ham darhol (sikl ishlatmasdan) qaytaradigan stekni amalga oshiring (ikkinchi yordamchi stekdan foydalaning).
Misol: push(5), push(3), push(7), push(2) → eng kichik 5, 3, 3, 2; pop() dan keyin → 3

36. Satrda <teg> va </teg> ko'rinishidagi teglar berilgan. Stek yordamida teglarning to'g'ri ochilib-yopilganligini tekshiring.
Misol: <a><b></b></a> → True; <a><b></a></b> → False

37. N o'lchamli massiv berilgan. Stek yordamida har bir element uchun undan chapda joylashgan eng yaqin kichikroq elementni toping (bunday element bo'lmasa, −1).
Misol: [4 8 5 2 9] → [-1 4 4 -1 2]

Navbat (queue)

38. Navbat tuzilmasini yarating. Unga N ta son qo'shib (enqueue), so'ng ularni olib (dequeue) tartib bo'yicha chiqaring.
Misol: N = 3: 1 2 3 → 1 2 3

39. Navbatni bog'langan ro'yxat asosida bosh va dum ko'rsatkichlari yordamida amalga oshiring: enqueue, dequeue va is_empty amallarini yozing.
Misol: enqueue(1), enqueue(2), dequeue() → 1, is_empty() → False

40. Ikkita navbat berilgan. Ularning elementlarini navbatma-navbat olib (birinchisidan, ikkinchisidan, …), uchinchi navbat hosil qiling.
Misol: [1 2 3] va [10 20] → [1 10 2 20 3]

41. Navbat berilgan. Stek yordamida navbat elementlari tartibini teskari qiling.
Misol: [1 2 3] → [3 2 1]

42. Doiraviy navbat (circular queue) ni massiv asosida amalga oshiring: to'lganda eski elementni yangi bilan almashtiring.
Misol: sig'im 3: enqueue 1 2 3 4 → [2 3 4]

43. 0 (yo'l) va 1 (devor) lardan iborat N×M o'lchamli maydon berilgan. Navbat yordamida kenglik bo'yicha qidiruv (BFS) usulida boshlang'ich katakdan chiqish katagigacha bo'lgan eng qisqa yo'l uzunligini toping.
Misol: 0 0 1 / 1 0 1 / 1 0 0, boshlang'ich (0, 0), chiqish (2, 2) → 4

44. Iosif masalasi: N kishi aylana bo'ylab turibdi. Birinchisidan boshlab sanaganda har K-kishi aylanadan chiqadi. Navbat yordamida kishilarning chiqish tartibini va oxirida qolgan kishini toping.
Misol: N = 5, K = 2 → chiqish tartibi 2 4 1 5, qolgan 3

45. Ustuvorlikli navbatni ustuvorlik bo'yicha saralangan bog'langan ro'yxat asosida amalga oshiring: element qo'shish (ustuvorligi bilan) va eng yuqori ustuvorlikli elementni olish amallarini yozing.
Misol: (A, 2), (B, 5), (C, 1) → olish tartibi B, A, C

46. Navbat berilgan. Undagi eng katta elementni topib, uni navbat boshiga ko'chiring (qolgan elementlar tartibi saqlansin).
Misol: [3 9 4 1] → [9 3 4 1]

Ikki tomonlama bog'langan ro'yxat

47. Ikki tomonlama bog'langan ro'yxat yarating va uni boshidan oxirigacha hamda oxiridan boshigacha chiqaring.
Misol: 1 ⇄ 2 ⇄ 3 → oldinga 1 2 3, orqaga 3 2 1

48. Ikki tomonlama bog'langan ro'yxat va undagi biror tugun berilgan. Shu tugundan oldin yangi element qo'shing.
Misol: 1 ⇄ 3, tugun 3, X = 2 → 1 ⇄ 2 ⇄ 3

49. Ikki tomonlama bog'langan ro'yxat va undagi biror tugun berilgan. Shu tugundan keyin yangi element qo'shing.
Misol: 1 ⇄ 3, tugun 1, X = 2 → 1 ⇄ 2 ⇄ 3

50. Ikki tomonlama bog'langan ro'yxat va undagi biror tugun berilgan. Shu tugunni ro'yxatdan o'chiring.
Misol: 1 ⇄ 2 ⇄ 3, tugun 2 → 1 ⇄ 3

51. Ikki tomonlama bog'langan ro'yxat berilgan. Har bir tugunning oldingi va keyingi ko'rsatkichlarini almashtirib, ro'yxatni teskari tartibga o'tkazing.
Misol: 1 ⇄ 2 ⇄ 3 → 3 ⇄ 2 ⇄ 1

52. Ikki tomonlama bog'langan ro'yxat berilgan. Uning birinchi va oxirgi tugunlarini (qiymatlarini emas, tugunlarning o'zini qayta bog'lab) o'rin almashtiring.
Misol: 1 ⇄ 2 ⇄ 3 ⇄ 4 → 4 ⇄ 2 ⇄ 3 ⇄ 1

53. Ikki tomonlama bog'langan ro'yxat berilgan. Ikki uchidan bir vaqtda o'rtaga qarab harakatlanib, uning o'rta elementini toping.
Misol: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 → 3

54. O'sish tartibida saralangan ikki tomonlama bog'langan ro'yxat va X soni berilgan. X ni saralanganlik saqlanadigan o'ringa qo'shing.
Misol: 1 ⇄ 3 ⇄ 5, X = 4 → 1 ⇄ 3 ⇄ 4 ⇄ 5

55. Ikki tomonlama bog'langan ro'yxat berilgan. Juft qiymatli barcha tugunlarni ro'yxat oxiriga ko'chiring (nisbiy tartib saqlansin).
Misol: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 → 1 ⇄ 3 ⇄ 5 ⇄ 2 ⇄ 4

56. Ikki tomonlama bog'langan ro'yxat berilgan. Uning ikki uchidan harakatlanib, qiymatlar palindrom tashkil qilishini tekshiring.
Misol: 1 ⇄ 2 ⇄ 1 → ha; 1 ⇄ 2 ⇄ 3 → yo'q

57. Ikki tomonlama bog'langan ro'yxat berilgan. Uni qo'yish orqali saralash (insertion sort) usulida saralang.
Misol: 4 ⇄ 2 ⇄ 3 ⇄ 1 → 1 ⇄ 2 ⇄ 3 ⇄ 4

Dek (ikki uchli navbat)

58. Dekni ikki tomonlama bog'langan ro'yxat asosida amalga oshiring: push_front, push_back, pop_front va pop_back amallarini yozing.
Misol: push_back(1), push_back(2), push_front(0) → [0 1 2]; pop_front() → 0; pop_back() → 2

59. S satri berilgan. Dek yordamida satr palindrom ekanligini tekshiring.
Misol: "level" → True; "salom" → False

60. N o'lchamli massiv va K berilgan. Dek yordamida uzunligi K bo'lgan har bir ketma-ket oynadagi eng katta elementni toping.
Misol: [1 3 -1 -3 5 3 6 7], K = 3 → [3 3 5 5 6 7]

61. Dek va K soni berilgan. Dekni K pozitsiyaga o'ngga aylantiring (oxirgi elementni boshiga o'tkazish amalini K marta bajarib).
Misol: [1 2 3 4 5], K = 2 → [4 5 1 2 3]

Halqali ro'yxat

62. Halqali bir tomonlama bog'langan ro'yxat (oxirgi tugun birinchisiga bog'langan) yarating va uning barcha elementlarini bir marta aylanib chiqib chiqaring.
Misol: 1 → 2 → 3 → (1) → 1 2 3

63. Juft sondagi elementlardan iborat halqali ro'yxat berilgan. Uni teng uzunlikdagi ikkita halqali ro'yxatga bo'ling.
Misol: 1 → 2 → 3 → 4 → 1 → 2 → (1) va 3 → 4 → (3)

64. O'sish tartibida saralangan halqali ro'yxat (eng kichik elementga ko'rsatkich bilan) va X soni berilgan. X ni saralanganlik saqlanadigan o'ringa qo'shing.
Misol: 1 → 3 → 5 → (1), X = 4 → 1 → 3 → 4 → 5 → (1)

65. Halqali ikki tomonlama ro'yxat va K soni berilgan. Joriy tugundan K qadam o'ngga, so'ng K qadam chapga harakatlanib, har bir to'xtagan tugun qiymatini chiqaring.
Misol: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 (halqa), joriy tugun 1, K = 2 → 2 3 2 1

66. Chiziqli bog'langan ro'yxat berilgan. Uni halqali ro'yxatga aylantiring, so'ng yana chiziqli ro'yxatga qaytaring.
Misol: 1 → 2 → 3 → 1 → 2 → 3 → (1) → yana 1 → 2 → 3

67. Halqali ro'yxatning faqat bitta tuguniga ko'rsatkich berilgan. Ro'yxat uzunligini toping.
Misol: a → b → c → (a), tugun b → 3

Amaliy masalalar

68. Talabalar ro'yxati bog'langan ro'yxat sifatida saqlangan (ism, baho). Eng yuqori baholi talabani toping va uni ro'yxat boshiga ko'chiring.
Misol: Ali 85 → Vali 92 → Sevara 78 → Vali 92 → Ali 85 → Sevara 78

69. Navbat (masalan, kassaga navbat) bog'langan ro'yxat sifatida modellashtirilgan. N kishi navbatga qo'shiladi va K kishi xizmat ko'rsatilib chiqariladi — qolgan navbatni chiqaring.
Misol: N = 5 (1 … 5), K = 2 → 3 → 4 → 5

70. Ikki kassaning navbati modellashtirilgan. Har bir yangi mijoz qisqaroq navbatga turadi; har bir kassa har qadamda bittadan mijozga xizmat ko'rsatadi. Amallar ketma-ketligi (kelish yoki xizmat) berilganda har bir qadamdan keyingi navbatlar holatini chiqaring.
Misol: kelish A, kelish B, kelish C, xizmat → K1: [A], K2: []; K1: [A], K2: [B]; K1: [A C], K2: [B]; K1: [C], K2: [] (teng bo'lsa 1-kassa)

71. Printer navbati: vazifalar (nomi, sahifalar soni) navbatda turibdi, printer daqiqada 10 sahifa chiqaradi. Har bir vazifa qachon tugashini va jami vaqtni toping.
Misol: hujjat 25, rasm 10, jadval 40 sahifa → tugash vaqtlari 2.5, 3.5, 7.5 daqiqa; jami 7.5 daqiqa

72. Ko'phad bog'langan ro'yxat ko'rinishida berilgan: har bir tugunda (daraja, koeffitsient), darajalar kamayish tartibida. Ikki ko'phad yig'indisini xuddi shunday ro'yxat ko'rinishida toping.
Misol: 3x² + 2x + 1 va x² + 5 → (2, 3) (1, 2) (0, 1) + (2, 1) (0, 5) = (2, 4) (1, 2) (0, 6)

73. Ko'phadlar bog'langan ro'yxat ko'rinishida berilgan. Ikki ko'phad ko'paytmasini toping (o'xshash hadlar birlashtirilsin).
Misol: (x + 1) va (x − 1) → (1, 1) (0, 1) · (1, 1) (0, -1) = (2, 1) (0, -1)

74. Bog'langan ro'yxat ko'rinishidagi ko'phad va x soni berilgan. Ko'phadning x nuqtadagi qiymatini hisoblang.
Misol: (2, 3) (1, 2) (0, 1), x = 2 → 17

75. Ikkita katta natural sonning raqamlari bog'langan ro'yxatlarda (kichik xonadan boshlab) saqlangan. Ularning yig'indisini xuddi shunday ro'yxat ko'rinishida toping.
Misol: 342 + 465: 2 → 4 → 3 va 5 → 6 → 4 → 7 → 0 → 8 (ya'ni 807)

76. Siyrak matritsa nolga teng bo'lmagan elementlar ro'yxati — (qator, ustun, qiymat) tugunlari ko'rinishida saqlangan. Ikki siyrak matritsaning yig'indisini xuddi shunday ro'yxat ko'rinishida toping.
Misol: A: (0, 0, 1), (1, 1, 2); B: (0, 0, 3), (0, 1, 4) → (0, 0, 4), (0, 1, 4), (1, 1, 2)

77. Matn muharririning «bekor qilish» (undo) funksiyasini stek yordamida modellashtiring: «qo'shish X» va «o'chirish» amallari matnni o'zgartiradi, «undo» esa oxirgi amalni bekor qiladi.
Misol: qo'shish a, qo'shish b, o'chirish, undo → matn: a, ab, a, ab

78. Brauzer tarixini ikkita stek yordamida modellashtiring: sahifaga o'tish, «orqaga» va «oldinga» amallarini bajaring va har bir amaldan keyin joriy sahifani chiqaring.
Misol: a.uz, b.uz, c.uz, orqaga, orqaga, oldinga → a.uz, b.uz, c.uz, b.uz, a.uz, b.uz

79. Sig'imi K bo'lgan LRU kesh (eng uzoq ishlatilmagan element chiqariladi) ni ikki tomonlama bog'langan ro'yxat yordamida amalga oshiring: get va put amallarini yozing.
Misol: K = 2: put(1, A), put(2, B), get(1) → A, put(3, C) (2 chiqariladi), get(2) → -1

80. Talabalar ro'yxati (ism, guruh) bog'langan ro'yxat ko'rinishida berilgan. Uni har bir guruh uchun alohida ro'yxatlarga ajrating (ro'yxatlar ro'yxati hosil bo'lsin).
Misol: Ali G1 → Vali G2 → Sevara G1 → G1: Ali → Sevara, G2: Vali