Stack (Yığın)
Son güncelleme
Bir stack (yığın), tam olarak tek bir açık ucu olan bir koleksiyondur. Bir değeri tepeye iterek (push) eklersiniz, yine tepeden çekerek (pop) çıkarırsınız; böylece en son giren değer daima ilk çıkan olur. LIFO'nun anlamı budur ve kuralın tamamı da bundan ibarettir: üstündekileri çıkarmadan ortadaki bir değere uzanmanın yolu yoktur. Yukarıdan Oynat'a basın; sütunun her push ile büyümesini, her pop ile aynı uçtan küçülmesini izleyin.
Kısıtlamanın kendisi işin özüdür. Her iki işlem de yalnızca tepeye dokunduğu için, yığın ne kadar yükselirse yükselsin her biri O(1)'dir. Yığınların bilgisayar dünyasında bu kadar çok şeyin altında yatmasının nedeni de bu öngörülebilirliktir: özyinelemeyi çalıştıran çağrı yığını, bir düzenleyicideki geri alma geçmişi, bir ayrıştırıcıdaki parantez eşleştirme ve özyinelemeli bir derinlik öncelikli aramayı döngüye çeviren açık yığın. Çıkarmanın yapıldığı ucu değiştirin, elinizde bunun yerine bir queue olur.
Zaman ve alan karmaşıklığı
Dizi veya bağlı liste tabanlı standart yığın için:
| İşlem | Karmaşıklık | Notlar |
|---|---|---|
| Push (ekleme) | O(1) | Zaman zaman yeniden boyutlanan dinamik bir dizide amortize edilmiş O(1). |
| Pop (çıkarma) | O(1) | Her zaman tepedeki eleman olduğu için kaydırma gerekmez. |
| Peek (tepeye bakma) | O(1) | Tepedeki değeri çıkarmadan okur. |
| Arama | O(n) | Yığın bunun için değildir: aşağı inmek için değerleri teker teker çıkarmanız gerekir. |
| Alan | O(n) | Saklanan her değer için bir yuva. |
Adım adım
| Adım | Ne olur |
|---|---|
| 1 | Yığın boş başlar; tepe hiçbir şeyi göstermez. |
| 2 | Push, değeri tepe konumuna yazar ve tepeyi bir yukarı taşır. |
| 3 | Sonraki her push, bir önceki değerin tam üstüne oturur. |
| 4 | Pop, tepedeki değeri okur ve ardından tepeyi bir aşağı taşır. |
| 5 | Geri dönen değer daima en son eklenmiş olandır. |
| 6 | Boş bir yığından çıkarma yapmak hatadır, buna yığın boşalması (stack underflow) denir; bu yüzden gerçek kod önce is_empty() kontrolü yapar. |
Çözümlü örnek
3, 7, 5 değerlerini ekleyip ardından yığını boşaltma:
| İşlem | Yığın (alttan üste) | Döndürdüğü |
|---|---|---|
push(3) | [3] | hiçbir şey |
push(7) | [3, 7] | hiçbir şey |
push(5) | [3, 7, 5] | hiçbir şey |
pop() | [3, 7] | 5, en yeni değer |
pop() | [3] | 7 |
pop() | [] | 3, en eski değer, en sonda |
Stack ne zaman kullanılır
| Şu durumlarda kullanın | Şu durumlarda kaçının |
|---|---|
| En son eklenen öğeyi önce geri almanız gerekiyorsa: geri alma, geri butonları, parantez eşleştirme | En eski öğeye önce ihtiyacınız varsa; bunun için bir queue vardır |
| Özyinelemeli bir algoritmayı yinelemeli hale getiriyorsanız | Verinin ortasında arama yapmanız veya indeksle erişmeniz gerekiyorsa |
| İfadeler, JSON veya HTML gibi iç içe yapıları ayrıştırıyorsanız | Birçok okuyucunun rastgele erişime ihtiyacı varsa; bu durumda bir dizi veya harita daha uygundur |
Yeniden dengeleme olmadan garantili O(1) ekleme ve çıkarma istiyorsanız | Verinin sıralı tutulması gerekiyorsa; bunu bir heap veya ağaç sağlar |
Stack kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Stack uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Stack kodu
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)JavaScript ile Stack kodu
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Java ile Stack kodu
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}C++ ile Stack kodu
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}C ile Stack kodu
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Stack SSS
LIFO ne demek?
Last in, first out, yani son giren ilk çıkar: en son eklenen değer, ilk çıkarılan değerdir. Alışılmış benzetme bir tabak yığınıdır; az önce koyduğunuz tabağı alırsınız, en alttakini değil. Bir queue ise tam tersi kurala, FIFO'ya uyar.
Stack ile queue arasındaki fark nedir?
Yalnızca hangi uçtan çıkardığınız. İkisi de bir uçtan
O(1) ile ekler; stack aynı uçtan çıkarır (LIFO), queue diğer uçtan çıkarır (FIFO). Yukarıdaki karmaşıklık tablosu dahil geri kalan her şey aynıdır.Yığının temel işlemleri nelerdir?
push tepeye bir değer ekler, pop tepedeki değeri çıkarıp döndürür, peek (bazen top) tepedeki değeri çıkarmadan okur ve is_empty geriye bir şey kalıp kalmadığını bildirir. Dördü de O(1)'dir.Yığın taşması (stack overflow) nedir?
Yer kalmamış bir yığına ekleme yapmaktır. Ünlü örnek çağrı yığınıdır: her fonksiyon çağrısı bir çerçeve ekler, bu yüzden temel durumuna hiç ulaşmayan bir özyineleme, çalışma zamanının yığın sınırına çarpıp program çökene kadar eklemeye devam eder. Bunun aynadaki karşılığı, yani boş bir yığından çıkarma yapmak, yığın boşalmasıdır (stack underflow).
Bir yığın nasıl gerçeklenir?
İki yaygın yol var. Dinamik bir dizi eklemeyi ve çıkarmayı sondan yapar: amortize
O(1) ve önbellek dostudur, Python'daki list ile Java'daki ArrayDeque böyle çalışır. Bağlı liste eklemeyi ve çıkarmayı baştan yapar: en kötü durumda O(1) ve yeniden boyutlandırma yoktur, ama eleman başına bir işaretçi tutar. C++'taki std::stack bir adaptördür: varsayılan olarak parçalı bir dizi olan std::deque üzerinde çalışır, isterseniz başka bir kapsayıcı da verebilirsiniz.Gerçek programlarda yığınlar nerede kullanılır?
Fonksiyon çağrıları ve özyineleme için çağrı yığını, geri alma ve yineleme geçmişi, tarayıcıda geri gezinme, ayrıştırıcılarda ifade değerlendirme ve parantez eşleştirme, bir de özyinelemeli bir derinlik öncelikli aramayı yinelemeli bir döngüye çeviren açık yığın.
İlgili kaynaklar
Daha fazla görselleştirme
