전체 목록
자료구조Medium#28

스택(Stack)과 큐(Queue)의 차이점과 실제 활용 사례를 설명해주세요.

#자료구조#스택#큐
힌트

LIFO vs FIFO 원칙과 실제 시스템에서의 활용을 생각해보세요.

정답 및 해설

스택(Stack)과 큐(Queue)의 차이점과 실제 활용 사례를 설명해주세요.

스택과 큐는 데이터 삽입·삭제의 순서가 다른 두 가지 선형 자료구조입니다. 스택은 LIFO(Last In First Out), 큐는 FIFO(First In First Out) 원칙을 따르며, 이 차이가 각각의 적합한 활용 사례를 결정합니다. 두 자료구조 모두 배열이나 연결 리스트로 구현할 수 있으며, 다양한 알고리즘과 시스템 설계의 핵심 구성 요소입니다.

스택 (Stack)

LIFO 원리

스택은 나중에 들어온 것이 먼저 나가는(Last In First Out) 자료구조입니다. 책을 쌓는 것처럼, 가장 위에 있는 항목만 꺼낼 수 있습니다.

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
pop()   → 3 반환, [1, 2]
pop()   → 2 반환, [1]
peek()  → 1 (제거 없이 확인)

핵심 연산

연산설명시간 복잡도
push(item)스택 맨 위에 추가O(1)
pop()맨 위 항목 제거 및 반환O(1)
peek() / top()맨 위 항목 확인 (제거 안 함)O(1)
isEmpty()스택이 비어있는지 확인O(1)
size()스택의 크기 반환O(1)

스택 구현

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

// Java에서 스택 사용
import java.util.Deque;
import java.util.ArrayDeque;

// Java 공식 문서에서는 Stack 클래스 대신 Deque 사용 권장
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);     // 맨 위에 추가
stack.push(2);
stack.push(3);
stack.pop();       // 3 반환
stack.peek();      // 2 확인 (제거 안 함)

스택의 실제 활용 사례

1. 함수 호출 스택 (Call Stack)

프로그램의 함수 호출과 반환은 스택 구조로 관리됩니다.

def c():
    print("c 실행")
    # 호출 스택: [main, a, b, c]
    return

def b():
    c()
    # 호출 스택: [main, a, b]
    return

def a():
    b()
    # 호출 스택: [main, a]
    return

# 호출 스택: [main]
a()
# a 반환 후: [main]

재귀 함수가 너무 깊어지면 Stack Overflow 발생합니다.

2. 브라우저 뒤로가기/앞으로가기

class Browser:
    def __init__(self):
        self.back_stack = []    # 방문 기록
        self.forward_stack = []  # 앞으로 가기 기록
        self.current = None

    def visit(self, url):
        if self.current:
            self.back_stack.append(self.current)
        self.current = url
        self.forward_stack.clear()  # 새 페이지 방문 시 앞으로가기 초기화

    def back(self):
        if self.back_stack:
            self.forward_stack.append(self.current)
            self.current = self.back_stack.pop()

    def forward(self):
        if self.forward_stack:
            self.back_stack.append(self.current)
            self.current = self.forward_stack.pop()

browser = Browser()
browser.visit("google.com")
browser.visit("github.com")
browser.visit("stackoverflow.com")
browser.back()    # github.com으로
browser.back()    # google.com으로
browser.forward() # github.com으로

3. 괄호 유효성 검사

def is_valid_brackets(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return len(stack) == 0

print(is_valid_brackets("({[]})"))  # True
print(is_valid_brackets("({[})"))   # False
print(is_valid_brackets("((())"))   # False

4. DFS (깊이 우선 탐색)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()  # 스택에서 꺼냄 (LIFO)
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
dfs_iterative(graph, 1)  # 1 3 6 2 5 4 (LIFO 순서)

큐 (Queue)

FIFO 원리

큐는 먼저 들어온 것이 먼저 나가는(First In First Out) 자료구조입니다. 줄을 서는 것처럼, 가장 먼저 들어온 항목이 먼저 처리됩니다.

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
dequeue()  → 1 반환, [2, 3]
dequeue()  → 2 반환, [3]
front()    → 3 (제거 없이 확인)

핵심 연산

연산설명시간 복잡도
enqueue(item)큐 뒤에 추가O(1)
dequeue()맨 앞 항목 제거 및 반환O(1)
front() / peek()맨 앞 항목 확인O(1)
isEmpty()큐가 비어있는지 확인O(1)
size()큐의 크기 반환O(1)

큐 구현

from collections import deque  # 파이썬에서 효율적인 큐 구현

class Queue:
    def __init__(self):
        self._items = deque()  # O(1) 양끝 삽입/삭제

    def enqueue(self, item):
        self._items.append(item)  # 뒤에 추가

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._items.popleft()  # 앞에서 제거

    def front(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

배열로 큐를 구현하면 dequeue 시 O(n) 이동이 필요하므로, 파이썬에서는 collections.deque를 사용합니다.

큐의 실제 활용 사례

1. 작업 스케줄링 (Task Scheduling)

import threading
import time
from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"작업 추가: {task}")

    def process(self):
        while self.queue:
            task = self.queue.popleft()  # FIFO
            print(f"처리 중: {task}")
            time.sleep(0.1)

queue = TaskQueue()
queue.add_task("이메일 발송")
queue.add_task("보고서 생성")
queue.add_task("DB 백업")
queue.process()
# 이메일 발송 → 보고서 생성 → DB 백업 순서로 처리

2. BFS (너비 우선 탐색)

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()  # 큐에서 꺼냄 (FIFO)
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
bfs(graph, 1)  # 1 2 3 4 5 6 (레벨 순서)

3. 이벤트 처리 (Event Handling)

// 브라우저의 이벤트 루프 (개념적 표현)
const eventQueue = [];

// 이벤트 발생 시 큐에 추가
eventQueue.push({ type: 'click', handler: handleClick });
eventQueue.push({ type: 'keypress', handler: handleKeypress });

// 이벤트 루프: 큐에서 순서대로 처리
function eventLoop() {
    while (eventQueue.length > 0) {
        const event = eventQueue.shift();  // FIFO
        event.handler();
    }
    requestAnimationFrame(eventLoop);
}

덱 (Deque, Double-Ended Queue)

덱은 앞뒤 양쪽에서 삽입과 삭제가 모두 가능한 자료구조입니다. 스택과 큐의 특성을 모두 가집니다.

앞 ←→ [a, b, c, d] ←→ 뒤

appendleft(x): 앞에 추가
append(x):     뒤에 추가
popleft():     앞에서 제거
pop():         뒤에서 제거

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)   # [0, 1, 2, 3] - 앞에 추가
dq.append(4)       # [0, 1, 2, 3, 4] - 뒤에 추가
dq.popleft()       # 0 반환, [1, 2, 3, 4]
dq.pop()           # 4 반환, [1, 2, 3]

덱의 활용: 슬라이딩 윈도우

from collections import deque

def max_sliding_window(nums, k):
    """크기 k인 슬라이딩 윈도우에서 최댓값 구하기"""
    dq = deque()  # 인덱스 저장
    result = []

    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

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

우선순위 큐 (Priority Queue)

일반 큐와 달리, 우선순위가 높은 항목이 먼저 나옵니다.

import heapq  # 파이썬 힙 (우선순위 큐)

pq = []
heapq.heappush(pq, (3, "낮은 우선순위"))
heapq.heappush(pq, (1, "높은 우선순위"))
heapq.heappush(pq, (2, "중간 우선순위"))

print(heapq.heappop(pq))  # (1, "높은 우선순위")
print(heapq.heappop(pq))  # (2, "중간 우선순위")
print(heapq.heappop(pq))  # (3, "낮은 우선순위")

스택 vs 큐 비교 요약

특성스택 (Stack)큐 (Queue)
원리LIFO (Last In First Out)FIFO (First In First Out)
삽입 위치맨 위 (top)맨 뒤 (rear)
삭제 위치맨 위 (top)맨 앞 (front)
주요 연산push, pop, peekenqueue, dequeue, front
시간 복잡도O(1)O(1)
탐색 알고리즘DFSBFS
주요 활용함수 호출, 뒤로가기, 괄호 검사작업 스케줄링, 이벤트 처리
비유책 쌓기, 접시 쌓기줄 서기, 티켓 발권
파이썬 구현list 또는 dequedeque
Java 구현Deque (ArrayDeque)Queue (LinkedList, ArrayDeque)
이전 질문다음 질문