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

자료구조는 프로그래밍의 기초이자 핵심입니다. 그 중에서도 스택(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

구현체 선택 가이드

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 인터페이스를 사용하여 스택을 구현하는 것이 권장됩니다.
• 스레드 안전성과 성능을 고려하여 적절한 구현체를 선택해야 합니다.

참고 자료

• Java Stack 클래스 문서
• Java Deque 인터페이스 문서
• Java Collections Framework 문서
• Python collections.deque 문서