Question 1

Stack nədir və hansı əməliyyatları var?

Accepted Answer

Tərifdən başla: stack — LIFO (Last In, First Out) prinsipi ilə işləyən abstrakt data tipidir; sonuncu qoyulan element birinci çıxarılır. Boşqab yığını analogiyası cavabı dərhal aydınlaşdırır. Əməliyyatları mürəkkəbliyi ilə birlikdə sadala — mürəkkəbliyi demək gözlənilir: push(x) O(1), pop() O(1), peek() O(1), isEmpty() O(1), size O(1). Sonra iki implementasiya variantını qeyd et: massiv üzərində (praktikada default — cache-dostudur) və linked list üzərində (heç vaxt köçürmə olmur). Hər ikisində əsas əməliyyatlar O(1)-dir. Ən güclü hissə isə niyə stack istifadə etmək sualına cavabdır: massiv onsuz da hər şeyi edə bilir, amma stack niyyəti ifadə edir və səhv istifadəni qeyri-mümkün edir — ortadan element götürmək interfeysdə yoxdur. Sonda real nümunə ver: call stack, undo, mötərizə yoxlaması, DFS.

Question 2

Mötərizələrin balansını yoxlayan alqoritmi izah et.

Accepted Answer

Əvvəlcə niyə stack sualına cavab ver: mötərizələrdə qayda "ən son açılan ən əvvəl bağlanmalıdır" — bu, tam olaraq LIFO-dur, ona görə stack təbii uyğunlaşır. Alqoritm: Sətri bir dəfə gəz Açılan mötərizə ((, [, {) gördükdə onu stack-ə push et Bağlanan mötərizə gördükdə: əvvəlcə stack boşdursa false qaytar (artıq bağlanan var); sonra pop et və növün uyğunluğunu yoxla — uyğun deyilsə false Dövr bitəndən sonra stack.isEmpty() qaytar — bağlanmamış mötərizə qalıbsa false Mürəkkəblik: O(n) time, ən pis halda O(n) space (bütün simvollar açılan mötərizədirsə). Sərhəd hallarını ucadan sadala — bu, cavabın ən dəyərli hissəsidir: boş sətir (true), yalnız açılanlar "(((" (false — son yoxlama tutur), yalnız bağlananlar ")))" (false — boş stack yoxlaması tutur), səhv növ uyğunluğu "([)]" (false), mötərizədən başqa simvollar (nəzərə alınmır). Sonda genişləndirməni qeyd et: real linter-lərdə eyni texnika HTML teq-ləri, dırnaqlar və kod blokları üçün istifadə olunur; xəta mesajı üçün mötərizə ilə birlikdə onun mövqeyini də stack-də saxlamaq lazımdır.

Question 3

Stack-i massiv və linked list üzərində implementasiya etməyin fərqi nədir? Hansını seçərsən?

Accepted Answer

Hər ikisində əsas əməliyyatların O(1) olduğunu dərhal de — fərq mürəkkəblikdə deyil, praktik xassələrdədir. Bu çərçivə cavabı güclü edir. Massiv əsaslı: push amortized O(1) (tutum dolanda O(n) köçürmə), pop/peek O(1) Yaddaş sıxdır — element başına əlavə metadata yoxdur Cache lokallığı yaxşıdır — praktikada nəzərəçarpacaq dərəcədə sürətlidir Mənfi: böyümə anlarında O(n) pauza; istifadə olunmayan tutum bir qədər israfdır Linked list əsaslı: Bütün əməliyyatlar zəmanətli O(1) — heç vaxt köçürmə pauzası yoxdur Node başına əlavə pointer yaddaşı Cache lokallığı pisdir Hər push bir obyekt ayırması deməkdir — GC təzyiqi Seçim: "Default olaraq massiv əsaslı seçirəm — JS-də Array, Kotlin-də ArrayDeque, Dart-da List. Cache lokallığı və sadəlik demək olar həmişə üstün gəlir. Linked list-i yalnız hər əməliyyatın zəmanətli O(1) olması tələb olunanda (real-time sistemlərdə köçürmə pauzası qəbuledilməzdirsə) və ya elementlər çox böyükdürsə seçərdim." Əlavə bir nüans: Java/Kotlin-də java.util.Stack istifadə etməmək lazımdır — o, köhnəlmiş, Vector-dan miras alan və hər əməliyyatda sinxronlaşan sinifdir; ArrayDeque daha sürətlidir. Bu detalı bilmək təcrübə siqnalıdır.

Question 4

Call stack ilə stack data strukturu arasında əlaqə nədir?

Accepted Answer

Əlaqəni birbaşa de: call stack məhz stack data strukturudur — sadəcə onu proqram deyil, runtime idarə edir. Necə işləyir: funksiya çağırılanda stack-ə frame push olunur (parametrlər, lokal dəyişənlər, qayıdış ünvanı); return olanda frame pop olunur. Ən son çağırılan funksiya birinci qayıdır — tam LIFO. Bu əlaqədən çıxan nəticələri sadala — cavabı dəyərli edən hissə budur: Stack trace LIFO sırası ilə çap olunur: ən üstdəki sətir ən son çağırışdır, aşağı getdikcə çağıran funksiyalara doğru gedirsən. Debug edərkən bunu bilmək vacibdir. Stack overflow — pop olunmayan push-ların yığılması; stack məhdud olduğu üçün (bir neçə MB) dərin rekursiya onu doldurur. Rekursiyanın space complexity-si dərinliyə bərabərdir, çünki frame-lər eyni anda stack-də durur. Hər rekursiya iterativ yazıla bilər — call stack-i heap-dəki açıq stack ilə əvəz edirsən. DFS-in rekursiv və iterativ variantları məhz eyni alqoritmin iki üzüdür. Tail call optimizasiyası — rekursiv çağırış son əməliyyatdırsa, frame təkrar istifadə oluna bilər; Kotlin tailrec ilə bunu edir, JS mühitlərinin əksəriyyəti və Dart etmir. Praktik nəticə ilə bitir: "Dərinliyi girişdən asılı olan alqoritmlərdə açıq stack ilə iterativ yazıram — o zaman limit call stack-in bir neçə MB-ı yox, heap-in həcmi olur."

Question 5

Bir massivdən istifadə edərək iki stack-i necə saxlayarsan? Yaxud iki stack ilə queue necə qurulur?

Accepted Answer

Bunlar klassik "struktur dizaynı" sualları olduğu üçün ideyanı aydın izah etmək kodu yazmaqdan vacibdir. İki stack, bir massiv: birini massivin əvvəlindən (indeks 0-dan sağa), digərini sonundan (son indeksdən sola) böyüt. Massiv dolub-dolmadığını top1 + 1 == top2 şərti ilə yoxlayırsan. Üstünlüyü: yaddaş dinamik bölüşdürülür — biri az, digəri çox yer tuta bilər, halbuki massivi ortadan ikiyə bölsəydin, bir tərəf dolanda digərində boş yer qalardı. Bütün əməliyyatlar O(1). İki stack ilə queue: inbox və outbox stack-ləri saxla. enqueue(x): inbox-a push — O(1) dequeue(): outbox boşdursa, inbox-dakı hamısını outbox-a köçür (bu, sıranı tərsinə çevirir və FIFO davranışı verir), sonra outbox-dan pop et Mürəkkəblik təhlili — sualın əsl mahiyyəti budur: tək bir dequeue ən pis halda O(n) ola bilər, amma hər element ömrü boyu yalnız bir dəfə köçürülür, ona görə dequeue amortized O(1)-dir. Bu amortized arqumenti düzgün ifadə etmək cavabın ən vacib hissəsidir. Əks sual da var — iki queue ilə stack: mümkündür, amma ya push, ya da pop O(n) olur; bu, əvvəlkindən daha az səmərəlidir və bunu qeyd etmək müqayisə bacarığı göstərir. Praktik qeyd əlavə et: real kodda FIFO lazımdırsa hazır ArrayDeque/Queue istifadə edirəm; bu konstruksiyalar əsasən müsahibə məsələləridir və məhdud primitivlərlə düşünmə bacarığını yoxlayır.

Meyar	Massiv əsaslı	Linked list əsaslı
push	amortized O(1) — sona əlavə	O(1) — başa əlavə
pop / peek	O(1) — sondan	O(1) — başdan
Yaddaş	Sıx; boş tutum bir qədər israf ola bilər	Node başına əlavə pointer
Böyümə	Tutum dolanda O(n) köçürmə (nadir)	Köçürmə yoxdur
Cache lokallığı	Yaxşı — praktikada daha sürətli	Pis
Ölçü limiti	Yaddaş qədər	Yaddaş qədər
Praktik seçim	Default — JS `Array`, Kotlin `ArrayDeque`, Dart `List`	Yalnız xüsusi tələb olanda

Stack (LIFO)

📚 Mənbələr və sənədlər