Brauzerdə «Geri» düyməsini basanda ən son açdığın səhifəyə qayıdırsan, xidmət mərkəzindəki elektron növbədə isə birinci bilet alan birinci qəbul olunur. Bu iki gündəlik qayda informatikanın iki əsas verilənlər strukturunun — stekin və növbənin mahiyyətidir. Onların altında isə daha sadə «kərpiclər» dayanır: massiv və əlaqəli siyahı. Hər strukturun güclü və zəif tərəfini bilmək proqramın sürətini çox vaxt alqoritmdən də çox müəyyən edir.
Massiv və dinamik massiv
MassivTərif
Eyni ölçülü elementlərin yaddaşda ardıcıl, boşluqsuz yerləşdirildiyi struktur. Elementin ünvanı onun indeksindən sadə düsturla hesablanır, ona görə istənilən elementə müraciət O(1) vaxt aparır.
Burada
- base
- massivin başlanğıc ünvanı (A[0]-ın ünvanı)
- i
- elementin indeksi (0-dan başlayır)
- s
- bir elementin ölçüsü, bayt
İndeksin 0-dan başlamasının səbəbi də budur: i elementin başlanğıcdan neçə addım uzaqda olduğunu göstərir.
Nümunə 1: ünvanın hesablanması
Məsələ
4 baytlıq tam ədədlər massivi 1000 ünvanından başlayır. A[25] elementi hansı ünvandadır? Bəs A[5]-dən A[6]-ya keçəndə ünvan nə qədər dəyişir?
Həllini göstərHəllini gizlət
Həll
Qonşu elementlər arasında fərq s = 4 bayt.
Hesab i-nin qiymətindən asılı olmayaraq bir vurma və bir toplamadır — bu, O(1) müraciətin səbəbidir.
Bunun da bədəli var: massivin ortasına element əlavə etmək üçün sağdakı bütün elementləri bir yer sürüşdürmək lazımdır — O(n). Həm də ölçü əvvəlcədən sabitdir. Dinamik massiv (Python list, Java ArrayList, C++ vector) bu problemi belə həll edir: yer bitəndə iki dəfə böyük yeni massiv ayırır və köhnə elementləri ora köçürür.
Burada
- n
- əlavə edilən elementlərin sayı
- 1 + 2 + … + 2ᵏ
- bütün genişlənmələrdə köçürülən elementlərin cəmi (< 2n)
Amortizasiyalı dəyər: n əlavə etmənin ümumi işi 3n-dən azdır, deməli, bir əlavə etmə orta hesabla O(1)-dir — ayrı-ayrı «bahalı» genişlənmələrə baxmayaraq.
class DynamicArray:
def __init__(self):
self.cap, self.n, self.copies = 1, 0, 0
self.data = [None]
def append(self, x):
if self.n == self.cap:
self.cap *= 2
new = [None] * self.cap
for i in range(self.n):
new[i] = self.data[i]
self.copies += 1
self.data = new
self.data[self.n] = x
self.n += 1
arr = DynamicArray()
for k in range(1, 1025):
arr.append(k)
if k in (1, 2, 3, 5, 9, 17, 1024):
print(k, arr.cap, arr.copies)
print('copies per append:', arr.copies / arr.n)Gözlənilən nəticə
1 1 0 2 2 1 3 4 3 5 8 7 9 16 15 17 32 31 1024 1024 1023 copies per append: 0.9990234375
Davamını oxumaq üçün pulsuz qeydiyyatdan keç
Dərsin qalan bölmələri, test və qeydlər Educora hesabı ilə açılır. Qeydiyyat bir dəqiqə çəkir; irəliləyişin bütün cihazlarında saxlanılır.
Əlaqəli siyahılar
Əlaqəli siyahıTərif
Hər düyünün qiyməti və növbəti düyünə göstəricisi olan zəncir. Düyünlər yaddaşın istənilən yerində ola bilər; birinci düyünə baş (head) deyilir. İkitərəfli siyahıda hər düyün əvvəlkinə də göstərici saxlayır.
| Əməliyyat | Dinamik massiv | Birtərəfli əlaqəli siyahı |
|---|---|---|
| i-ci elementə müraciət | O(1) | O(n) |
| əvvələ əlavə / əvvəldən silmə | O(n) | O(1) |
| sona əlavə | amortizasiyalı O(1) | O(1) (tail göstəricisi ilə) |
| məlum düyündən sonra əlavə | O(n) (sürüşdürmə) | O(1) |
| qiymətə görə axtarış | O(n) | O(n) |
| yaddaş | yığcam, keşə uyğun | hər düyünə əlavə göstərici, səpələnmiş |
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, value):
self.head = Node(value, self.head)
def reverse(self):
prev, cur = None, self.head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
self.head = prev
def items(self):
cur = self.head
while cur:
yield cur.value
cur = cur.next
lst = LinkedList()
for city in ['Shaki', 'Ganja', 'Baku']: lst.push_front(city)
print(list(lst.items()))
lst.reverse()
print(list(lst.items()))Gözlənilən nəticə
['Baku', 'Ganja', 'Shaki'] ['Shaki', 'Ganja', 'Baku']
push_front yeni düyünü başa O(1)-də qoşur. reverse siyahını bir keçiddə — O(n) vaxt və O(1) əlavə yaddaşla çevirir: hər düyünün göstəricisini geriyə yönəldir. Bu, müsahibələrin klassik tapşırığıdır.Stek (LIFO) və növbə (FIFO)
| Struktur | Prinsip | Əməliyyatlar (hamısı O(1)) | Tətbiqlər |
|---|---|---|---|
| Stek | LIFO — sonuncu gələn birinci çıxır | push, pop, peek | funksiya çağırışları steki, «Geri al» (undo), mötərizələrin yoxlanması, DFS |
| Növbə | FIFO — birinci gələn birinci çıxır | enqueue, dequeue, front | çap növbəsi, şəbəkə buferləri, tapşırıq planlayıcısı, BFS |
Nümunə 2: postfiks ifadənin stek ilə hesablanması
Məsələ
Postfiks (tərs Polşa) yazılışında operator operandlardan sonra gəlir. 5 1 2 + 4 * + 3 - ifadəsini stek ilə hesabla.
Həllini göstərHəllini gizlət
Həll
5 → [5]
1 → [5, 1]
2 → [5, 1, 2]
+ → 1 + 2 = 3 → [5, 3]4 → [5, 3, 4]
* → 3 · 4 = 12 → [5, 12]+ → 5 + 12 = 17 → [17]3 → [17, 3]
- → 17 − 3 = 14 → [14]Cavab: 14 (adi yazılışda 5 + (1 + 2) · 4 − 3). Hər simvol bir dəfə emal olunur → O(n).
from collections import deque
def balanced(text):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in text:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
for s in ['(a[i] + b) * {c}', '(]', '((x)']:
print(s, balanced(s))
queue = deque(['Aysel', 'Murad', 'Leyla'])
queue.append('Elvin')
print(queue.popleft(), 'is served;', list(queue), 'wait')Gözlənilən nəticə
(a[i] + b) * {c} True
(] False
((x) False
Aysel is served; ['Murad', 'Leyla', 'Elvin'] waitdeque hər iki ucdan O(1)-də əlavə və silmə verir — ideal növbə.Növbəni sabit ölçülü massivdə də qurmaq olar: dairəvi bufer baş (head) və quyruq (tail) indekslərini saxlayır və massivin sonuna çatanda qalıqla bölmə vasitəsilə yenidən əvvələ «dolanır». Belə növbə yaddaş ayırmır və şəbəkə kartlarında, səs kartlarında, klaviatura buferində işlədilir.
Burada
- head
- növbənin ilk elementinin indeksi
- size
- növbədəki elementlərin sayı
- m
- massivin tutumu
- tail
- növbəti elementin yazılacağı indeks
Nümunə 3: dairəvi bufer
Məsələ
Tutumu m = 6 olan dairəvi buferdə head = 4, size = 3. Yeni element hansı indeksə yazılacaq? Sonra iki element çıxarılır. head nə olar?
Həllini göstərHəllini gizlət
Həll
tail = (4 + 3) mod 6 = 7 mod 6 = 1 → yeni element A[1]-ə yazılır, size = 4.
İki çıxarma: head = (4 + 1) mod 6 = 5, sonra (5 + 1) mod 6 = 0; size = 2.
Klassik müsahibə sualı: iki stekdən növbə qurmaq. Yeni elementlər in stekinə push olunur. Çıxarmaq lazım olanda out steki boşdursa, in-dəki bütün elementlər bir-bir out-a köçürülür — bu zaman sıra tərsinə çevrilir və ən köhnə element yuxarıya çıxır. Tək bir çıxarma O(n) ola bilər, amma hər element ən çoxu bir dəfə köçürülür, ona görə n əməliyyatın cəmi O(n), yəni hər əməliyyat amortizasiyalı O(1)-dir.
Yadda saxla
- Massivdə element ünvanı base + i · s ilə hesablanır — müraciət O(1), ortaya əlavə O(n).
- Dinamik massiv tutumu həndəsi artırır, ona görə sona əlavə amortizasiyalı O(1)-dir.
- Əlaqəli siyahıda əvvələ və məlum düyündən sonra əlavə O(1), indeksə görə müraciət isə O(n)-dir.
- Stek — LIFO (çağırışlar, undo, mötərizələr), növbə — FIFO (buferlər, BFS); hər ikisinin əməliyyatları O(1)-dir.
- Dairəvi bufer indeksləri mod m ilə dolandırır və sabit yaddaşda növbə yaradır.