스택(Stack)

스택(Stack)

데이터를 쌓아 올리는 방식의 자료 구조

마지막에 삽입된 요소(top)가 가장 먼저 제거(pop)되는 LIFO(Last-In-First-Out) 구조

----🐢

주요 연산

push(item)

스택의 맨 위(top)에 아이템을 삽입

pop()

스택의 맨 위(top)에 있는 아이템을 제거하고 반환

peek() (또는 top())

스택의 맨 위 아이템을 확인(반환)하되 제거하지 않음

is_empty()

스택이 비어 있는지 확인

size()

스택에 쌓여 있는 데이터 개수 확인

---🐢-

파이썬 스택 구현

리스트 스택 구현

내장 자료 구조인 리스트(list) 를 이용해 간단히 스택을 구현

# append()와 pop() 사용

stack = []

# push 연산: append()
stack.append(10)  # [10]
stack.append(20)  # [10, 20]
stack.append(30)  # [10, 20, 30]

# pop 연산: pop()
item = stack.pop()  # item=30, stack=[10,20]

# peek (리스트 마지막 요소 확인)
top_item = stack[-1]  # 20 (제거되지 않음)

# is_empty
if not stack:
    print("스택이 비어있습니다.")
else:
    print("스택에 원소가 있습니다.")

# size
print("스택 크기:", len(stack))  # 2

리스트의 맨 뒤(list[-1])를 top으로 사용하므로, append()와 pop()이 O(1) 시간에 수행

단, 리스트의 앞쪽(pop(0))을 스택으로 사용하면 비효율적이므로 주의(앞쪽 요소 제거 시 O(n) 소요)

# 사용자 정의 스택 클래스

class Stack:
    def __init__(self):
        self.items = []  # 내부적으로 list 사용

    def push(self, item):
        self.items.append(item)

    def pop(self):
        # 비어있을 때 pop()을 하려면 보통 예외 처리
        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]
        return None  # or raise exception

    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
print(stack.size())  # 1

 

collections.deque를 사용한 구현

파이썬의 collections.deque는 양쪽에서 삽입/삭제가 O(1)에 가능하도록 설계된 양방향 큐(Double-Ended Queue) 구조

스택으로 사용할 때는 오른쪽 끝(또는 왼쪽 끝)을 top으로 정의하여, append() / pop() 메서드로 스택 연산을 수행

리스트와 유사하게 사용할 수 있지만, 큰 규모에서 더 효율적

from collections import deque

stack = deque()

# push: append
stack.append(10)  # deque([10])
stack.append(20)  # deque([10, 20])

# pop
item = stack.pop()   # item=20, stack=deque([10])
top_item = stack[-1] # 10

--🐢--

스택 활용 사례

괄호 체크(Parenthesis Matching)

소스 코드나 식에서 (, ), {, }, [, ] 등이 올바르게 쌍을 이루는지 검사할 때 스택을 사용

수식 후위 표기법(Postfix Expression) 변환 및 계산

중위 표기식을 후위 표기식으로 변환하거나, 후위 표기식을 계산할 때 스택 구조가 핵심

웹 브라우저 뒤로 가기

방문 기록을 스택에 넣고, “뒤로 가기” 시 스택에서 pop 하여 이전 페이지로 돌아감

DFS(깊이 우선 탐색)

그래프/트리 탐색에서, 재귀를 사용하지 않고 스택으로 구현 가능

 

# 활용 예시(괄호 짝 체크)

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        # 여는 괄호라면 stack에 push
        if char in '({[':
            stack.append(char)
        # 닫는 괄호라면 stack에서 pop한 뒤 짝이 맞는지 확인
        elif char in ')}]':
            if not stack:
                return False  # 스택이 비었는데 닫는 괄호가 나옴
            top = stack.pop()
            if mapping[char] != top:
                return False  # 짝 불일치

    return len(stack) == 0  # 스택에 남은 여는 괄호가 없으면 True

# 테스트
print(is_valid_parentheses("(){}[]"))  # True
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses("{[]}"))    # True

-🐢---

스택 시간 복잡도

push(삽입): O(1) (평균 혹은 암묵적으로 상수 시간; 동적 배열/덱 구조 특성상 재할당 상황에서 드물게 O(n)이 일어나지만, **아몰타이즈드(amortized)**로 O(1))

pop(삭제): O(1)

peek/top(맨 위 원소 확인): O(1)

is_empty(비었는지 확인): O(1)

size(크기 확인): O(1) (파이썬 리스트나 deque는 길이를 내부적으로 관리하므로 즉시 확인 가능)

 

>>> 파이썬에서 전형적인 스택 연산은 상수 시간, 즉 O(1)

🐢----

스택 search

시간 복잡도: O(n)

>>> 스택은 LIFO구조로, 데이터가 한쪽으로만 삽입(push)되고 제거(pop)

>>> 특정 값을 검색하려면 스택의 데이터를 하나씩 탐색

>>> 스택의 크기를 n이라 하면 최악의 경우 모든 요소를 확인해야

stack = [10, 20, 30, 40, 50]

# 값이 스택 안에 있는지 확인
def search(stack, target):
    for i in range(len(stack) - 1, -1, -1):  # LIFO 방식으로 스캔
        if stack[i] == target:
            return len(stack) - i  # 스택의 1-based 위치 반환
    return -1  # 찾지 못하면 -1

# 테스트
print(search(stack, 30))  # 출력: 3 (30이 스택의 위에서부터 3번째 위치)
print(search(stack, 100))  # 출력: -1 (100은 스택에 없음)