03_stack_queue.py

Download
python 320 lines 9.1 KB 
  1"""
  2μŠ€νƒκ³Ό 큐 ν™œμš©
  3Stack and Queue Applications
  4
  5μŠ€νƒ(LIFO)κ³Ό 큐(FIFO) 자료ꡬ쑰λ₯Ό ν™œμš©ν•œ μ•Œκ³ λ¦¬μ¦˜ μ˜ˆμ œμž…λ‹ˆλ‹€.
  6"""
  7
  8from collections import deque
  9from typing import List, Optional
 10
 11
 12# =============================================================================
 13# μŠ€νƒ κ΅¬ν˜„ (리슀트 기반)
 14# =============================================================================
 15class Stack:
 16    """리슀트 기반 μŠ€νƒ κ΅¬ν˜„"""
 17
 18    def __init__(self):
 19        self._items = []
 20
 21    def push(self, item):
 22        self._items.append(item)
 23
 24    def pop(self):
 25        if not self.is_empty():
 26            return self._items.pop()
 27        raise IndexError("Stack is empty")
 28
 29    def peek(self):
 30        if not self.is_empty():
 31            return self._items[-1]
 32        raise IndexError("Stack is empty")
 33
 34    def is_empty(self):
 35        return len(self._items) == 0
 36
 37    def size(self):
 38        return len(self._items)
 39
 40
 41# =============================================================================
 42# 큐 κ΅¬ν˜„ (deque 기반)
 43# =============================================================================
 44class Queue:
 45    """deque 기반 큐 κ΅¬ν˜„ (O(1) μ—°μ‚°)"""
 46
 47    def __init__(self):
 48        self._items = deque()
 49
 50    def enqueue(self, item):
 51        self._items.append(item)
 52
 53    def dequeue(self):
 54        if not self.is_empty():
 55            return self._items.popleft()
 56        raise IndexError("Queue is empty")
 57
 58    def front(self):
 59        if not self.is_empty():
 60            return self._items[0]
 61        raise IndexError("Queue is empty")
 62
 63    def is_empty(self):
 64        return len(self._items) == 0
 65
 66    def size(self):
 67        return len(self._items)
 68
 69
 70# =============================================================================
 71# 1. κ΄„ν˜Έ 검증 (Valid Parentheses)
 72# =============================================================================
 73def is_valid_parentheses(s: str) -> bool:
 74    """
 75    κ΄„ν˜Έ λ¬Έμžμ—΄μ˜ μœ νš¨μ„± 검사
 76    μ‹œκ°„λ³΅μž‘λ„: O(n), κ³΅κ°„λ³΅μž‘λ„: O(n)
 77    """
 78    stack = []
 79    mapping = {')': '(', '}': '{', ']': '['}
 80
 81    for char in s:
 82        if char in mapping:
 83            # λ‹«λŠ” κ΄„ν˜ΈμΌ λ•Œ
 84            if not stack or stack[-1] != mapping[char]:
 85                return False
 86            stack.pop()
 87        else:
 88            # μ—¬λŠ” κ΄„ν˜ΈμΌ λ•Œ
 89            stack.append(char)
 90
 91    return len(stack) == 0
 92
 93
 94# =============================================================================
 95# 2. ν›„μœ„ ν‘œκΈ°λ²• 계산 (Postfix Evaluation)
 96# =============================================================================
 97def evaluate_postfix(expression: str) -> int:
 98    """
 99    ν›„μœ„ ν‘œκΈ°λ²• μˆ˜μ‹ 계산
100    예: "2 3 + 4 *" = (2 + 3) * 4 = 20
101    """
102    stack = []
103    operators = {'+', '-', '*', '/'}
104
105    for token in expression.split():
106        if token in operators:
107            b = stack.pop()
108            a = stack.pop()
109            if token == '+':
110                stack.append(a + b)
111            elif token == '-':
112                stack.append(a - b)
113            elif token == '*':
114                stack.append(a * b)
115            elif token == '/':
116                stack.append(int(a / b))  # μ •μˆ˜ λ‚˜λˆ—μ…ˆ
117        else:
118            stack.append(int(token))
119
120    return stack[0]
121
122
123# =============================================================================
124# 3. λ‹€μŒ 큰 μš”μ†Œ (Next Greater Element)
125# =============================================================================
126def next_greater_element(arr: List[int]) -> List[int]:
127    """
128    각 μš”μ†Œμ˜ 였λ₯Έμͺ½μ—μ„œ 처음으둜 더 큰 μš”μ†Œ μ°ΎκΈ°
129    μ—†μœΌλ©΄ -1 λ°˜ν™˜
130    μ‹œκ°„λ³΅μž‘λ„: O(n), κ³΅κ°„λ³΅μž‘λ„: O(n)
131    """
132    n = len(arr)
133    result = [-1] * n
134    stack = []  # 인덱슀 μ €μž₯
135
136    for i in range(n):
137        # ν˜„μž¬ μš”μ†Œκ°€ μŠ€νƒ top보닀 크면
138        while stack and arr[i] > arr[stack[-1]]:
139            idx = stack.pop()
140            result[idx] = arr[i]
141        stack.append(i)
142
143    return result
144
145
146# =============================================================================
147# 4. 일일 μ˜¨λ„ (Daily Temperatures)
148# =============================================================================
149def daily_temperatures(temperatures: List[int]) -> List[int]:
150    """
151    더 λ”°λœ»ν•œ λ‚ κΉŒμ§€ 며칠을 κΈ°λ‹€λ €μ•Ό ν•˜λŠ”μ§€ 계산
152    μ‹œκ°„λ³΅μž‘λ„: O(n), κ³΅κ°„λ³΅μž‘λ„: O(n)
153    """
154    n = len(temperatures)
155    result = [0] * n
156    stack = []  # (인덱슀) μ €μž₯
157
158    for i in range(n):
159        while stack and temperatures[i] > temperatures[stack[-1]]:
160            prev_idx = stack.pop()
161            result[prev_idx] = i - prev_idx
162        stack.append(i)
163
164    return result
165
166
167# =============================================================================
168# 5. μ΅œμ†Œ μŠ€νƒ (Min Stack)
169# =============================================================================
170class MinStack:
171    """
172    O(1) μ‹œκ°„μ— μ΅œμ†Ÿκ°’μ„ λ°˜ν™˜ν•˜λŠ” μŠ€νƒ
173    """
174
175    def __init__(self):
176        self.stack = []
177        self.min_stack = []
178
179    def push(self, val: int):
180        self.stack.append(val)
181        if not self.min_stack or val <= self.min_stack[-1]:
182            self.min_stack.append(val)
183
184    def pop(self):
185        if self.stack:
186            val = self.stack.pop()
187            if val == self.min_stack[-1]:
188                self.min_stack.pop()
189
190    def top(self) -> int:
191        return self.stack[-1] if self.stack else None
192
193    def get_min(self) -> int:
194        return self.min_stack[-1] if self.min_stack else None
195
196
197# =============================================================================
198# 6. 큐 두 개둜 μŠ€νƒ κ΅¬ν˜„
199# =============================================================================
200class StackUsingQueues:
201    """두 개의 큐둜 μŠ€νƒ κ΅¬ν˜„"""
202
203    def __init__(self):
204        self.q1 = deque()
205        self.q2 = deque()
206
207    def push(self, x: int):
208        self.q2.append(x)
209        while self.q1:
210            self.q2.append(self.q1.popleft())
211        self.q1, self.q2 = self.q2, self.q1
212
213    def pop(self) -> int:
214        return self.q1.popleft() if self.q1 else None
215
216    def top(self) -> int:
217        return self.q1[0] if self.q1 else None
218
219    def empty(self) -> bool:
220        return len(self.q1) == 0
221
222
223# =============================================================================
224# 7. μŠ¬λΌμ΄λ”© μœˆλ„μš° μ΅œλŒ“κ°’ (Monotonic Queue)
225# =============================================================================
226def max_sliding_window(nums: List[int], k: int) -> List[int]:
227    """
228    크기 k인 μŠ¬λΌμ΄λ”© μœˆλ„μš°μ—μ„œ μ΅œλŒ“κ°’ μ°ΎκΈ°
229    단쑰 κ°μ†Œ 큐(Monotonic Deque) μ‚¬μš©
230    μ‹œκ°„λ³΅μž‘λ„: O(n), κ³΅κ°„λ³΅μž‘λ„: O(k)
231    """
232    result = []
233    dq = deque()  # 인덱슀 μ €μž₯, 값은 단쑰 κ°μ†Œ
234
235    for i in range(len(nums)):
236        # μœˆλ„μš° λ²”μœ„ λ°–μ˜ 인덱슀 제거
237        while dq and dq[0] < i - k + 1:
238            dq.popleft()
239
240        # ν˜„μž¬ 값보닀 μž‘μ€ κ°’λ“€ 제거 (λ’€μ—μ„œλΆ€ν„°)
241        while dq and nums[dq[-1]] < nums[i]:
242            dq.pop()
243
244        dq.append(i)
245
246        # μœˆλ„μš°κ°€ μ™„μ„±λ˜λ©΄ μ΅œλŒ“κ°’ μΆ”κ°€
247        if i >= k - 1:
248            result.append(nums[dq[0]])
249
250    return result
251
252
253# =============================================================================
254# ν…ŒμŠ€νŠΈ
255# =============================================================================
256def main():
257    print("=" * 60)
258    print("μŠ€νƒκ³Ό 큐 ν™œμš© 예제")
259    print("=" * 60)
260
261    # 1. κ΄„ν˜Έ 검증
262    print("\n[1] κ΄„ν˜Έ 검증")
263    test_cases = ["()", "()[]{}", "(]", "([)]", "{[]}"]
264    for tc in test_cases:
265        result = is_valid_parentheses(tc)
266        print(f"    '{tc}' -> {result}")
267
268    # 2. ν›„μœ„ ν‘œκΈ°λ²• 계산
269    print("\n[2] ν›„μœ„ ν‘œκΈ°λ²• 계산")
270    expressions = ["2 3 +", "2 3 + 4 *", "5 1 2 + 4 * + 3 -"]
271    for expr in expressions:
272        result = evaluate_postfix(expr)
273        print(f"    '{expr}' = {result}")
274
275    # 3. λ‹€μŒ 큰 μš”μ†Œ
276    print("\n[3] λ‹€μŒ 큰 μš”μ†Œ (Next Greater Element)")
277    arr = [4, 5, 2, 25]
278    result = next_greater_element(arr)
279    print(f"    λ°°μ—΄: {arr}")
280    print(f"    κ²°κ³Ό: {result}")
281
282    # 4. 일일 μ˜¨λ„
283    print("\n[4] 일일 μ˜¨λ„")
284    temps = [73, 74, 75, 71, 69, 72, 76, 73]
285    result = daily_temperatures(temps)
286    print(f"    μ˜¨λ„: {temps}")
287    print(f"    λŒ€κΈ° 일수: {result}")
288
289    # 5. μ΅œμ†Œ μŠ€νƒ
290    print("\n[5] μ΅œμ†Œ μŠ€νƒ (MinStack)")
291    min_stack = MinStack()
292    operations = [
293        ("push", 3), ("push", 5), ("getMin", None),
294        ("push", 2), ("push", 1), ("getMin", None),
295        ("pop", None), ("getMin", None)
296    ]
297    for op, val in operations:
298        if op == "push":
299            min_stack.push(val)
300            print(f"    push({val})")
301        elif op == "pop":
302            min_stack.pop()
303            print(f"    pop()")
304        elif op == "getMin":
305            print(f"    getMin() = {min_stack.get_min()}")
306
307    # 6. μŠ¬λΌμ΄λ”© μœˆλ„μš° μ΅œλŒ“κ°’
308    print("\n[6] μŠ¬λΌμ΄λ”© μœˆλ„μš° μ΅œλŒ“κ°’")
309    nums = [1, 3, -1, -3, 5, 3, 6, 7]
310    k = 3
311    result = max_sliding_window(nums, k)
312    print(f"    λ°°μ—΄: {nums}, k={k}")
313    print(f"    각 μœˆλ„μš° μ΅œλŒ“κ°’: {result}")
314
315    print("\n" + "=" * 60)
316
317
318if __name__ == "__main__":
319    main()