[자료구조] 스택

스택(Stack)이란?

스택은 후입선출(LIFO, Last‑In First‑Out) 방식으로 작동하는 추상 자료구조이다.

즉, 가장 나중에 넣은 데이터가 가장 먼저 꺼내지는 구조다.

💡추상 자료구조란?

“어떤 기능을 제공할지”만 정의한 사양서이자 계약서

스택이라는 개념을 **“마지막에 넣은 값부터 꺼낸다(LIFO)”**라는 사양으로만 정의해놓고
실제 구현은 어떤 방식이든지(배열을 쓰든, 연결 리스트를 쓰든…) 상관없음

---

스택 메서드 소개

메서드	설명
push(x)	스택 맨 위에 요소 x를 추가
pop()	스택 맨 위의 요소를 제거하고 반환. 비어 있으면 IndexError 발생
peek()	스택 맨 위의 요소를 반환만(제거 X). 비어 있으면 IndexError 발생
is_empty()	스택이 비어 있으면 True, 아니면 False

⚠️ 주의 사항

빈 스택에서의 pop()/peek(): 반드시 예외 처리 또는 조건 검사로 안정성 확보

⁉️ 스택은 인덱스 접근이 안될까?

앞서 설명했듯이 스택은 LIFO 연산을 목적으로 한 자료구조이다.
그렇기 때문에 스택의 내부 데이터 접근은 Top(가장 마지막에 삽입된 요소)을 통해서만 이루어지고,
push/pop/peek 외에 다른 방법으로 내부 구조를 건드리는 건 의도에 맞지 않는다.

⇒ 인덱스를 통한 임의 접근은 일반적으로 제공X (이게 필요한 경우면 다른 자료구조 쓰는게…)

---

실제 코드로 구현 (Python list로 구현)

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

    def push(self, x):
        """스택 맨 위에 x 추가"""
        self._data.append(x)

    def pop(self):
        """스택 맨 위 요소 제거 후 반환"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        """스택 맨 위 요소 확인"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self) -> bool:
        """스택이 비어 있는지 검사"""
        return not self._data

    # 추가 옵션: len(Stack) 사용 가능
    def __len__(self):
        """스택 크기 확인"""
        return len(self._data)

스택 시간 복잡도

연산	시간 복잡도	메모리 사용
push(x)	O(1)	O(1) 추가
pop()	O(1)	O(1) 제거
peek()	O(1)	O(1) 읽기만
is_empty()	O(1)	O(1) 확인
전체 요소 n개 저장	—	O(n) 총 사용

개발 시 스택 사용 사례

🔍 대표 사용 예시

• 웹 브라우저 ‘뒤로 가기’: 마지막에 방문한 페이지부터 순서대로 복원

• 실행 취소(Undo) 기능: 가장 최근 작업부터 되돌리기

• 함수 호출 스택(Call Stack): LIFO 구조로 마지막에 호출된 함수가 가장 먼저 반환

스택 알고리즘 유형 예시

1. 단어 역순 출력

문자열은 물론 슬라이싱 str[::-1] 혹은 단순하게 반복문을 통해서도 쉽게 뒤집을 수 있지만,

“역순”이라는 표현에서 우리는 스택의 LIFO 구조를 떠올릴 수 있다.

def reverse_word(word):
    stack = Stack()
    for char in word: 
        stack.push(char) # 문자열을 스택에 하나씩 push
    result = ''
    while not stack.is_empty(): # 스택이 빌 때까지 위에서부터 하나씩 배출
        result += stack.pop()
    return ''.join(result)

print(reverse_word("Hello world"))  # "dlrow olleH"

---

2. 괄호 짝 검사

스택을 이용하면 소괄호, 중괄호, 대괄호의 짝이 모두 맞는지 쉽게 확인이 가능하다.

def check_pairs(s: str) -> bool:
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    for char in s:
        if char in pairs: # 여는 괄호를 만나면 stack에 push
            stack.push(char)
        else:
            if stack.is_empty(): # 주어진 문자열은 무조건 여는 괄호로 시작하므로 
                    return False # 문자열을 다 검사하기도 전에 Stack이 비어있으면 False 반환
            values = pairs.values()
            if char in values:    # char이 일반 문자가 아니라 닫는 괄호이면
                top = stack.pop() 
                if pairs[top] != char: # top의 pair 괄호와 char을 비교
                    return False

    return stack.is_empty()  # 검사 종료 후 스택이 비어있어야 함

print(check_pairs("({[asd]})"))  # True
print(check_pairs("([asd}{qwe])"))  # False

---

3. 후위 표기법 계산 (Postfix Notation)

후위 표기법은 연산자를 피연산자 뒤에 쓰는 연산 표기법이다.

💡중위 표기법과 후위 표기법

우리 사람이 쓰는 수식 표현 방식을 중위 표기법(Infix Notation)이라 부른다.
연산자에 우선순위가 부여되어 있고(곱하기와 나누기가 덧셈,뺄셈보다 높은 식),
우선순위를 조정하기 위해 괄호 또한 사용된다.

그러나 계산 위치/우선순위를 판단하는 부분을 컴파일러가 이해하기 어려웠기 때문에 만들어진 표기법이 바로 후위 표기법이다.

후위 표기법은 우선순위나 괄호 따위가 없고 그저 좌에서 우로 읽어가면서 하나씩 계산이 가능하다.

그리고 이 후위 표기법은 LIFO 원리를 통해 Stack을 이용하여 계산이 가능하다.

중위 표기법을 후위 표기법으로 쉽게 바꾸는 방법은

1. 중위식의 모든 연산마다 괄호를 친 다음
2. 연산자를 해당 연산자의 괄호 뒤로 옮긴 후
3. 괄호를 지우는 것이다.

예를 들어 2*2+4의 식이 있을 때 이를 후위 표기법으로 바꿔보면

1. ((2*2) + 4)
2. ((22)* 4)+
3. 22*4+

이렇게 바뀌는 것이다.

코드 구현

# 중위식을 후위식으로 변환하는 함수
def change_to_postfix(expr):
    operators = {"+": 1, "-": 1, "*": 2, "/": 2}
    stack = Stack()
    res = ''
    for exp in expr:
        if exp.isnumeric():
            res += exp
        elif exp == "(":
            stack.push(exp)
        elif exp == ")":
            while stack.peek() != "(":
                res += stack.pop()
            stack.pop() # 스택에서 다 꺼내면 
        elif exp in operators:
            if stack and stack.peek() != "(" and (operators[exp] <= operators[stack.peek()]):
                res += stack.pop()
            stack.push(exp)
    while stack:
        res += stack.pop()
    return res

expression = "(2 + 3 * 1) * 9"
print(change_to_postfix(expression)) # 231*+9*

# 후위식을 실제로 계산하는 함수
def eval_postfix(expr):
    stack = Stack()
    for exp in expr:
        if exp.isdigit():
            stack.push(int(exp))
        else:
            b, a = stack.pop(), stack.pop()
            stack.push({'+': a+b, '-': a-b, '*': a*b, '/': a//b}[exp])
    return stack.pop()

print(eval_postfix(change_to_postfix(expression))) # 45

---

결론

스택은 간결하면서도 강력한 자료구조로,

• 실생활 예시에서 직관적으로 이해할 수 있고,

• 알고리즘 문제에서도 자주 등장하는 개념이다.

다음에는 스택과 반대되는 FIFO 원리로 작동하는 큐(Queue) 에 대해 살펴보자!