Backend Development

스택(Stack) 자료구조: 개념부터 구현까지

Kun Woo Kim 2025. 5. 29. 01:03
728x90

자료구조는 프로그래밍의 기초이자 핵심입니다. 그 중에서도 스택(Stack)은 가장 기본적이면서도 강력한 자료구조 중 하나입니다. 이 글에서는 스택의 기본 개념부터 Java와 Python에서의 구현 방법까지, 실무에서 바로 활용할 수 있는 지식을 제공합니다.


1. 스택이란 무엇인가?

스택은 후입선출(LIFO: Last In, First Out) 원칙을 따르는 선형 자료구조입니다. 쉽게 말해, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조를 가집니다.

스택의 주요 특징

  • 데이터는 항상 스택의 최상단(top)에서만 삽입(push)과 삭제(pop)가 이루어집니다.
  • 스택이 비어있을 때 pop을 시도하면 스택 언더플로우(Stack Underflow)가 발생합니다.
  • 스택이 가득 찼을 때 push를 시도하면 스택 오버플로우(Stack Overflow)가 발생합니다.

2. 스택의 활용 사례

스택은 다양한 실제 애플리케이션에서 활용됩니다:

  1. 메모리 관리

    • 함수 호출 시 지역 변수 저장
    • 재귀 호출 관리
  2. 브라우저 기능

    • 뒤로가기/앞으로가기 기능
    • 방문 기록 관리
  3. 문서 편집기

    • 실행 취소(Undo) 기능
    • 작업 히스토리 관리
  4. 컴파일러

    • 수식의 괄호 검사
    • 중위 표기법을 후위 표기법으로 변환

3. 스택 구현: Java와 Python

Java 구현

Java에서는 스택을 구현하는 두 가지 주요 방법이 있습니다:

1. Stack 클래스 사용 (비권장)

Stack<Integer> stack = new Stack<>();
stack.push(1);  // 데이터 삽입
int top = stack.pop();  // 데이터 추출

2. Deque 인터페이스 사용 (권장)

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // 데이터 삽입
int top = stack.pop();  // 데이터 추출

Python 구현

Python에서는 리스트를 사용하여 스택을 쉽게 구현할 수 있습니다:

1. 리스트를 사용한 기본 구현

stack = []
stack.append(1)  # push: 데이터 삽입
top = stack.pop()  # pop: 데이터 추출

2. collections.deque 사용 (권장)

from collections import deque

stack = deque()
stack.append(1)  # push: 데이터 삽입
top = stack.pop()  # pop: 데이터 추출

3. 스택 클래스 구현

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")

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

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

# 사용 예시
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 출력: 2
print(stack.peek())  # 출력: 1

구현체 선택 가이드

언어 권장 구현체 이유
Java Deque 인터페이스 LIFO 원칙 준수, 성능 최적화
Python collections.deque O(1) 시간 복잡도, 스레드 안전성

4. Stack vs Deque: 왜 Deque를 사용해야 할까?

Stack 클래스의 문제점

  1. Vector 상속으로 인한 문제

    • 인덱스 기반 접근이 가능하여 LIFO 원칙이 깨질 수 있음
    • 개발자의 실수로 잘못된 사용 가능성 존재
  2. 성능 이슈

    • 모든 메소드가 synchronized로 구현
    • 단일 스레드 환경에서 불필요한 동기화 오버헤드 발생

Deque 인터페이스의 장점

  1. LIFO 원칙 준수

    • 스택의 본질적인 특성을 완벽하게 유지
    • 잘못된 사용 방지
  2. 유연한 구현체 선택

    • 동기화가 필요한 경우: ConcurrentLinkedDeque
    • 단일 스레드 환경: ArrayDeque
    • 상황에 맞는 최적화 가능

5. 실무에서의 활용 팁

  1. 스택 크기 관리

    • 스택 오버플로우를 방지하기 위한 적절한 크기 설정
    • 동적 크기 조정이 필요한 경우 Deque 구현체 사용
    • Python에서는 리스트보다 deque를 사용하여 성능 최적화
  2. 스레드 안전성

    • 멀티스레드 환경에서는 ConcurrentLinkedDeque(Java) 사용
    • 단일 스레드 환경에서는 ArrayDeque(Java) 또는 deque(Python) 사용
  3. 성능 최적화

    • 불필요한 동기화 작업 피하기
    • 적절한 초기 용량 설정으로 재할당 최소화
    • Python에서는 리스트 대신 deque를 사용하여 O(1) 시간 복잡도 보장

6. 결론

스택은 단순하면서도 강력한 자료구조입니다. Java에서는 Stack 클래스보다 Deque 인터페이스를 사용하는 것이 더 현대적이고 효율적인 방법입니다. 특히 실무에서는 스레드 안전성과 성능을 고려하여 적절한 구현체를 선택하는 것이 중요합니다.

핵심 인사이트

  • 스택은 LIFO 원칙을 따르는 선형 자료구조입니다.
  • Java에서는 Deque 인터페이스를 사용하여 스택을 구현하는 것이 권장됩니다.
  • 스레드 안전성과 성능을 고려하여 적절한 구현체를 선택해야 합니다.

참고 자료

728x90