[스택과 큐의 활용 사례] 꼭 알아야 할 자료구조 활용법

공부를 하다보면 기본 개념이 정리가 되지 않아 헷갈리는 경우가 많습니다

스택과 큐는 사실 프로그램 개발할 때 적용하는 기본 원리인 것 같아요 아직 제대로 된 프로젝트를 혼자 구현해볼 수 있는 정도는 아니지만 그래도 기본 개념은 항상 머릿속에 적립해놔야할 것!

---

1. 스택(Stack)이란?

• 스택은 LIFO(Last In, First Out) 구조로, 마지막에 들어간 데이터가 가장 먼저 나옵니다.

• 비유: 접시 쌓기 → 가장 위에 있는 접시를 먼저 꺼냄.

스택의 동작

1. Push: 데이터를 스택에 추가.

2. Pop: 가장 위의 데이터를 제거.

3. Peek/Top: 가장 위의 데이터를 확인.

2. 스택의 활용 사례

1) 함수 호출 관리 (Call Stack)

• 설명: 함수 호출 정보를 스택에 저장하여 실행 순서를 관리.

• 예: 재귀 함수에서 호출된 함수가 종료될 때, 호출 순서대로 스택에서 제거됩니다.

2) 문자열의 괄호 검사

• 설명: 올바른 괄호(() {} [])인지 확인.

• 예: 소스 코드의 구문 오류 검사.

def is_valid_parentheses(string):
    stack = []
    for char in string:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack:
                return False
            top = stack.pop()
            if char == ")" and top != "(":
                return False
            if char == "}" and top != "{":
                return False
            if char == "]" and top != "[":
                return False
    return not stack

3) 웹 브라우저의 뒤로가기

• 설명: 방문한 웹페이지를 스택에 저장하여 뒤로가기를 구현.

• 예: 사용자가 페이지 A → B → C를 방문.

• “뒤로가기” 버튼을 누르면 가장 최근 페이지 C를 스택에서 제거하고 B로 이동.

4) 문서 편집기에서 실행 취소 (Undo)

• 설명: 편집 기록을 스택에 저장하여 실행 취소를 구현.

• 예: “실행 취소(Undo)”를 누르면 가장 최근 작업을 스택에서 제거하고 이전 상태로 복구.

5) 깊이 우선 탐색 (DFS)

• 설명: 그래프 탐색 알고리즘에서 DFS는 스택을 사용하여 경로를 추적.

• 예: 미로 탐색, 네트워크 경로 분석.

3. 큐(Queue)란?

• 큐는 FIFO(First In, First Out) 구조로, 먼저 들어간 데이터가 가장 먼저 나옵니다.

• 비유: 줄 서기 → 먼저 온 사람이 먼저 나감.

큐의 동작

1. Enqueue: 데이터를 큐에 추가.

2. Dequeue: 큐의 앞에서 데이터를 제거.

3. Peek/Front: 큐의 앞에 있는 데이터를 확인.

4. 큐의 활용 사례

1) 프로세스 관리 (CPU 스케줄링)

• 설명: 운영체제에서 작업을 처리할 때 대기열을 사용하여 작업 순서를 관리.

• 예: FCFS (First Come, First Serve) 방식으로 작업 처리.

2) 네트워크 패킷 처리

• 설명: 네트워크에서 들어온 데이터 패킷을 큐에 저장하고 순서대로 처리.

• 예: 라우터가 데이터 패킷을 수신 → 큐에 저장 → 순차적으로 처리.

3) 프린터 작업 관리

• 설명: 프린터에 여러 작업이 들어오면 작업 요청을 큐에 저장하고 순서대로 처리.

• 예: 사용자 A → B → C가 프린트를 요청하면 A 작업이 끝난 후 B, C 작업을 순서대로 처리.

4) BFS(너비 우선 탐색)

• 설명: 그래프 탐색에서 BFS는 큐를 사용하여 레벨 순으로 탐색.

• 예: 최단 경로 찾기.

5) 대기열 시스템

• 설명: 고객 서비스나 병원 접수 시스템에서 대기열 관리.

• 예: 고객 번호표 발급 시스템.

6) 캐시 구현 (FIFO 캐시)

• 설명: 제한된 메모리 내에서 오래된 데이터를 제거하고 새 데이터를 추가.

• 예: FIFO 알고리즘 기반 캐시 시스템.

6. 스택과 큐의 Python 구현 예시

스택 구현 (Python)

stack = []

# Push
stack.append(1)
stack.append(2)

# Pop
print(stack.pop())  # 출력: 2
print(stack.pop())  # 출력: 1

큐 구현 (Python, collections.deque 사용)

from collections import deque

queue = deque()

# Enqueue
queue.append(1)
queue.append(2)

# Dequeue
print(queue.popleft())  # 출력: 1
print(queue.popleft())  # 출력: 2