알고리즘 기초 - 스택

---

스택이란?

---

스택은 데이터를 쌓아 올린 형태의 자료구조로, 가장 마지막에 삽입한 데이터를 가장 먼저 꺼내는 Last In, First Out 구조를 가진다.

 

 

 쉽게 프링클스 통을 생각하면 이해하기 쉽다.

-> 과자를 통에 넣는다 : push

-> 과자를 꺼내 먹는다 : pop

 

 

---

스택 구현 

---

 

파이썬 스택 구현

파이썬에서는 기본 리스트를 이용해 간단히 스택을 구현할 수 있다.

stack = []

# 데이터 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)
print("스택 상태:", stack)

# 데이터 꺼내기 (pop)
print("pop:", stack.pop())
print("스택 상태:", stack)

# 가장 위 원소 확인 (peek)
print("peek:", stack[-1])

# 스택이 비어있는지 확인
print("isEmpty:", len(stack) == 0)

 

 

출력결과 

 

스택 상태: [1, 2, 3]
pop: 3
스택 상태: [1, 2]
peek: 2
isEmpty: False

 

 

 

---

알고리즘 예시

---

 

괄호 검사 문제

올바른 괄호 문자열인지 확인하는 문제는 전형적인 스택 활용 예시다.

def check_bracket(s):
    stack = []
    for ch in s:
        if ch == "(":
            stack.append(ch)
        elif ch == ")":
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

print(check_bracket("(())"))   # True
print(check_bracket("(()"))    # False

 

 

보통 스택문제는 이렇게 반복문을 통해 원하는 값을 찾는 문제가 많이 주어진다.

---

스택 활용 분야

---

• 수식 계산 (후위 표기법)
• DFS(깊이 우선 탐색)
• 웹 브라우저 뒤로 가기/앞으로 가기
• 문자열 뒤집기
• 괄호 검사

---

마무리

---

스택은 단순해 보이지만, 다양한 문제 해결의 기초가 되는 자료구조다.
특히 문자열 처리, 수식 계산, 그래프 탐색 등 여러 분야에서 유용하게 쓰이므로 꼭 이해하고 넘어가야 한다.