스택(Stack)

Jeonghwan Yoon·2025년 3월 30일

개념

후입선출(LIFO, Last In First Out) 구조
가장 나중에 들어온 데이터가 가장 먼저 나감
책 더미, 접시 쌓기처럼 위에서 넣고 위에서 꺼냄

주요 연산

연산	설명
`push(x)`	값을 스택에 추가
`pop()`	가장 위에 있는 값을 제거하고 반환
`peek()` / `top()`	가장 위 값을 확인 (제거하지 않음)
`isEmpty()`	스택이 비었는지 확인

파이썬에서의 스택 구현

리스트 사용

stack = []

stack.append(1)    # push
stack.pop()        # pop
top = stack[-1]    # peek

if not stack:      # isEmpty
    print("스택이 비어 있음")

deque 사용 (성능 안정)

from collections import deque

stack = deque()
stack.append(1)
stack.pop()

활용 예시

유형	설명
괄호 검사	여는 괄호 push, 닫는 괄호 만나면 pop
오큰수 문제	이전 수들과의 관계 추적
DFS (비재귀 구현)	방문 경로를 스택에 저장하며 탐색
수식 계산기	후위 표기법 계산
히스토그램 최대 사각형	높이 정보 추적하여 면적 계산

예제: 괄호 짝 맞추기

def is_valid_parentheses(s):
    stack = []
    for ch in s:
        if ch == '(':
            stack.append('(')
        else:
            if not stack:
                return False
            stack.pop()
    return not stack

print(is_valid_parentheses("(()())"))  # True
print(is_valid_parentheses("())("))    # False

파이썬 조건문 팁

if stack:
    print("스택에 값 있음")
else:
    print("비어 있음")

파이썬 리스트는 빈 리스트이면 False, 값이 있으면 True

예외 처리 (peek 시)

try:
    top = stack[-1]
except IndexError:
    print("스택이 비어 있음")

pop 또는 peek 시 스택이 비어 있으면 오류 발생 가능

시간 복잡도

연산	시간 복잡도
push / pop / peek	O(1)
전체 순회 문제	O(N) (선형 시간 내 모든 요소 처리)

C언어 전환 시 유의사항

항목	C언어에서의 처리
리스트	배열 또는 동적 할당 사용
append	배열 인덱스 증가로 삽입
pop	인덱스 감소 처리
비었는지 확인	스택 포인터(인덱스) == 0 여부로 판단