การสร้างสแตกและการประยุกต์ใช้

โครงสร้างข้อมูลสแตก

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

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

วงเล็บที่ถูกต้อง (LeetCode 20)

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

สแตกค่าต่ำสุด (LeetCode 155)

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

การประเมินสัญกรณ์โปแลนด์แบบย้อนกลับ

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

การถอดรหัสสตริง (LeetCode 394)

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'

อุณหภูมิรายวัน (เกริ่นนำสแตกแบบโมโนโทนิก)

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

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]

ความซับซ้อนด้านเวลาและหน่วยความจำ

# 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

สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม (เกริ่นนำ)

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

กลยุทธ์การสัมภาษณ์สำหรับโจทย์สแตก

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน