스택 정의, 값 넣기/빼기

프로그래밍을 처음 접할 때 나오는 대표적인 자료구조 중 하나가 바로 스택(Stack) 이다. 이름만 들으면 어렵게 느껴질 수 있지만, 실제로는 우리 일상에서도 쉽게 찾아볼 수 있는 개념이다. 예를 들어 젠가(Jenga) 게임을 떠올려보자.

---

스택이란? 젠가로 이해하는 Stack의 원리

젠가 블럭을 하나씩 통에 넣고 꺼내는 상황을 상상해보자. 가장 최근에 넣은 블럭은 통의 가장 위에 쌓이게 된다. 그리고 꺼내고자 할 때도 맨 위의 블럭부터 꺼낼 수밖에 없다. 만약 맨 아래에 있는 블럭이 필요하다면? 위에 있는 블럭들을 먼저 전부 꺼내야 한다.

이처럼 가장 나중에 들어간 데이터가 가장 먼저 나오는 구조를 우리는 후입선출(Last In, First Out, LIFO) 이라고 부른다. 스택은 바로 이 LIFO 원리를 따르는 대표적인 자료구조이다.

Stack의 기본 연산 5가지

스택은 마치 블럭을 차곡차곡 쌓고 꺼내는 것처럼, 다음과 같은 다섯 가지 주요 기능을 갖는다.

리스트로 표현

stack = []

# 데이터 삽입
stack.append(5)   # push(5)
stack.append(10)  # push(10)

# 데이터 확인 및 제거
print(stack[-1])  # top() → 10
print(stack.pop())  # pop() → 10

# 스택 상태
print(len(stack))  # size() → 1
print(not stack)   # empty() → False

Stack의 시간복잡도

스택에서 데이터를 삽입하거나 삭제하는 연산은 모두 맨 위에서만 일어나기 때문에, 시간복잡도는 평균적으로 O(1) 이다. 즉, 매우 빠른 속도로 데이터를 처리할 수 있다는 장점이 있다.

---

🧱 Python으로 Stack 자료구조 직접 구현하기

✨ Python에는 Stack이 없다?

Python은 내장 자료구조로 리스트(list)를 제공하지만, Stack이라는 별도의 클래스는 없다.
그래서 Stack을 사용하려면, Stack을 직접 만들어야 한다.

🧰 Stack 클래스 직접 구현하기

class Stack:
    def __init__(self):
        self.items = []  # 내부적으로 리스트를 사용합니다.

    def push(self, item):
        self.items.append(item)  # 맨 끝에 아이템을 추가합니다.

    def pop(self):
        if self.empty():
            raise Exception("Stack is empty")
        return self.items.pop()  # 맨 끝에서 제거하고 반환합니다.

    def top(self):
        if self.empty():
            raise Exception("Stack is empty")
        return self.items[-1]  # 맨 끝 요소를 반환 (제거하지 않음)

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

    def empty(self):
        return not self.items

📦 사용 예제

s = Stack()          # 빈 스택 생성
s.push(2)
s.push(5)
s.push(9)

print(s.top())       # 👉 9 (가장 위에 있는 값)
s.pop()              # 9 제거
print(s.size())      # 👉 2

# 스택이 빌 때까지 top → pop 반복
while not s.empty():
    print(s.top())   # 👉 5, 2
    s.pop()

💡 실행 결과

9
2
5
2

🧑‍💻 실전에서 Stack은 어디에 쓰일까?

• 웹 브라우저의 뒤로 가기 기능

• 수식 계산기 (괄호 짝 맞추기, 후위 표기법 등)

• DFS (깊이 우선 탐색) 알고리즘

• 괄호 유효성 검사

• 함수 호출 기록 관리