PricingLoginStart free
Forberedelse til kodeintervjuer · leksjon

Implementering og bruksområder for stakk

Implementer en stakk med push/pop/peek, og løs deretter valid-parentheses, min-stack og evaluer omvendt polsk notasjon.

Leksjon 1 av 413 trinn

Implementering og bruksområder for stakk er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Datastrukturen stakk

En stakk er en datastruktur med sist inn, først ut (LIFO). Det siste elementet som legges på stakken, tas først av. Tenk på en stabel med tallerkener: De kan bare legge til eller fjerne fra toppen. De viktigste operasjonene er push (legge på toppen), pop (fjerne fra toppen) og peek (lese toppen uten å fjerne den). Alle tre er O(1) på en godt implementert stakk.

I Python fungerer en liste som en perfekt stakk: append er push, pop() er pop, og [-1] er peek.

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]

Stakk-klasse med Push, Pop, Peek, isEmpty

Å pakke listen inn i en klasse gir et ryddigere grensesnitt og hindrer utilsiktet bruk av operasjoner som ikke hører til stakken, for eksempel insert eller indeksering på andre posisjoner enn toppen. Dette er implementasjonen intervjuere forventer når de ber om å «implementere en stakk fra bunnen av».

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

Gyldige parenteser (LeetCode 20)

LeetCode 20 «Gyldige parenteser»: avgjør om en streng med parenteser er balansert. For hver åpningsparentes legges den på stakken. For hver lukkende parentes kontrolleres det at toppen av stakken er den tilsvarende åpningsparentesen; hvis ikke, eller hvis stakken er tom, returneres False. Hvis stakken er tom til slutt, er strengen gyldig. Dette er det klassiske første bruksområdet for en stakk i kodeintervjuer.

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

Minstakk (LeetCode 155)

LeetCode 155 «Minstakk»: utform en stakk som støtter push, pop, peek og getMin, alt i O(1). Trikset er å opprettholde en ekstra stakk som holder oversikt over minimumsverdien på hvert tidspunkt. Når en verdi legges på, legges den også på minimumsstakken hvis den nye verdien er <= det gjeldende minimumet (eller hvis minimumsstakken er tom). Når en verdi tas av, tas den også av minimumsstakken hvis den avlagte verdien er lik det gjeldende minimumet.

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

Evaluer omvendt polsk notasjon

LeetCode 150 «Evaluer omvendt polsk notasjon» (postfiks): operander legges på stakken; når en operator møter, tas to operander av, operatoren brukes, og resultatet legges på stakken. Rekkefølgen er viktig ved subtraksjon og divisjon: den første operanden som tas av, er høyre operand, og den andre er venstre.

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

Dekod streng (LeetCode 394)

LeetCode 394 «Dekod streng»: gitt en kodet streng som 3[a2[c]], utvid den til accaccacc. Bruk to stakker: én for repetisjonstall og én for oppsamlede strenger. Når et siffer møter, bygges hele tallet. Ved [ legges den gjeldende strengen og antallet på stakkene. Ved ] tas de av, og det gjeldende segmentet gjentas. Når en bokstav møter, legges den til i den gjeldende strengen.

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'

Daglige temperaturer (forhåndsvisning av monoton stakk)

LeetCode 739 «Daglige temperaturer»: finn for hver dag hvor mange dager det er til en varmere temperatur. En uttømmende løsning tar O(n²). Med en stakk går man gjennom temperaturene; for hver dag tas alle stakkoppføringer (dagindekser) med lavere temperatur enn dagens av stakken. Svaret for disse dagene er (today - popped_day). Den gjeldende dagen legges på stakken. Stakkoppføringene som blir igjen, fant aldri en varmere dag – svaret deres er 0.

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]

Stakk for DFS-gjennomløping

Kallstakken i rekursiv DFS kan erstattes med en eksplisitt stakk, slik at algoritmen blir iterativ. Legg roten på stakken; så lenge stakken ikke er tom, tas en node av, den behandles, og barna legges på stakken (høyre før venstre for behandling fra venstre mot høyre). Denne iterative DFS-en har samme virkemåte som rekursiv DFS, men unngår Pythons rekursjonsgrense for dype trær.

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]

Tids- og plasskompleksitet

Alle stakkoperasjoner (push, pop, peek, isEmpty) er amortisert O(1). Å bygge en stakk med n elementer tar O(n). Plassforbruket er O(n) i verste fall, når alle elementene lagres. I problemer som bruker en monoton stakk, legges hvert element på og tas av høyst én gang, noe som gir totalt O(n)-tid gjennom alle iterasjonene – ikke O(n²), slik en naiv lesning av den ytre løkken kan antyde.

# 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

Største rektangel i et histogram (forhåndsvisning)

LeetCode 84 «Største rektangel i et histogram» er den vanskeligste klassiske stakkoppgaven. For hver søyle strekker rektangelet den kan være anker for, seg mot venstre til en lavere søyle finnes, og mot høyre til en lavere søyle finnes. En monoton stakk holder oversikt over indekser for søyler i økende høydeorden. Når en lavere søyle oppdages, tas søyler av stakken, og rektangelet med høyden til den avlagte søylen beregnes. Stakken gir venstre og høyre grense i O(1) per fjerning.

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

Intervjustrategi for stakkproblemer

Stakkproblemer skjuler seg ofte som «behandle innenfra og ut» eller «finn det neste større/mindre elementet». Tegn på at en stakk kan være nyttig, er at De trenger det sist observerte elementet, matcher par (parenteser, tagger), eller ønsker O(n) for et problem som naivt krever nestede løkker med O(n²). Monotone stakker gjør særlig «finn det nærmeste større/mindre elementet for hvert element» om fra O(n²) til O(n).

I et intervju bør De formulere stakkens invariant tydelig: «Jeg opprettholder en stakk med indekser i avtakende høydeorden.»

Kort sjekk

Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: Python-lister implementerer push, pop og peek i O(1), noe som gjør dem til ideelle stakker, gyldige parenteser og minstakk er de to klassiske stakkproblemene i kodeintervjuer, og monotone stakker løser problemer med neste større element i O(n) ved å legge hvert element på og ta det av høyst én gang. I neste leksjon bygger vi køer med Pythons deque og løser maksimum i et glidende vindu.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
90
Leksjoner
360
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «Implementering og bruksområder for stakk» gratis?

Ja – hele teksten i «Implementering og bruksområder for stakk» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Implementering og bruksområder for stakk»?

Implementer en stakk med push/pop/peek, og løs deretter valid-parentheses, min-stack og evaluer omvendt polsk notasjon. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Implementering og bruksområder for stakk»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. Implementering og bruksområder for stakk
  2. Implementering av kø og deque
  3. Mønsteret med monoton stakk
  4. Gjensidig simulering av stakk og kø
← Tilbake til Forberedelse til kodeintervjuer