[Python] 스택 (stack) 기본개념

데이터를 임시 저장할 때 쓰는 자료구조
입, 출력 순서는 후입 선출 LIFO(Last In First Out) 방식

©️ 나

개요

위와 같이, 가장 나중에 추가된 데이터가 가장 먼저  선형 자료구조 임

실제 예로는 접시 쌓기나, 웹 브라우저의 뒤로가기 기능이 있음

주요 특성

1. LIFO 구조 :
   마지막에 들어온 요소가 가장 먼저 나감
2. 단순성 :
   삽입(push)와 삭제(pop) 연산만 지원
3. 제한된 접근 :
   스택 내에서는 오직 top 요소만 접근 가능, 임의 접근(random access)가 불가능

기본 연산

스택 자료구조에서는 아래의 연산을 지원

• push(item) : 스택의 top에 새 데이터를 삽입
• pop() : top 요소를 제거하고 반환, 비어있으면 오류 발생
• peek() 또는 top() : 스택의 top 요소를 제거하지 않고 반환
• isEmpty() : 스택이 비어있는지 확인 (bool)

구현

아래는 list를 활용한 스택 구현 예제임

class Stack:
    def __init__(self):
        # 빈 스택 초기화 (내부적으로 리스트 사용)
        self.items = []

    def is_empty(self):
        # 스택이 비어있으면 True, 아니면 False 반환
        return len(self.items) == 0

    def push(self, item):
        # 새 데이터를 스택의 top에 추가
        self.items.append(item)

    def pop(self):
        # 스택이 비어있지 않으면 top 요소를 제거하고 반환
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        # 스택의 top 요소를 반환 (제거하지 않음)
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

    def size(self):
        # 스택에 들어있는 데이터의 개수를 반환
        return len(self.items)

# 스택 사용 예제
if __name__ == '__main__':
    s = Stack()
    print("스택이 비어있는가?", s.is_empty())  # True 출력
    s.push(10)
    s.push(20)
    s.push(30)
    print("현재 스택의 크기:", s.size())      # 3 출력
    print("스택의 top:", s.peek())             # 30 출력
    print("pop:", s.pop())                     # 30 제거 및 반환
    print("pop:", s.pop())                     # 20 제거 및 반환
    print("현재 스택의 크기:", s.size())         # 1 출력

collections.deque로 스택 구현

deque는 Python에서 제공하는 내장 컨테이너 collection 모듈 내의 함수이며, 이는 맨 앞과 맨 끝 양쪽에서 원소를 추가/삭제하는 자료구조인 덱(deque)을 구현하는 함수임

• 주요 속성 및 함수

append(x) deque의 맨 끝(오른쪽)에 x를 추가

appendleft(x) deque의 맨 앞(왼쪽)에 x를 추가

clear() 모든 원소를 삭제하고 크기를 0으로 만듦

copy() 얕은 복사(shallow copy)를 수행

count(x) 안에 있는 x와 같은 원소의 개수를 계산

extend(iterable) 순차 반복 인수 iterable에서 가져온 원소를 deque의 맨 끝(오른쪽)에 추가하여 확장

extendleft(iterable) 순차 반복 인수 iterable에서 가져온 원소를 deque의 맨 앞(왼쪽)에 추가하여 확장

index(x[, start[, stop]]) idx start부터 stop까지 양 끝을 포함한 범위에 존재하는 값 x들 중 가장 앞쪽의 원소 위치를 반환, x가 존재하지 않을 때 ValueError를 내보냄

insert(i, x) x를 deque의 i위치에 삽입. 이 때 크기 제한이 있는 deque의 경우 maxlen을 초과한 삽입은 IndexError 를 발생

pop() 맨 끝(우측)에 있는 원소 1개 삭제, 반환. 하나도 없는 경우는 IndexError 를 발생

popleft() 맨 앞(좌측)에 있는 원소 1개 삭제, 반환. 하나도 없는 경우는 IndexError 를 발생

remove(value) value와 같은 값을 가진 가장 앞의 항목을 삭제. 원소가 없는 경우는 ValueError를 발생

reverse() 원소를 역순으로 재정렬하고 None 를 반환

rotate(n = 1) 원소를 n값 만큼 오른쪽으로 밀어냄. 음수라면 왼쪽으로 밀어냄

활용

• 함수 호츨 관리 : OS나 인터프리터는 함수 호출 시 콜 스택(Call Stack)을 사용하여 호출 순서와 반환 주소를 관리
• 수식의 후위 표기법 계산 : 후위(postfix) 또는 전위(prefix) 표기법으로 변환한 수식을 계산할 때 스택을 사용
• 문자열 처리 : 괄호의 균형 검사, 문자열 뒤집기 등 알고리즘 문제에 사용