Expand description
§Ma’lumotlar strukturalari (Data Structures)
Darslik: 05-data-structures/
Algoritm — bu retsept, ma’lumotlar strukturasi — idish. To’g’ri idishni tanlash ko’pincha algoritmni tanlashdan muhimroq.
| Struktura | Qo’shish | O’chirish | Qidirish | Tartib | Qachon kerak |
|---|---|---|---|---|---|
Vec<T> (massiv) | O(1)* oxiriga | O(n) | O(n) / O(log n)† | Bor | Deyarli har doim |
Stack | O(1) | O(1) | O(n) | LIFO | Orqaga qaytish, qavslar, DFS |
Queue | O(1) | O(1) | O(n) | FIFO | Navbat, BFS |
MinHeap | O(log n) | O(log n) | O(1) min | Qisman | Prioritet, Dijkstra |
HashTable | O(1) o’rt. | O(1) o’rt. | O(1) o’rt. | Yo’q | Kalit → qiymat |
DisjointSet | — | — | ~O(1) | — | Guruhlar, Kruskal |
* amortizatsiyalangan; † tartiblangan bo’lsa binary search bilan.
Amalda:
Vec,VecDeque,BinaryHeap,HashMap,BTreeMap— standart kutubxonadagi tayyor va optimallashtirilgan variantlardan foydalaning. Bu yerdagi implementatsiyalar ichida nima borligini ko’rsatish uchun.
Structs§
- Disjoint
Set - Kesishmaydigan to’plamlar strukturasi: elementlarni guruhlarga birlashtiradi va “bu ikkovi bir guruhdami?” savoliga deyarli O(1) da javob beradi.
- Hash
Table - Zanjirlash (separate chaining) usulidagi xesh-jadval.
- MinHeap
- Min-heap: eng kichik element har doim tepada.
- Queue
- Halqasimon bufer (ring buffer) asosidagi navbat.
- Stack
- Stack — bir uchidan qo’shiladigan va o’sha uchidan olinadigan to’plam.
Functions§
- stack_
balanced_ brackets - Stackning klassik qo’llanilishi: qavslar to’g’ri joylashganini tekshirish.