Coding Interview Prep · Ders

Yığın Uygulaması ve Kullanım Alanları

Q: “Yığın Uygulaması ve Kullanım Alanları” dersi ücretsiz mi?

Evet — “Yığın Uygulaması ve Kullanım Alanları” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

Q: “Yığın Uygulaması ve Kullanım Alanları” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

push/pop/peek işlemlerine sahip bir yığın uygulayın; ardından geçerli parantezler, minimum yığın ve ters Polonya gösterimini değerlendirme problemlerini çözün.

Yığın Uygulaması ve Kullanım Alanları, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Yığın Veri Yapısı

Bir yığın, son giren ilk çıkar (LIFO) veri yapısıdır. Yığına en son eklenen öğe, ilk çıkarılan öğedir. Bir tabak yığını düşünün: yalnızca en üstten ekleme veya çıkarma yapabilirsiniz. Temel işlemler push (üste ekleme), pop (üstten çıkarma) ve peek (çıkarmadan üstteki öğeyi okuma) işlemleridir. İyi uygulanmış bir yığında bu üçünün de maliyeti O(1)'dir.

Python'da bir liste kusursuz bir yığın görevi görür: append push, pop() pop ve [-1] peek işlemidir.

stack = []

# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack)  # [10, 20, 30]

# Peek
print('Top:', stack[-1])       # 30

# Pop
print('Popped:', stack.pop())  # 30
print('After pop:', stack)     # [10, 20]

push, pop, peek, isEmpty İşlemlerine Sahip Yığın Sınıfı

Listeyi bir sınıfla sarmalamak daha temiz bir arayüz sağlar ve insert gibi yığına ait olmayan işlemlerin veya üst dışındaki konumlarda indekslemenin yanlışlıkla kullanılmasını engeller. Bu, sizden 'sıfırdan bir yığın uygulamanız' istendiğinde mülakatçıların beklediği uygulamadır.

class Stack:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError('pop from empty stack')
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty stack')
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek())  # 3
print(s.pop())   # 3
print(len(s))    # 2

Geçerli Parantezler (LeetCode 20)

LeetCode 20 'Geçerli Parantezler': bir parantez dizisinin dengeli olup olmadığını belirleyin. Her açılış parantezi için onu yığına ekleyin. Her kapanış parantezinde, yığının en üstündeki öğenin eşleşen açılış parantezi olduğunu denetleyin; eşleşmiyorsa veya yığın boşsa Yanlış döndürün. Sonda yığın boşsa dizi geçerlidir. Bu, kodlama mülakatlarında yığının ilk ve en temel uygulamasıdır.

def isValid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return len(stack) == 0

print(isValid('()[]{}'))    # True
print(isValid('([)]'))      # False
print(isValid('{[]}'))      # True
print(isValid(']'))         # False

Minimum Yığın (LeetCode 155)

LeetCode 155 'Minimum Yığın': push, pop, peek ve getMin işlemlerini O(1) zamanda destekleyen bir yığın tasarlayın. İncelik şudur: her konumdaki minimumu izleyen ikinci bir yığın tutun. Bir değer eklerken, yeni değer geçerli minimumdan <= ise (veya minimum yığını boşsa) onu minimum yığınına da ekleyin. Bir değer çıkarırken, çıkarılan değer geçerli minimuma eşitse minimum yığınından da çıkarın.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

Ters Polonya Gösterimini Değerlendirme

LeetCode 150 'Ters Polonya Gösterimini Değerlendirme' (son ek gösterimi): işlenenler yığına eklenir; bir işleçle karşılaşıldığında iki işlenen çıkarılır, işlem uygulanır ve sonuç yığına eklenir. Çıkarma ve bölme işlemlerinde sıra önemlidir: ilk çıkarılan sağ işlenendir, ikinci çıkarılan ise sol işlenendir.

def evalRPN(tokens):
    stack = []
    ops = set(['+', '-', '*', '/'])
    for tok in tokens:
        if tok not in ops:
            stack.append(int(tok))
        else:
            b = stack.pop()  # right operand
            a = stack.pop()  # left operand
            if tok == '+':
                stack.append(a + b)
            elif tok == '-':
                stack.append(a - b)
            elif tok == '*':
                stack.append(a * b)
            else:             # division truncated toward zero
                stack.append(int(a / b))
    return stack[0]

print(evalRPN(['2','1','+','3','*']))     # 9
print(evalRPN(['4','13','5','/','+']))    # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+']))  # 22

Dizge Kodunu Çözme (LeetCode 394)

LeetCode 394 'Dizge Kodunu Çözme': 3[a2[c]] gibi kodlanmış bir dizgeyi accaccacc biçimine genişletin. İki yığın kullanın: biri tekrar sayıları, diğeri biriktirilen dizgeler için. Bir rakamla karşılaşıldığında tam sayıyı oluşturun. [ ile karşılaşıldığında geçerli dizgeyi ve sayıyı yığına ekleyin. ] ile karşılaşıldığında bunları çıkarıp geçerli parçayı tekrarlayın. Bir harfle karşılaşıldığında onu geçerli dizgeye ekleyin.

def decodeString(s):
    count_stack = []
    str_stack   = []
    current_str = ''
    current_num = 0
    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)
        elif ch == '[':
            count_stack.append(current_num)
            str_stack.append(current_str)
            current_str = ''
            current_num = 0
        elif ch == ']':
            repeats = count_stack.pop()
            current_str = str_stack.pop() + current_str * repeats
        else:
            current_str += ch
    return current_str

print(decodeString('3[a]2[bc]'))    # 'aaabcbc'
print(decodeString('3[a2[c]]'))     # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'

Günlük Sıcaklıklar (Monotonik Yığın Ön İzlemesi)

LeetCode 739 'Günlük Sıcaklıklar': her gün için daha sıcak bir sıcaklığa kaç gün kaldığını bulun. Kaba kuvvet yaklaşımı O(n²)'dir. Yığınla şu şekilde çalışılır: sıcaklıklar üzerinde ilerleyin; her gün için sıcaklığı bugünkünden düşük olan tüm yığın girdilerini (gün indekslerini) çıkarın. Çıkarılan günlerin yanıtı (bugün - çıkarılan gün) olur. Geçerli günü yığına ekleyin. Yığında kalan girdiler hiçbir zaman daha sıcak bir gün bulamamıştır; bunların yanıtı 0'dır.

def dailyTemperatures(temps):
    result = [0] * len(temps)
    stack  = []  # stores indices
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

DFS Gezinmesi için Yığın

Özyinelemeli DFS'deki çağrı yığını açık bir yığınla değiştirilebilir ve algoritma yinelemeli hâle getirilebilir. Kökü yığına ekleyin; yığın boş olmadığı sürece bir düğüm çıkarın, işleyin ve çocuklarını ekleyin (soldan sağa işlemek için sağ çocuğu soldan önce ekleyin). Bu yinelemeli DFS, davranış açısından özyinelemeli DFS ile aynıdır; ancak derin ağaçlarda Python'un özyineleme sınırını aşma sorununu önler.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)  # push right first
        if node.left:
            stack.append(node.left)   # so left is processed first
    return result

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root))  # [1, 2, 4, 5, 3]

Zaman ve Alan Karmaşıklığı

Tüm yığın işlemleri (push, pop, peek, isEmpty) O(1) amortismanlıdır. n öğeden oluşan bir yığın oluşturmak O(n) zaman alır. Tüm öğelerin depolandığı en kötü durumda alan O(n)'dir. Monotonik yığın kullanan problemlerde her öğe en fazla bir kez eklenip çıkarılır; bu nedenle tüm yinelemeler boyunca toplam zaman O(n)'dir — naif bir dış döngü incelemesinin düşündürebileceği gibi O(n²) değildir.

# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total

def count_ops(n):
    pushes = pops = 0
    stack = []
    for i in range(n):
        while stack and stack[-1] < i:  # simulated decreasing condition
            stack.pop()
            pops += 1
        stack.append(i)
        pushes += 1
    return pushes, pops

p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}')  # <= 2000

Histogramdaki En Büyük Dikdörtgen (Ön İzleme)

LeetCode 84 'Histogramdaki En Büyük Dikdörtgen', klasik yığın problemlerinin en zorudur. Her çubuk için, çubuğun dayanak olabileceği dikdörtgen sola doğru daha kısa bir çubuk bulunana, sağa doğru da daha kısa bir çubuk bulunana kadar uzanır. Monotonik bir yığın, çubuk indekslerini artan yükseklik sırasıyla izler. Daha kısa bir çubuk görüldüğünde pop edin ve çıkarılan çubuğun yüksekliğiyle dikdörtgeni hesaplayın. Yığın, her pop işlemi için sol ve sağ sınırları O(1) zamanda verir.

def largestRectangleArea(heights):
    stack  = []  # indices, increasing heights
    result = 0
    heights = heights + [0]  # sentinel forces all pops
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width  = i if not stack else i - stack[-1] - 1
            result = max(result, height * width)
        stack.append(i)
    return result

print(largestRectangleArea([2,1,5,6,2,3]))  # 10
print(largestRectangleArea([2,4]))           # 4

Yığın Problemleri için Mülakat Stratejisi

Yığın problemleri çoğu zaman kendilerini 'içten dışa işle' veya 'bir sonraki daha büyük/küçük öğeyi bul' biçiminde gizler. Yığının yardımcı olabileceğini gösteren işaretler şunlardır: en son görülen öğeye ihtiyacınız vardır, çiftleri (parantezleri, etiketleri) eşleştiriyorsunuzdur veya naif olarak O(n²) iç içe döngüler gerektiren bir problemde O(n) istiyorsunuzdur. Özellikle monotonik yığınlar, 'her öğe için en yakın daha büyük/küçük öğeyi bulma' problemini O(n²)'den O(n)'e dönüştürür.

Bir mülakatta yığın değişmezini açıkça belirtin: 'Yükseklikleri azalan sırada indekslerden oluşan bir yığın tutacağım.'

Hızlı Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.

Ders Özeti

Bu derste şunları öğrendiniz: Python listeleri O(1) push/pop/peek işlemlerini gerçekleştirerek ideal yığınlar olur, geçerli parantezler ve minimum yığın, yığınlarla ilgili iki temel mülakat problemidir ve monotonik yığınlar, her öğeyi en fazla bir kez ekleyip çıkararak bir sonraki daha büyük öğe problemlerini O(n) zamanda çözer. Sırada Python'un deque yapısıyla kuyruklar oluşturmak ve kayan pencere maksimumunu çözmek var.

Sıkça Sorulan Sorular