[자료구조] 파이썬으로 스택(Stack) 구현하기

스택(Stack)

스택 구조

스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조입니다.
가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out)방식을 사용합니다.

웹브라우저의 뒤로가기나 편집기의 되돌리기(undo) 기능이 이런 방식을 이용합니다.

사실 파이썬의 리스트는 스택이 가져야할 메서드를 이미 가지고 있습니다. 따라서 스택 자료형을 따로 만들 필요는 없습니다. 하지만 그냥 공부한다는 생각으로 간단하게 스택 자료형을 만들어봅시다.

기본적으로 아래의 네 가지 연산이 필요합니다.

• S.push(e): Top에 새로운 요소를 추가
• S.pop(): Top 요소를 반환하면서 제거
• S.top(): Top 요소를 제거하지 않고 반환
• S.is_empty(): 스택이 비어있으면 True를 반환

뼈대 구성

뼈대를 구성해 봅시다.

class ArrayStack:
    def __init__(self):
    """빈 스택 하나를 생성합니다"""

    def __len__(self):
    """스택에 저장된 요소의 개수를 반환합니다"""

    def push(self, e):
    """스택에 요소를 추가합니다"""

    def is_empty(self):
    """스택이 비어있으면 True를 반환합니다."""  

    def pop(self):
    """가장 마지막에 들어온 요소를 반환하고 제거합니다"""

    def top(self):
    """가장 마지막에 들어온 요소를 제거하지 않고 반환합니다"""

스택이 비어있으면 pop이나 top 연산을 할 수 없으므로 예외도 하나 만들어 줍시다.

class Empty(Exception):
    pass

위처럼 파이썬의 내장 클래스인 Exception을 상속받으면 오류를 직접 만들 수 있습니다.

 

초기화

def __init__(self):
"""빈 스택 하나를 생성합니다"""
    self._data = []

빈 리스트를 하나 할당해 줍니다.

 

__len__(), push(), is_empty()

def __len__(self):
"""스택에 저장된 요소의 개수를 반환합니다"""
    return len(self._data)

def push(self, e):
"""스택에 요소를 추가합니다"""
    self._data.append(e)

def is_empty(self):
"""스택이 비어있으면 True를 반환합니다.""" 
  return len(self._data) == 0

 

push(), pop()

def pop(self):
"""가장 마지막에 들어온 요소를 반환하고 제거합니다"""
    if self.is_empty():
        raise Empty("Stack is empty")
    return self._data.pop()

def top(self):
"""가장 마지막에 들어온 요소를 제거하지 않고 반환합니다"""
    if self.is_empty():
        raise Empty("Stack is empty")
    return self._data[-1]

 

전체 코드

class Empty(Exception):
    pass


class ArrayStack:
    def __init__(self):
    """빈 스택 하나를 생성합니다"""
        self._data = []
    def __len__(self):
    """스택에 저장된 요소의 개수를 반환합니다"""
        return len(self._data)

    def push(self, e):
    """스택에 요소를 추가합니다"""
        self._data.append(e)

    def is_empty(self):
    """스택이 비어있으면 True를 반환합니다.""" 
      return len(self._data) == 0
    def pop(self):
    """가장 마지막에 들어온 요소를 반환하고 제거합니다"""
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data.pop()

    def top(self):
    """가장 마지막에 들어온 요소를 제거하지 않고 반환합니다"""
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[-1]

파이썬의 리스트 메소드를 이용하니 아주 간단하게 스택 자료형을 만들 수 있었습니다.

스택은 모든 연산이 O(1)의 시간 복잡도를 갖습니다.

Operation	Running Time
S.push(e)	O(1)*
S.pop()	O(1)*
S.top()	O(1)
S.is_empty()	O(1)
*amortized

 

예제) 괄호문법 체크

이제 우리가 만든 ArrayStack을 이용해서 괄호 문법을 체크하는 함수를 만들어 봅시다.
괄호 문법을 체크하는 문제는 스택을 사용하는 알고리즘 중에서 가장 기본적이고 대표적인 예제입니다.

[(5 + x) - (y + z)]

위와 같은 입력이 들어오면 아래의 순서로 확인 절차를 거칩니다.

1. 순서대로 하나씩 읽음
2. 왼쪽 부호를 만나면 경우 스택에 push
3. 오른쪽 부호를 만나면 스택에서 pop
4. 왼쪽 부호와 오른쪽 부호가 같은지 확인

def is_matched(expr):
    left = "{[(" 
    right = "}])"
    S = ArrayStack()
    for c in expr:
        if c in left:
            S.push(c)
        # 입력값에 왼쪽 부호가 있으면 스택에 넣어줍니다.
        elif c in right:
            if S.is_empty():
                return False
            #오른쪽 부호가 나왔는데 스택에 아무것도 없다면 False를 반환합니다.
            if right.index(c) != left.index(S.pop()):
                return False
            #오른쪽 부호가 S.pop()의 리턴값과 쌍을 이루는지 확인하고 아니라면 False를 반환합니다.
    return S.is_empty()
    #스택이 다 비워졌는지 확인합니다. 스택에 값이 남아있다면 왼쪽 부호와 쌍을 이루는 오른쪽 값이 다 나오지 않은 것이므로 거짓을 반환합니다.