[CS 기초 #7] 스택과 큐: LIFO와 FIFO 완벽 이해

가장 많이 사용되는 자료구조! 브라우저의 뒤로가기, 프린터 대기열, 작업 스케줄링 등 우리 주변에 스택과 큐가 있습니다.

🎯 이 글을 읽고 나면

• 스택(Stack)과 큐(Queue)의 차이를 명확히 설명할 수 있습니다
• LIFO와 FIFO 개념을 이해하고 실생활 예시를 들 수 있습니다
• 스택과 큐를 직접 구현할 수 있습니다
• 브라우저 히스토리, BFS 등 실제 활용 사례를 이해합니다
• 상황에 맞는 자료구조를 선택할 수 있습니다

📚 사전 지식

• 배열(Array) 기초: 리스트의 기본 동작 (관련 글: 배열과 연결 리스트)
• Python 기초 문법: 클래스, 리스트 사용법
• 시간 복잡도: Big-O 표기법 기초 (모르셔도 됩니다!)

💡 핵심 개념 미리보기

스택(Stack)은 접시 쌓기처럼 “나중에 넣은 것이 먼저 나오는(LIFO)” 구조입니다. 브라우저 뒤로가기, 실행 취소 기능에 사용됩니다.

큐(Queue)는 줄 서기처럼 “먼저 넣은 것이 먼저 나오는(FIFO)” 구조입니다. 프린터 대기열, 작업 스케줄링에 사용됩니다.

이 두 자료구조는 단순하지만, 수많은 알고리즘의 기본이 됩니다!

---

📚 들어가며: 스택과 큐는 어디서 사용될까?

브라우저의 뒤로가기 버튼, 실행 취소(Ctrl+Z), 프린터 대기열… 이 모든 것들이 스택과 큐로 구현됩니다!

오늘은 가장 실용적인 자료구조인 스택(Stack)과 큐(Queue)를 깊이 있게 알아보겠습니다. 단순해 보이지만, 수많은 알고리즘과 시스템의 핵심이 되는 자료구조입니다!

📦 스택 (Stack) - LIFO

스택은 Last In First Out (LIFO) 원칙을 따르는 자료구조입니다. 마지막에 들어간 것이 먼저 나옵니다.

🔰 초보자를 위한 비유

스택은 접시 쌓기와 같습니다!

• 접시를 쌓을 때: 맨 위에 올립니다 (Push)
• 접시를 뺄 때: 맨 위에서 뺍니다 (Pop)
• 가장 나중에 쌓은 접시가 가장 먼저 나옵니다!

실생활 예시:

• 📚 책 더미: 맨 위 책만 쉽게 꺼낼 수 있음
• ↩️ 브라우저 뒤로가기: 가장 최근 페이지부터
• ⌨️ Ctrl+Z (실행 취소): 가장 최근 작업부터

graph TB
    subgraph "스택 동작"
        S1[TOP<br/>30]
        S2[20]
        S3[10]
        S4[BOTTOM]

        S1 --> S2
        S2 --> S3
        S3 --> S4
    end

    subgraph "연산"
        Push[Push: 위에 추가]
        Pop[Pop: 위에서 제거]
        Peek[Peek: 위 확인]
    end

    Push --> S1
    Pop --> S1
    Peek -.-> S1

스택 구현: 단계별로 이해하기

1단계: 기본 구조 만들기

class Stack:
    """가장 간단한 스택 구현"""

    def __init__(self):
        self.items = []  # 빈 리스트로 시작
        print("✅ 빈 스택을 만들었습니다!")

2단계: 추가 기능 (Push)

    def push(self, item):
        """맨 위에 추가 - O(1) 시간 복잡도"""
        self.items.append(item)
        print(f"📥 {item}을(를) 추가 → {self.items}")

3단계: 제거 기능 (Pop)

    def pop(self):
        """맨 위에서 제거 - O(1) 시간 복잡도"""
        if self.is_empty():
            print("❌ 스택이 비어있습니다!")
            return None

        item = self.items.pop()
        print(f"📤 {item}을(를) 제거 → {self.items}")
        return item

4단계: 보조 기능들

    def peek(self):
        """맨 위 요소만 확인 (제거하지 않음)"""
        if self.is_empty():
            return None
        return self.items[-1]  # 마지막 요소

    def is_empty(self):
        """스택이 비었는지 확인"""
        return len(self.items) == 0

    def size(self):
        """스택 크기 확인"""
        return len(self.items)

직접 사용해보기:

# 스택 생성
stack = Stack()

# 데이터 추가
stack.push(10)  # 📥 10을(를) 추가 → [10]
stack.push(20)  # 📥 20을(를) 추가 → [10, 20]
stack.push(30)  # 📥 30을(를) 추가 → [10, 20, 30]

print(f"현재 스택 크기: {stack.size()}")  # 3
print(f"맨 위 요소: {stack.peek()}")      # 30

# 데이터 제거 (LIFO - 나중에 넣은 것부터!)
stack.pop()  # 📤 30을(를) 제거 → [10, 20]
stack.pop()  # 📤 20을(를) 제거 → [10]

print(f"남은 요소: {stack.items}")  # [10]

연결 리스트 기반 스택

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedStack:
    """연결 리스트 기반 스택"""
    
    def __init__(self):
        self.top = None
        self._size = 0
    
    def push(self, item):
        """맨 위에 추가 - O(1)"""
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1
    
    def pop(self):
        """맨 위 제거 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        
        data = self.top.data
        self.top = self.top.next
        self._size -= 1
        return data
    
    def peek(self):
        """맨 위 확인 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.top.data
    
    def is_empty(self):
        return self.top is None
    
    def size(self):
        return self._size

🎯 스택의 활용

1. 괄호 검증

def is_valid_parentheses(s):
    """괄호의 유효성 검사"""
    stack = Stack()
    pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    
    for char in s:
        if char in pairs:  # 여는 괄호
            stack.push(char)
        elif char in pairs.values():  # 닫는 괄호
            if stack.is_empty():
                return False
            
            last_open = stack.pop()
            if pairs[last_open] != char:
                return False
    
    return stack.is_empty()

# 테스트
test_cases = [
    "()",
    "()[]{}",
    "(]",
    "([)]",
    "{[()]}",
    "((()))"
]

for test in test_cases:
    result = is_valid_parentheses(test)
    print(f"{test:10} → {result}")

2. 후위 표기법 계산

def evaluate_postfix(expression):
    """후위 표기법 수식 계산
    예: "2 3 + 4 *" = (2 + 3) * 4 = 20
    """
    stack = Stack()
    tokens = expression.split()
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            # 연산자일 경우 두 개의 피연산자 pop
            b = stack.pop()
            a = stack.pop()
            
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(int(a / b))  # 정수 나눗셈
        else:
            # 숫자일 경우 push
            stack.push(int(token))
    
    return stack.pop()

# 중위 표기법을 후위 표기법으로 변환
def infix_to_postfix(expression):
    """중위 표기법 → 후위 표기법 변환"""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = Stack()
    postfix = []
    tokens = expression.split()
    
    for token in tokens:
        if token.isdigit():
            postfix.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.peek() != '(':
                postfix.append(stack.pop())
            stack.pop()  # '(' 제거
        else:  # 연산자
            while (not stack.is_empty() and 
                   stack.peek() != '(' and
                   stack.peek() in precedence and
                   precedence[stack.peek()] >= precedence[token]):
                postfix.append(stack.pop())
            stack.push(token)
    
    while not stack.is_empty():
        postfix.append(stack.pop())
    
    return ' '.join(postfix)

# 테스트
infix = "2 + 3 * 4"
postfix = infix_to_postfix(infix)
result = evaluate_postfix(postfix)
print(f"중위: {infix}")
print(f"후위: {postfix}")
print(f"결과: {result}")

3. 함수 호출 스택 시뮬레이션

class CallStack:
    """함수 호출 스택 시뮬레이션"""
    
    def __init__(self):
        self.stack = Stack()
        self.depth = 0
    
    def call(self, func_name, params=None):
        """함수 호출"""
        frame = {
            'function': func_name,
            'params': params,
            'depth': self.depth
        }
        self.stack.push(frame)
        self.depth += 1
        print(f"{'  ' * frame['depth']}→ 호출: {func_name}({params})")
    
    def return_from(self, result=None):
        """함수 반환"""
        if not self.stack.is_empty():
            frame = self.stack.pop()
            self.depth -= 1
            print(f"{'  ' * frame['depth']}← 반환: {frame['function']} = {result}")
            return result
    
    def print_stack_trace(self):
        """스택 추적 출력"""
        print("\n=== Stack Trace ===")
        temp = []
        while not self.stack.is_empty():
            frame = self.stack.pop()
            temp.append(frame)
            print(f"  at {frame['function']}({frame['params']})")
        
        # 스택 복원
        for frame in reversed(temp):
            self.stack.push(frame)

# 재귀 함수 실행 시뮬레이션
def simulate_factorial(n, call_stack):
    """팩토리얼 재귀 시뮬레이션"""
    call_stack.call('factorial', n)
    
    if n <= 1:
        call_stack.return_from(1)
        return 1
    else:
        result = n * simulate_factorial(n - 1, call_stack)
        call_stack.return_from(result)
        return result

cs = CallStack()
result = simulate_factorial(5, cs)
print(f"\n최종 결과: {result}")

4. 브라우저 히스토리

class BrowserHistory:
    """브라우저 방문 기록 관리"""
    
    def __init__(self):
        self.back_stack = Stack()
        self.forward_stack = Stack()
        self.current_page = None
    
    def visit(self, url):
        """새 페이지 방문"""
        if self.current_page:
            self.back_stack.push(self.current_page)
        
        self.current_page = url
        # 새 페이지 방문 시 forward 스택 초기화
        self.forward_stack = Stack()
        print(f"방문: {url}")
    
    def back(self):
        """뒤로 가기"""
        if not self.back_stack.is_empty():
            self.forward_stack.push(self.current_page)
            self.current_page = self.back_stack.pop()
            print(f"뒤로: {self.current_page}")
        else:
            print("뒤로 갈 페이지가 없습니다")
    
    def forward(self):
        """앞으로 가기"""
        if not self.forward_stack.is_empty():
            self.back_stack.push(self.current_page)
            self.current_page = self.forward_stack.pop()
            print(f"앞으로: {self.current_page}")
        else:
            print("앞으로 갈 페이지가 없습니다")

# 브라우저 시뮬레이션
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("stackoverflow.com")
browser.visit("github.com")
browser.back()
browser.back()
browser.forward()
browser.visit("leetcode.com")
browser.back()

📋 큐 (Queue) - FIFO

큐는 First In First Out (FIFO) 원칙을 따르는 자료구조입니다. 먼저 들어간 것이 먼저 나옵니다.

graph LR
    subgraph "큐 동작"
        Front[Front] --> Q1[10]
        Q1 --> Q2[20]
        Q2 --> Q3[30]
        Q3 --> Rear[Rear]
    end
    
    Enqueue[Enqueue] --> Rear
    Dequeue[Dequeue] --> Front

큐 구현

from collections import deque

class Queue:
    """덱(deque) 기반 큐 구현"""
    
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """뒤에 추가 - O(1)"""
        self.items.append(item)
    
    def dequeue(self):
        """앞에서 제거 - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()
    
    def front(self):
        """맨 앞 요소 확인 - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[0]
    
    def is_empty(self):
        """비어있는지 확인 - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """크기 반환 - O(1)"""
        return len(self.items)
    
    def __str__(self):
        return f"Queue({list(self.items)})"

# 큐 사용 예시
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(f"큐: {queue}")
print(f"Dequeue: {queue.dequeue()}")
print(f"Front: {queue.front()}")
print(f"큐: {queue}")

원형 큐 (Circular Queue)

class CircularQueue:
    """고정 크기 원형 큐"""
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0
    
    def enqueue(self, item):
        """추가 - O(1)"""
        if self.is_full():
            raise OverflowError("Queue is full")
        
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1
    
    def dequeue(self):
        """제거 - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        
        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item
    
    def is_empty(self):
        return self.size == 0
    
    def is_full(self):
        return self.size == self.capacity
    
    def __str__(self):
        if self.is_empty():
            return "CircularQueue([])"
        
        result = []
        index = self.front
        for _ in range(self.size):
            result.append(self.queue[index])
            index = (index + 1) % self.capacity
        
        return f"CircularQueue({result})"

# 원형 큐 테스트
cq = CircularQueue(5)
for i in range(1, 5):
    cq.enqueue(i * 10)
print(f"원형 큐: {cq}")

cq.dequeue()
cq.dequeue()
cq.enqueue(50)
cq.enqueue(60)
print(f"원형 큐: {cq}")

🎯 큐의 활용

1. BFS (너비 우선 탐색)

from collections import deque

class Graph:
    """그래프 BFS 구현"""
    
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        """간선 추가"""
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)
    
    def bfs(self, start):
        """너비 우선 탐색"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            if vertex in self.graph:
                for neighbor in self.graph[vertex]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        
        return result
    
    def shortest_path(self, start, end):
        """최단 경로 찾기"""
        if start == end:
            return [start]
        
        visited = set()
        queue = deque([(start, [start])])
        visited.add(start)
        
        while queue:
            vertex, path = queue.popleft()
            
            if vertex in self.graph:
                for neighbor in self.graph[vertex]:
                    if neighbor == end:
                        return path + [neighbor]
                    
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, path + [neighbor]))
        
        return None  # 경로 없음

# 그래프 테스트
g = Graph()
edges = [
    ('A', 'B'), ('A', 'C'),
    ('B', 'D'), ('B', 'E'),
    ('C', 'F'), ('E', 'F')
]

for u, v in edges:
    g.add_edge(u, v)

print(f"BFS 순회: {g.bfs('A')}")
print(f"A→F 최단 경로: {g.shortest_path('A', 'F')}")

2. 프로세스 스케줄링

class ProcessScheduler:
    """라운드 로빈 스케줄러"""
    
    def __init__(self, time_quantum):
        self.time_quantum = time_quantum
        self.ready_queue = Queue()
        self.current_time = 0
        self.completed = []
    
    def add_process(self, process_id, burst_time):
        """프로세스 추가"""
        process = {
            'id': process_id,
            'burst_time': burst_time,
            'remaining_time': burst_time,
            'wait_time': 0,
            'turnaround_time': 0
        }
        self.ready_queue.enqueue(process)
    
    def run(self):
        """스케줄링 실행"""
        print(f"라운드 로빈 스케줄링 (Time Quantum: {self.time_quantum})")
        print("-" * 50)
        
        while not self.ready_queue.is_empty():
            process = self.ready_queue.dequeue()
            
            # 실행 시간 계산
            execution_time = min(self.time_quantum, process['remaining_time'])
            process['remaining_time'] -= execution_time
            self.current_time += execution_time
            
            print(f"시간 {self.current_time-execution_time:2d}-{self.current_time:2d}: "
                  f"프로세스 {process['id']} 실행 (남은 시간: {process['remaining_time']})")
            
            if process['remaining_time'] == 0:
                # 프로세스 완료
                process['turnaround_time'] = self.current_time
                self.completed.append(process)
                print(f"         프로세스 {process['id']} 완료!")
            else:
                # 다시 큐에 추가
                self.ready_queue.enqueue(process)
    
    def print_statistics(self):
        """통계 출력"""
        print("\n=== 스케줄링 결과 ===")
        total_turnaround = 0
        
        for process in self.completed:
            print(f"프로세스 {process['id']}: "
                  f"실행시간={process['burst_time']}, "
                  f"완료시간={process['turnaround_time']}")
            total_turnaround += process['turnaround_time']
        
        avg_turnaround = total_turnaround / len(self.completed)
        print(f"\n평균 반환 시간: {avg_turnaround:.2f}")

# 스케줄러 테스트
scheduler = ProcessScheduler(time_quantum=2)
scheduler.add_process('P1', 5)
scheduler.add_process('P2', 3)
scheduler.add_process('P3', 8)
scheduler.add_process('P4', 2)
scheduler.run()
scheduler.print_statistics()

3. 캐시 구현 (LRU)

from collections import deque

class LRUCache:
    """LRU 캐시 (큐 활용)"""
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.order = deque()
    
    def get(self, key):
        """값 조회"""
        if key in self.cache:
            # 최근 사용으로 업데이트
            self.order.remove(key)
            self.order.append(key)
            print(f"캐시 히트: {key} = {self.cache[key]}")
            return self.cache[key]
        
        print(f"캐시 미스: {key}")
        return -1
    
    def put(self, key, value):
        """값 저장"""
        if key in self.cache:
            # 기존 키 업데이트
            self.order.remove(key)
        elif len(self.cache) >= self.capacity:
            # 가장 오래된 항목 제거
            oldest = self.order.popleft()
            del self.cache[oldest]
            print(f"제거: {oldest}")
        
        self.cache[key] = value
        self.order.append(key)
        print(f"저장: {key} = {value}")
    
    def display(self):
        """현재 캐시 상태"""
        print(f"캐시: {list(self.order)} → {self.cache}")

# LRU 캐시 테스트
lru = LRUCache(3)
lru.put(1, 'A')
lru.put(2, 'B')
lru.put(3, 'C')
lru.display()

lru.get(1)
lru.put(4, 'D')
lru.display()

lru.get(2)
lru.get(3)
lru.put(5, 'E')
lru.display()

🔀 덱 (Deque) - 양방향 큐

덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.

class Deque:
    """덱 구현"""
    
    def __init__(self):
        self.items = []
    
    def add_front(self, item):
        """앞에 추가 - O(1)"""
        self.items.insert(0, item)
    
    def add_rear(self, item):
        """뒤에 추가 - O(1)"""
        self.items.append(item)
    
    def remove_front(self):
        """앞에서 제거 - O(1)"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.pop(0)
    
    def remove_rear(self):
        """뒤에서 제거 - O(1)"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.pop()
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# 회문 검사에 덱 활용
def is_palindrome(s):
    """회문 검사"""
    deque = Deque()
    
    # 문자만 덱에 추가 (대소문자 구분 X)
    for char in s.lower():
        if char.isalnum():
            deque.add_rear(char)
    
    # 양쪽에서 비교
    while deque.size() > 1:
        if deque.remove_front() != deque.remove_rear():
            return False
    
    return True

# 테스트
test_strings = [
    "racecar",
    "A man, a plan, a canal: Panama",
    "hello",
    "Was it a car or a cat I saw?"
]

for s in test_strings:
    result = is_palindrome(s)
    print(f"'{s[:20]}...' → {result}")

🎯 우선순위 큐 (Priority Queue)

우선순위가 높은 요소가 먼저 나오는 큐입니다.

import heapq

class PriorityQueue:
    """힙 기반 우선순위 큐"""
    
    def __init__(self):
        self.heap = []
        self.index = 0  # 동일 우선순위 처리용
    
    def push(self, item, priority):
        """추가 - O(log n)"""
        # 최소 힙이므로 음수로 변환 (낮은 값이 높은 우선순위)
        heapq.heappush(self.heap, (priority, self.index, item))
        self.index += 1
    
    def pop(self):
        """제거 - O(log n)"""
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return heapq.heappop(self.heap)[2]
    
    def peek(self):
        """확인 - O(1)"""
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return self.heap[0][2]
    
    def is_empty(self):
        return len(self.heap) == 0

# 작업 스케줄링 예제
class TaskScheduler:
    """우선순위 기반 작업 스케줄러"""
    
    def __init__(self):
        self.pq = PriorityQueue()
    
    def add_task(self, task_name, priority):
        """작업 추가 (낮은 숫자 = 높은 우선순위)"""
        self.pq.push(task_name, priority)
        print(f"작업 추가: {task_name} (우선순위: {priority})")
    
    def execute_tasks(self):
        """작업 실행"""
        print("\n작업 실행 순서:")
        while not self.pq.is_empty():
            task = self.pq.pop()
            print(f"  실행: {task}")

# 테스트
scheduler = TaskScheduler()
scheduler.add_task("버그 수정", 1)
scheduler.add_task("기능 개발", 3)
scheduler.add_task("긴급 패치", 0)
scheduler.add_task("문서 작성", 4)
scheduler.add_task("코드 리뷰", 2)
scheduler.execute_tasks()

💡 실전 문제 풀이

문제 1: 스택으로 큐 구현

class QueueUsingStacks:
    """두 개의 스택으로 큐 구현"""
    
    def __init__(self):
        self.stack1 = Stack()  # 입력용
        self.stack2 = Stack()  # 출력용
    
    def enqueue(self, item):
        """추가 - O(1)"""
        self.stack1.push(item)
    
    def dequeue(self):
        """제거 - Amortized O(1)"""
        # stack2가 비어있으면 stack1의 모든 요소를 이동
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())
        
        if self.stack2.is_empty():
            raise IndexError("Queue is empty")
        
        return self.stack2.pop()
    
    def is_empty(self):
        return self.stack1.is_empty() and self.stack2.is_empty()

# 테스트
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(f"Dequeue: {q.dequeue()}")  # 1
q.enqueue(4)
print(f"Dequeue: {q.dequeue()}")  # 2
print(f"Dequeue: {q.dequeue()}")  # 3

문제 2: 슬라이딩 윈도우 최대값

from collections import deque

def max_sliding_window(nums, k):
    """슬라이딩 윈도우의 최대값 찾기"""
    if not nums:
        return []
    
    result = []
    dq = deque()  # 인덱스 저장
    
    for i, num in enumerate(nums):
        # 윈도우 벗어난 요소 제거
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 현재 요소보다 작은 요소 제거
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # 윈도우가 완성되면 최대값 추가
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# 테스트
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
result = max_sliding_window(nums, k)
print(f"배열: {nums}")
print(f"k={k} 슬라이딩 윈도우 최대값: {result}")

문제 3: 주식 스팬

def calculate_span(prices):
    """주식 가격 스팬 계산
    스팬 = 현재 가격보다 작거나 같은 연속된 이전 날짜 수
    """
    n = len(prices)
    span = [1] * n
    stack = Stack()  # (인덱스) 저장
    
    for i in range(n):
        # 현재 가격보다 작은 이전 가격들 제거
        while not stack.is_empty() and prices[stack.peek()] <= prices[i]:
            stack.pop()
        
        # 스팬 계산
        if stack.is_empty():
            span[i] = i + 1
        else:
            span[i] = i - stack.peek()
        
        stack.push(i)
    
    return span

# 테스트
prices = [100, 80, 60, 70, 60, 75, 85]
span = calculate_span(prices)
print("주식 가격과 스팬:")
for i in range(len(prices)):
    print(f"Day {i+1}: 가격={prices[i]:3}, 스팬={span[i]}")

🎯 핵심 정리

꼭 기억해야 할 5가지

1. 스택은 LIFO, 큐는 FIFO
2. 스택은 재귀, 백트래킹에 활용
3. 큐는 BFS, 스케줄링에 활용
4. 덱은 양방향 삽입/삭제 가능
5. 우선순위 큐는 힙으로 구현

실무 활용 팁

• 함수 호출, 실행 취소 → 스택
• 대기열, 버퍼 → 큐
• 최대/최소값 빠른 접근 → 우선순위 큐
• 양방향 처리 → 덱

📚 추가 학습 자료

추천 문제

• LeetCode: Valid Parentheses, Min Stack, Implement Queue using Stacks
• 프로그래머스: 프린터, 다리를 지나는 트럭, 주식가격
• 백준: 10828(스택), 18258(큐2), 1021(회전하는 큐)

심화 주제

• Monotonic Stack/Queue
• Double-ended Priority Queue
• Lock-free Queue

🚀 다음 시간 예고

다음 포스트에서는 트리(Tree) 구조를 다룹니다. 이진 트리부터 B-트리까지, 계층적 데이터를 다루는 방법을 알아보겠습니다!

---

📌 시리즈 네비게이션

순서	제목	링크
6	배열과 연결 리스트	← 이전 글
7	스택과 큐: LIFO와 FIFO의 활용 ✅	현재 글
8	트리 구조: 이진 트리부터 B-트리까지	다음 글 →

📋 전체 시리즈 목차 보기

기초 이론편

1. CS 입문 ✅
2. 컴퓨터 구조 ✅
3. 이진수와 논리 게이트 ✅
4. 운영체제 기초 ✅
5. 네트워크 기초 ✅

자료구조편

1. 배열과 연결 리스트 ✅
2. 스택과 큐 ✅
3. 트리 구조
4. 그래프
5. 해시 테이블

알고리즘편

1. 복잡도 분석
2. 정렬 알고리즘
3. 탐색 알고리즘
4. 동적 계획법
5. 그리디와 분할정복

실무 응용편

1. 데이터베이스 이론
2. 소프트웨어 공학
3. 보안 기초
4. 분산 시스템
5. CS 종합과 면접 준비