Yığın (Stack)

Masanın üzerinde duran bir tabak yığını düşün. Yeni tabağı en üste koyarsın, almak istediğinde de en üsttekini alırsın. Ortadan bir tabak çekmeye kalkarsan ya yığın devrilir ya da önce üstündekileri kaldırman gerekir. Bu gündelik kısıtlama, bilgisayar biliminin en yaygın veri yapılarından birinin tanımıdır: yığın (stack).

Yığın, yalnızca iki temel işlem sunar: en üste ekle (Push) ve en üstten al (Pop). Bu kısıtlama bir eksiklik değil, tam olarak yığının değeridir. "Son giren ilk çıkar" (LIFO — Last In, First Out) kuralı, geriye doğru izlenmesi gereken her problemin doğal ifadesidir: geri alma (undo) geçmişi, tarayıcının geri düğmesi, iç içe parantezler, özyinelemeli fonksiyon çağrıları.

Nitekim yığın yalnızca yazdığın bir veri yapısı değil; programının çalışma biçiminin de temelidir. Her fonksiyon çağrısı, çağrı yığınına (call stack) bir çerçeve ekler. Bu derste LIFO prensibini, yığını iki farklı yolla uygulamayı, parantez dengeleme ve postfix değerlendirme gibi klasik uygulamaları, çağrı yığınının nasıl çalıştığını ve mülakatların gözdesi olan monoton yığın desenini öğreneceksin.

LIFO ve temel işlemler

Push(10)   Push(20)   Push(30)    Pop() → 30   Pop() → 20
                                                
                        ┌────┐
             ┌────┐     │ 30 │◄ üst
  ┌────┐     │ 20 │◄    ├────┤     ┌────┐
  │ 10 │◄    ├────┤     │ 20 │     │ 20 │◄     ┌────┐
  ├────┤     │ 10 │     ├────┤     ├────┤      │ 10 │◄
  └────┘     └────┘     │ 10 │     │ 10 │      └────┘
                        └────┘     └────┘

Bir yığının sunduğu işlemler azdır ve hepsi sabit sürede çalışır:

Aşağıdaki görselleştirmede eleman ekleyip çıkararak LIFO davranışını izleyebilirsin. Aynı bileşenin kuyruk kipiyle karşılaştırmak, iki yapının farkını netleştirir:

Dilim tabanlı jenerik yığın

Go'da yığın için ayrı bir tip yoktur; çünkü dilimler zaten mükemmel bir yığındır. append sona ekler, dilimi bir kısaltmak sondan siler — ikisi de tam olarak ihtiyacımız olan işlemlerdir.

package main

import "fmt"

type Stack[T any] struct {
	items []T
}

// Push: amortize O(1)
func (s *Stack[T]) Push(v T) {
	s.items = append(s.items, v)
}

// Pop: O(1)
func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	last := len(s.items) - 1
	v := s.items[last]
	s.items[last] = zero // işaretçi tutuyorsa serbest bırak
	s.items = s.items[:last]
	return v, true
}

// Peek: O(1)
func (s *Stack[T]) Peek() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	return s.items[len(s.items)-1], true
}

func (s *Stack[T]) Len() int      { return len(s.items) }
func (s *Stack[T]) IsEmpty() bool { return len(s.items) == 0 }

func main() {
	var s Stack[string] // sıfır değer kullanıma hazır

	for _, page := range []string{"anasayfa", "ürünler", "sepet", "ödeme"} {
		s.Push(page)
	}
	fmt.Println("geçmiş derinliği:", s.Len())

	top, _ := s.Peek()
	fmt.Println("şu anki sayfa:", top)

	// Geri düğmesi: LIFO
	for range 2 {
		page, _ := s.Pop()
		fmt.Println("geri →", page)
	}

	current, _ := s.Peek()
	fmt.Println("şimdi buradayız:", current, "| kalan:", s.Len())

	var empty Stack[int]
	_, ok := empty.Pop()
	fmt.Println("boş yığından çekilebildi mi:", ok)
}

geçmiş derinliği: 4
şu anki sayfa: ödeme
geri → ödeme
geri → sepet
şimdi buradayız: ürünler | kalan: 2
boş yığından çekilebildi mi: false

s.items[last] = zero satırı ihmal edilmemesi gereken bir ayrıntıdır. Dilimi kısaltmak, altta yatan dizideki değeri silmez; eleman bir işaretçi içeriyorsa çöp toplayıcı o belleği geri alamaz. Yığın uzun ömürlüyse bu sızıntı büyür.

Bağlı liste tabanlı yığın

Yığını bağlı listeyle de yazabilirsin. Bu sürümde kapasite kopyalaması hiç olmaz, ama her eleman için bir düğüm ayrılır:

package main

import "fmt"

type node[T any] struct {
	value T
	next  *node[T]
}

type LinkedStack[T any] struct {
	top  *node[T]
	size int
}

func (s *LinkedStack[T]) Push(v T) {
	s.top = &node[T]{value: v, next: s.top} // yeni düğüm başa geçer
	s.size++
}

func (s *LinkedStack[T]) Pop() (T, bool) {
	var zero T
	if s.top == nil {
		return zero, false
	}
	n := s.top
	s.top = n.next
	n.next = nil
	s.size--
	return n.value, true
}

func (s *LinkedStack[T]) Peek() (T, bool) {
	var zero T
	if s.top == nil {
		return zero, false
	}
	return s.top.value, true
}

func (s *LinkedStack[T]) Len() int { return s.size }

func main() {
	var s LinkedStack[int]

	for _, v := range []int{1, 2, 3, 4} {
		s.Push(v)
	}

	fmt.Print("çıkış sırası: ")
	for s.Len() > 0 {
		v, _ := s.Pop()
		fmt.Print(v, " ")
	}
	fmt.Println()
	fmt.Println("boş mu:", s.Len() == 0)
}

çıkış sırası: 4 3 2 1
boş mu: true

Hangisini seçmeli? Neredeyse her zaman dilim tabanlı sürümü. Bitişik bellek önbellek dostudur, düğüm ayırma maliyeti yoktur ve kod daha kısadır. Bağlı liste sürümü yalnızca iki durumda avantajlıdır: yığın çok büyük olup tek seferlik büyük bir yeniden ayırma istemiyorsan, ya da elemanların adresleri sabit kalmalıysa.

Uygulama: parantez dengeleme

Derleyicilerin ve düzenleyicilerin ilk kontrollerinden biridir: Açılan her parantez kapanmış mı ve doğru sırada mı? Bu problem yığın için biçilmiş kaftandır, çünkü en son açılan parantez ilk kapanmalıdır.

package main

import "fmt"

// balanced, parantezlerin dengeli olup olmadığını ve ilk hatanın konumunu döndürür.
func balanced(s string) (bool, int) {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var stack []rune

	for i, r := range s {
		switch r {
		case '(', '[', '{':
			stack = append(stack, r)
		case ')', ']', '}':
			if len(stack) == 0 {
				return false, i // kapanış var, açılış yok
			}
			top := stack[len(stack)-1]
			if top != pairs[r] {
				return false, i // yanlış tür kapanış
			}
			stack = stack[:len(stack)-1]
		}
	}
	if len(stack) > 0 {
		return false, len(s) // kapanmamış parantez kaldı
	}
	return true, -1
}

func main() {
	cases := []string{
		"(a + b) * [c - d]",
		"{ [ ( ) ] }",
		"(a + b",
		"(a + b]",
		")(",
		"",
		"func(x) { return [1, 2] }",
	}

	for _, c := range cases {
		ok, pos := balanced(c)
		if ok {
			fmt.Printf("✓ %-26q dengeli\n", c)
		} else {
			fmt.Printf("✗ %-26q hata konumu: %d\n", c, pos)
		}
	}
}

✓ "(a + b) * [c - d]"        dengeli
✓ "{ [ ( ) ] }"              dengeli
✗ "(a + b"                   hata konumu: 6
✗ "(a + b]"                  hata konumu: 6
✗ ")("                       hata konumu: 0
✓ ""                         dengeli
✓ "func(x) { return [1, 2] }" dengeli

Alan karmaşıklığı en kötü durumda O(n)'dir: Girdi tamamen açılış parantezinden oluşuyorsa hepsi yığına girer.

Uygulama: postfix ifade değerlendirme

Alışık olduğumuz 3 + 4 * 2 yazımına infix denir ve işlem önceliği ile parantez kuralları gerektirir. Postfix (ters Lehçe) yazımda operatör işlenenlerden sonra gelir: 3 4 2 * +. Bu yazımın güzelliği, hiç parantez gerektirmemesi ve tek bir yığınla soldan sağa değerlendirilebilmesidir.

ifade: 3 4 2 * +

oku 3 → yığına        [3]
oku 4 → yığına        [3 4]
oku 2 → yığına        [3 4 2]
oku * → 4*2=8         [3 8]
oku + → 3+8=11        [11]

sonuç: 11

package main

import (
	"errors"
	"fmt"
	"strconv"
	"strings"
)

var (
	ErrBadExpression = errors.New("geçersiz ifade")
	ErrDivByZero     = errors.New("sıfıra bölme")
)

func evalPostfix(expr string) (int, error) {
	var stack []int

	pop2 := func() (int, int, bool) {
		if len(stack) < 2 {
			return 0, 0, false
		}
		b, a := stack[len(stack)-1], stack[len(stack)-2]
		stack = stack[:len(stack)-2]
		return a, b, true
	}

	for _, token := range strings.Fields(expr) {
		if n, err := strconv.Atoi(token); err == nil {
			stack = append(stack, n)
			continue
		}

		a, b, ok := pop2()
		if !ok {
			return 0, fmt.Errorf("%w: %q için yeterli işlenen yok", ErrBadExpression, token)
		}

		switch token {
		case "+":
			stack = append(stack, a+b)
		case "-":
			stack = append(stack, a-b)
		case "*":
			stack = append(stack, a*b)
		case "/":
			if b == 0 {
				return 0, ErrDivByZero
			}
			stack = append(stack, a/b)
		default:
			return 0, fmt.Errorf("%w: bilinmeyen işleç %q", ErrBadExpression, token)
		}
	}

	if len(stack) != 1 {
		return 0, fmt.Errorf("%w: ifade tamamlanmamış", ErrBadExpression)
	}
	return stack[0], nil
}

func main() {
	cases := []string{
		"3 4 2 * +",         // 3 + 4*2 = 11
		"5 1 2 + 4 * + 3 -", // 5 + (1+2)*4 - 3 = 14
		"10 2 /",
		"7 0 /",
		"1 +",
		"2 3 %",
		"1 2 3",
	}

	for _, c := range cases {
		result, err := evalPostfix(c)
		if err != nil {
			fmt.Printf("%-20q hata: %v\n", c, err)
			continue
		}
		fmt.Printf("%-20q = %d\n", c, result)
	}
}

"3 4 2 * +"          = 11
"5 1 2 + 4 * + 3 -"  = 14
"10 2 /"             = 5
"7 0 /"              hata: sıfıra bölme
"1 +"                hata: geçersiz ifade: "+" için yeterli işlenen yok
"2 3 %"              hata: geçersiz ifade: bilinmeyen işleç "%"
"1 2 3"              hata: geçersiz ifade: ifade tamamlanmamış

İşlenenleri çekerken sıraya dikkat et: Yığından ilk çıkan ikinci işlenendir. Bu ayrıntı çıkarma ve bölmede kritiktir; a - b ile b - a farklı sonuçlar verir.

Aynı fikirle infix ifadeleri postfix'e çeviren algoritmaya shunting-yard denir ve o da bir yığın kullanır. Hesap makineleri, derleyiciler ve elektronik tablo motorları bu iki adımı birlikte kullanır.

Çağrı yığını

Yığın yalnızca yazdığın bir yapı değildir; programın kendisi bir yığın üzerinde çalışır. Her fonksiyon çağrısında, o çağrıya ait yerel değişkenler, parametreler ve dönüş adresi bir çerçeve (frame) hâlinde çağrı yığınına eklenir. Fonksiyon dönünce çerçeve atılır.

main()
 └─ factorial(3)          yığın (yukarı doğru büyür)
     └─ factorial(2)      ┌──────────────┐
         └─ factorial(1)  │ factorial(1) │ ← en üst çerçeve
                          ├──────────────┤
                          │ factorial(2) │
                          ├──────────────┤
                          │ factorial(3) │
                          ├──────────────┤
                          │    main      │
                          └──────────────┘

package main

import "fmt"

var depth, maxDepth int

func factorial(n int) int {
	depth++
	maxDepth = max(maxDepth, depth)
	defer func() { depth-- }()

	if n <= 1 {
		return 1
	}
	return n * factorial(n-1)
}

// iterativeFactorial: özyineleme yerine döngü — çağrı yığını büyümez
func iterativeFactorial(n int) int {
	result := 1
	for i := 2; i <= n; i++ {
		result *= i
	}
	return result
}

func main() {
	fmt.Println("10! =", factorial(10))
	fmt.Println("ulaşılan en derin çerçeve sayısı:", maxDepth)
	fmt.Println("çağrı bittiğinde derinlik:", depth)

	fmt.Println("iteratif 10! =", iterativeFactorial(10))
	fmt.Println("sonuçlar aynı mı:", factorial(10) == iterativeFactorial(10))
}

10! = 3628800
ulaşılan en derin çerçeve sayısı: 10
çağrı bittiğinde derinlik: 0
iteratif 10! = 3628800
sonuçlar aynı mı: true

Özyineleme derinliği sınırsız değildir. Çoğu dilde sabit boyutlu bir çağrı yığını vardır ve aşıldığında program "stack overflow" hatasıyla çöker. Go bu konuda farklıdır: Goroutine yığınları küçük başlar (birkaç kilobayt) ve gerektikçe büyür, bu yüzden Go'da çok daha derin özyinelemeler mümkündür. Yine de sınır vardır ve aşıldığında çalışma zamanı programı sonlandırır.

Bu, özyinelemeli bir algoritmayı yığın kullanarak iteratif hâle getirmenin neden yaygın bir teknik olduğunu açıklar: Çerçeveleri sen yönetirsen, bellek sınırlarını da sen belirlersin. Bu dönüşümü Özyineleme ve BFS ve DFS derslerinde uygulayacaksın.

Monoton yığın deseni

Bu, yığınların en zarif kullanımıdır ve ilk görüldüğünde sihir gibi gelir. Fikir şudur: Yığında sıralı kalan (hep artan ya da hep azalan) bir eleman kümesi tutarsın. Yeni gelen eleman bu sırayı bozacaksa, bozan elemanları çıkarırsın — ve her çıkarılan eleman için bir cevap üretirsin.

Klasik problem: Her gün için, "kaç gün sonra bugünden daha sıcak bir gün gelecek?" sorusunu yanıtla. Kaba kuvvet çözümü her gün için ileriye bakar: O(n²). Monoton yığınla bu O(n)'e iner.

package main

import "fmt"

// nextWarmerDay, her gün için daha sıcak bir güne kaç gün kaldığını döndürür.
// Azalan monoton yığın kullanır; yığında henüz cevabı bulunmamış günlerin indeksleri durur.
func nextWarmerDay(temps []int) []int {
	answer := make([]int, len(temps))
	var stack []int // indeksler; karşılık gelen sıcaklıklar azalan sırada

	for i, t := range temps {
		// Bugün, yığındaki günlerden daha sıcaksa onların cevabı bulundu
		for len(stack) > 0 && temps[stack[len(stack)-1]] < t {
			prev := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			answer[prev] = i - prev
		}
		stack = append(stack, i)
	}
	// Yığında kalanların daha sıcak günü yok: cevapları 0 kalır
	return answer
}

// largestRectangle, histogramdaki en büyük dikdörtgenin alanını bulur.
// Artan monoton yığın kullanır.
func largestRectangle(heights []int) int {
	var stack []int // artan yüksekliklerin indeksleri
	best := 0

	for i := 0; i <= len(heights); i++ {
		h := 0 // sanal sıfır yükseklik: yığını sonda boşaltır
		if i < len(heights) {
			h = heights[i]
		}
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= h {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			left := -1
			if len(stack) > 0 {
				left = stack[len(stack)-1]
			}
			width := i - left - 1
			best = max(best, height*width)
		}
		stack = append(stack, i)
	}
	return best
}

func main() {
	temps := []int{30, 32, 28, 27, 35, 31, 33}
	fmt.Println("sıcaklıklar:", temps)
	fmt.Println("kaç gün sonra:", nextWarmerDay(temps))

	fmt.Println()
	heights := []int{2, 1, 5, 6, 2, 3}
	fmt.Println("histogram:", heights)
	fmt.Println("en büyük dikdörtgen alanı:", largestRectangle(heights))

	fmt.Println("tek çubuk:", largestRectangle([]int{7}))
	fmt.Println("artan:", largestRectangle([]int{1, 2, 3, 4, 5}))
}

sıcaklıklar: [30 32 28 27 35 31 33]
kaç gün sonra: [1 3 2 1 0 1 0]

histogram: [2 1 5 6 2 3]
en büyük dikdörtgen alanı: 10
tek çubuk: 7
artan: 9

Karmaşıklık analizindeki incelik şudur: İçteki for döngüsü yüzünden algoritma O(n²) gibi görünür. Ama her eleman yığına tam olarak bir kez girer ve en fazla bir kez çıkar. Dolayısıyla iç döngünün tüm çalıştırmalarının toplamı n ile sınırlıdır. Bu, amortize analizin klasik bir uygulamasıdır.

Monoton yığın deseninin tanınması gereken işareti şudur: "Her eleman için, solunda/sağında ondan büyük/küçük olan ilk elemanı bul." Bu cümleyi gördüğün her problemde monoton yığını dene.

Yığını ne zaman seçmeli?

Yığın, doğru problemde kullanıldığında kodu şaşırtıcı biçimde sadeleştirir. Tanıman gereken desenler şunlardır.

Geri alma ve geçmiş. Kullanıcının yaptığı işlemleri sırayla saklayıp tersine çevirmek gerekiyorsa, yığın tam olarak istediğin davranışı verir. İki yığın kullanarak ileri alma (redo) da eklenir: Geri alınan işlem ikinci yığına gider.

İç içe yapılar. Parantezler, HTML etiketleri, JSON nesneleri, blok kapsamları — hepsinde en son açılan ilk kapanır. Böyle bir yapıyı doğrulamak ya da işlemek istiyorsan yığın doğal araçtır.

Özyinelemeyi döngüye çevirme. Derin özyineleme yapan bir algoritmayı yığınla iteratif hâle getirebilirsin. Çağrı çerçevelerinin yerini, kendi tanımladığın durum kayıtları alır.

Geriye izleme. Bir çözüm yolunda ilerleyip çıkmaza girdiğinde geri dönmen gerekiyorsa, geçilen adımlar bir yığında tutulur. Labirent çözme, bulmaca ve kısıt problemleri bu desene uyar.

"Önceki büyük/küçük eleman" soruları. Monoton yığın, ilk bakışta O(n²) görünen bu problem ailesini O(n)'e indirir.

Yığın uygun olmayan yerler de vardır: Elemanlara sırayla (FIFO) hizmet vermen gerekiyorsa kuyruk, önceliğe göre hizmet vermen gerekiyorsa öncelik kuyruğu doğru araçtır. Ortadaki elemanlara erişmen gerekiyorsa yığın zaten yanlış soyutlamadır — o zaman dilimi doğrudan kullan.

Sık yapılan hatalar

• Boş yığından çekmeyi kontrol etmemek. items[len(items)-1] ifadesi boş dilimde panik oluşturur; her zaman ok dönüşü kullan.
• Pop sırasında sıfırlamayı unutmak. Silinen eleman işaretçi içeriyorsa bellek serbest bırakılmaz.
• Postfix'te işlenen sırasını karıştırmak. Yığından ilk çıkan ikinci işlenendir; çıkarma ve bölmede sonucu değiştirir.
• Yığın yerine dilimi doğrudan kullanıp niyeti gizlemek. Tip olarak Stack[T] kullanmak kodun ne yaptığını anlatır.
• Monoton yığında yanlış karşılaştırma yönü seçmek. Artan mı azalan mı tutacağın, sorunun "daha büyük" mü "daha küçük" mü aradığına bağlıdır.
• Derin özyinelemede yığın sınırını hesaba katmamak. Girdi boyutu kontrolsüzse iteratif sürümü tercih et.
• Eşzamanlı erişimde yığını korumamak. Birden çok goroutine aynı yığına dokunuyorsa kilit gerekir.

Alıştırmalar

package main

import "fmt"

type Editor struct {
	current string
	undo    []string
	redo    []string
}

func (e *Editor) Type(text string) {
	e.undo = append(e.undo, e.current)
	e.current = text
	e.redo = e.redo[:0] // yeni dal: ileri alma geçmişi geçersiz
}

func (e *Editor) Undo() bool {
	if len(e.undo) == 0 {
		return false
	}
	last := len(e.undo) - 1
	e.redo = append(e.redo, e.current)
	e.current = e.undo[last]
	e.undo = e.undo[:last]
	return true
}

func (e *Editor) Redo() bool {
	if len(e.redo) == 0 {
		return false
	}
	last := len(e.redo) - 1
	e.undo = append(e.undo, e.current)
	e.current = e.redo[last]
	e.redo = e.redo[:last]
	return true
}

func (e *Editor) String() string {
	return fmt.Sprintf("%-14q (geri:%d ileri:%d)", e.current, len(e.undo), len(e.redo))
}

func main() {
	var e Editor

	e.Type("merhaba")
	e.Type("merhaba dünya")
	e.Type("merhaba Go")
	fmt.Println("yazıldı:  ", &e)

	e.Undo()
	fmt.Println("geri al:  ", &e)
	e.Undo()
	fmt.Println("geri al:  ", &e)

	e.Redo()
	fmt.Println("ileri al: ", &e)

	e.Type("yeni dal")
	fmt.Println("yeni yazı:", &e)
	fmt.Println("ileri al mümkün mü:", e.Redo())

	for e.Undo() {
	}
	fmt.Println("tamamen geri:", &e)
	fmt.Println("daha fazla geri alınabilir mi:", e.Undo())
}

yazıldı:   "merhaba Go"   (geri:3 ileri:0)
geri al:   "merhaba dünya" (geri:2 ileri:1)
geri al:   "merhaba"      (geri:1 ileri:2)
ileri al:  "merhaba dünya" (geri:2 ileri:1)
yeni yazı: "yeni dal"     (geri:3 ileri:0)
ileri al mümkün mü: false
tamamen geri: ""             (geri:0 ileri:3)
daha fazla geri alınabilir mi: false

package main

import "fmt"

type MinStack struct {
	items []int
	mins  []int // mins[i] = items[0..i] aralığının minimumu
}

func (s *MinStack) Push(v int) {
	s.items = append(s.items, v)
	if len(s.mins) == 0 {
		s.mins = append(s.mins, v)
		return
	}
	s.mins = append(s.mins, min(s.mins[len(s.mins)-1], v))
}

func (s *MinStack) Pop() (int, bool) {
	if len(s.items) == 0 {
		return 0, false
	}
	last := len(s.items) - 1
	v := s.items[last]
	s.items = s.items[:last]
	s.mins = s.mins[:last]
	return v, true
}

func (s *MinStack) Peek() (int, bool) {
	if len(s.items) == 0 {
		return 0, false
	}
	return s.items[len(s.items)-1], true
}

// Min: O(1)
func (s *MinStack) Min() (int, bool) {
	if len(s.mins) == 0 {
		return 0, false
	}
	return s.mins[len(s.mins)-1], true
}

func (s *MinStack) Len() int { return len(s.items) }

func main() {
	var s MinStack

	for _, v := range []int{5, 3, 7, 3, 9, 1} {
		s.Push(v)
		m, _ := s.Min()
		fmt.Printf("push %-2d → min %d\n", v, m)
	}

	fmt.Println()
	for s.Len() > 0 {
		v, _ := s.Pop()
		m, ok := s.Min()
		if !ok {
			fmt.Printf("pop  %-2d → yığın boş\n", v)
			continue
		}
		fmt.Printf("pop  %-2d → min %d\n", v, m)
	}

	_, ok := s.Min()
	fmt.Println("boş yığında min var mı:", ok)
}

push 5  → min 5
push 3  → min 3
push 7  → min 3
push 3  → min 3
push 9  → min 3
push 1  → min 1

pop  1  → min 3
pop  9  → min 3
pop  3  → min 3
pop  7  → min 3
pop  3  → min 5
pop  5  → yığın boş
boş yığında min var mı: false

package main

import "fmt"

// trapStack: monoton yığınla katman katman su hesaplar.
func trapStack(heights []int) int {
	var stack []int // azalan yüksekliklerin indeksleri
	water := 0

	for i, h := range heights {
		for len(stack) > 0 && heights[stack[len(stack)-1]] < h {
			bottom := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break // solda duvar yok: su tutulmaz
			}
			left := stack[len(stack)-1]
			width := i - left - 1
			depth := min(heights[left], h) - heights[bottom]
			water += width * depth
		}
		stack = append(stack, i)
	}
	return water
}

// trapTwoPointers: O(1) bellekle aynı sonucu verir.
func trapTwoPointers(heights []int) int {
	if len(heights) < 3 {
		return 0
	}
	left, right := 0, len(heights)-1
	leftMax, rightMax := heights[left], heights[right]
	water := 0

	for left < right {
		if leftMax <= rightMax {
			left++
			leftMax = max(leftMax, heights[left])
			water += leftMax - heights[left]
		} else {
			right--
			rightMax = max(rightMax, heights[right])
			water += rightMax - heights[right]
		}
	}
	return water
}

func main() {
	cases := [][]int{
		{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1},
		{4, 2, 0, 3, 2, 5},
		{3, 3, 3},
		{5, 4, 3, 2, 1},
		{1},
		{},
	}

	for _, c := range cases {
		a := trapStack(c)
		b := trapTwoPointers(c)
		fmt.Printf("%-30v yığın=%-3d iki işaretçi=%-3d aynı mı=%t\n", c, a, b, a == b)
	}
}

[0                              1                              0                              2                              1                              0                              1                              3                              2                              1                              2                              1                             ] yığın=6   iki işaretçi=6   aynı mı=true
[4                              2                              0                              3                              2                              5                             ] yığın=9   iki işaretçi=9   aynı mı=true
[3                              3                              3                             ] yığın=0   iki işaretçi=0   aynı mı=true
[5                              4                              3                              2                              1                             ] yığın=0   iki işaretçi=0   aynı mı=true
[1                             ] yığın=0   iki işaretçi=0   aynı mı=true
[] yığın=0   iki işaretçi=0   aynı mı=true

Kısa sınav

Özet

• Yığın, LIFO prensibiyle çalışır: Push, Pop ve Peek işlemlerinin hepsi O(1)'dir.
• Go'da dilimler doğal bir yığındır; append ekler, dilimi kısaltmak siler.
• Pop sırasında çıkarılan yeri sıfırlamak, işaretçi içeren elemanlarda bellek sızıntısını önler.
• Bağlı liste tabanlı yığın kopyalama yapmaz ama önbellek dostu değildir ve eleman başına ek bellek harcar.
• Parantez dengeleme ve postfix değerlendirme, yığının klasik ve doğrudan uygulamalarıdır.
• Her fonksiyon çağrısı çağrı yığınına bir çerçeve ekler; derin özyineleme bu yüzden bellek tüketir.
• Monoton yığın, "solundaki/sağındaki ilk büyük eleman" ailesindeki problemleri O(n)'e indirir.
• Yığını geri alma, iç içe yapı doğrulama, geriye izleme ve özyinelemeyi döngüye çevirme işlerinde kullan; sıralı hizmet gerekiyorsa kuyruğa geç.