스택Stack

6. 스택Stack#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

  • 스택 자료구조

  • 스택 활용

6.1. 스택의 정의#

스택stack은 항목의 추가 및 삭제를 보통 탑top이라 불리는 한 쪽 끝에서만 허용한다. 반면에 다른 한 쪽 끝은 베이스base라 한다.

  • 탑: 가장 나중에 추가된 항목의 위치

  • 베이스: 남아 있는 항목 중에서 가장 먼저 추가된 항목의 위치

가장 나중에 추가된 항목이 가장 먼저 삭제되는 후입선출last-in first-out(LIFO) 원리를 따른다.

6.2. 스택 자료구조 구현#

스택 자료구조는 큐 자료구조와는 달리 항목의 추가와 삭제를 탑이라고 부르는 곳에서만 처리한다. 하지만 그 이외에는 큐와 동일한 기능을 지원한다. 실제로 파이썬에서 스택 자료구조로 제공되는 queue.LifoQueue 클래스가 큐 자료구조인 queue.Queue와 동일한 이름의 메서드를 제공한다.

따라서 여기서도 5장에서 정의한 다음 Queue 추상 자료형을 구상 클래스로 상속하는 방식으로 스택 자료구조를 선언한다.

class Queue:
    def __init__(self, maxsize=0):
        """
        - 새로운 큐 생성
        - maxsize: 최대 항목 수. 0은 무한대 의미.
        - 저장 방식은 자식 클래스가 지정해야 함.
        """
        raise NotImplementedError(
            """아래 두 변수 구현 필요
            self._maxsize=maxsize
            self._container=비어 있는 모음 객체. 항목 저장.
            """)
    
    def qsize(self):
        """항목 수 반환"""
        return len(self._container)
    
    def empty(self):
        """비었는지 여부 확인"""
        return not self._container

    def full(self):
        """_maxsize 충족 여부 확인"""

        if self._maxsize <= 0:
            return False
        elif self.qsize() < self._maxsize:
            return False
        else:
            return True            

    def put(self, item):
        """항목 추가"""
        raise NotImplementedError

    def get(self):
        """항목 삭제"""
        raise NotImplementedError

다만 리스트를 항목들의 저장 장치로 활용한다. 이유는 리스트의 오른쪽 끝(마지막 항목)을 탑으로 지정해도 항목의 추가와 삭제를 빠르게 실행할 수 있기 때문이다.

class Stack(Queue):
    def __init__(self, maxsize=0):
        """
        - 새로운 스택 생성
        - _maxsize: 최대 항목 수. 0은 무한대 의미.
        - _container: 항목 저장 장치. list 활용
        """
        self._maxsize = maxsize
        self._container = list() # 비어있는 리스트
    
    def __repr__(self):
        """스택 표기법: stack([1, 2, 3]) 등등"""
        return f"stack({self._container})"
    
    def put(self, item):
        """
        _maxsize를 못 채웠을 경우에만 항목 추가
        """
        if not self.full():
            self._container.append(item)
        else:
            print("추가되지 않아요!")

    def get(self):
        """머리 항목 삭제 후 반환"""
        return self._container.pop()

아래 코드가 스택 객체를 생성하고 활용하는 간단한 작동법을 소개한다.

s = Stack(maxsize=4)

s.put(4)
s.put("dog")
s.put(True)
print(s)
s.put(8.4)
print(s.full())
print(s)
s.put("하나 더?")
print(s)
print(s.get())
print(s.get())
print(s.qsize())
print(s)
print(s.empty())

stack([4, 'dog', True])
True
stack([4, 'dog', True, 8.4])
추가되지 않아요!
stack([4, 'dog', True, 8.4])
8.4
True
2
stack([4, 'dog'])
False

6.3. queue.LifoQueue 클래스#

파이썬 queue 모듈의 LifoQueue 클래스가 스택 자료구조를 가리킨다. 앞서 정의한 Stack 클래스보다 몇 배 느리다.

import queue

  • put() 메서드 속도 비교

%%time

n = 100_000
q1 = Stack(maxsize=0)

for k in range(n):
    q1.put(k)

CPU times: user 10.1 ms, sys: 151 μs, total: 10.3 ms
Wall time: 10.1 ms

%%time

n = 100_000
q2 = queue.LifoQueue(maxsize=0)

for k in range(n):
    q2.put(k)

CPU times: user 52.5 ms, sys: 0 ns, total: 52.5 ms
Wall time: 52.2 ms

  • get() 메서드 속도 비교

%%time

for k in range(n):
    q1.get()

CPU times: user 0 ns, sys: 6.85 ms, total: 6.85 ms
Wall time: 6.65 ms

%%time

for k in range(n):
    q2.get()

CPU times: user 55 ms, sys: 0 ns, total: 55 ms
Wall time: 54.7 ms

6.4. 스택 활용: 괄호 매칭 여부 판정#

코드에는 소, 중, 대 세 종류의 괄호가 각자의 역할에 따라 사용된다.

괄호 종류

기호

활용 예제

소괄호

(, )

튜플, 수식

중괄호

{, }

사전, 집합

대괄호

[, ]

리스트

코드에 포함된 표현식에 사용된 모든 괄호들의 짝이 맞는가를 확인하는 일은 매우 중요하다. 파이썬은 코드를 실행하기 전에 구문 검사를 진행하여 괄호의 짝이 맞지 않으면 아래에서처럼 바로 구문 오류(SyntaxError)를 발생시킨다.

x = [1, 2, (5, 3), ('a':7, 'b':9}]

  Cell In[9], line 1
    x = [1, 2, (5, 3), ('a':7, 'b':9}]
                                    ^
SyntaxError: closing parenthesis '}' does not match opening parenthesis '('

위 변수 할당문은 사전 객체를 'a':7, 'b':9 를 감싸는 중괄호 중에서 여는 중괄호가 소괄호로 되어 있어어 구문 오류가 발생하였다. 아래에서처럼 여는 중괄호와 닫는 중괄호가 서로 매칭되도록 해야 오류가 발생하지 않는다.

x = [1, 2, (5, 3), {'a':7, 'b':9}]

코드와 표현식에 사용된 모든 종류의 괄호를 대상으로 괄호 매칭 여부를 판단하기 위해 코드 내용과 상관 없이 괄호만으로 구성된 문자열을 이용할 수 있다. 예를 들어 위 표현식의 괄호만 고려하면 다음 문자열을 얻게 되고, 모든 종류의 괄호에 대해 괄호 매칭이 제대로 이뤄짐을 쉽게 확인할 수 있다.

[(){}]

그런데 괄호가 중첩되어 사용되면 괄호 매칭 여부의 판단이 보다 어려워진다. 예를 들어 아래 예제는 모두 괄호들의 짝이 맞는지 여부를 확인하기 위해 자세히 살펴 봐야 한다.

  • 처음 3 개의 문자열: 괄호 짝 맞음

  • 다음 3 개의 문자열: 괄호 짝 맞지 않음

{{([][])}()}
[[{{(())}}]]
[][][](){}
([))
((()]))
[{()]

6.4.1. 괄호 문자열 대상 괄호 매칭 여부 판정#

스택 자료구조를 활용하여 괄호만으로 구성된 문자열에 대해 괄호 매칭 여부를 판정하는 함수를 구현해보자. 스택 활용법은 다음과 같다.

  • 비어있는 스택을 하나 생성

  • 괄호 문자열에 포함된 기호에 대해 아래 작업 반복

    • 여는 괄호: 스택에 추가

    • 닫는 괄호: 스택의 탑 항목 삭제

예를 들어 아래 그림은 {[()]}에 대해 괄호 매칭 여부를 판정하는 과정을 보여준다.

괄호 매칭이 거짓인 경우 위 알고리즘을 진행하다 보면 아래 세 가지 경우 중 하나가 발생한다.

첫째, {[(])}의 경우처럼 탑에 위치한 여는 괄호와 표현식에 있는 닫는 괄호가 달라서 여는 괄호와 닫는 괄호가 매칭되지 않는다.

둘째, [()]}의 경우처럼 아직 확인해야할 닫는 괄호가 있지만 스택이 먼저 비워질 수 있다. 스택에 포함되어 있어야 하는 여는 괄호가 없는 경우에 이런 일이 발생한다.

셋째, {[()]의 경우처럼 문자열에 포함된 모든 괄호를 확인했음에도 불구하고 스택에 항목이 남아 있을 수 있다. 스택에 남아 있는 여는 괄호에 매칭되는 닫는 괄호가 없는 경우에 이런 일이 발생한다.

아래 balance_checker() 함수가 앞서 설명한 알고리즘을 구현한다. 이를 위해 먼저 두 괄호의 매칭 여부를 판정하는 matches() 함수를 구현한다. matches() 함수는 첫째 인자와 둘째 인자가 서로 매칭되는 괄호인 경우에만 True를 반환한다.

def matches(par_left, par_right):
    all_lefts = "([{"
    all_rights = ")]}"
    
    if (par_left not in all_lefts) or (par_right not in all_rights):
        return False
    
    return all_lefts.index(par_left) == all_rights.index(par_right)

print(matches('(', ')'))
print(matches('[', ']'))
print(matches('{', '}'))
print(matches('(', ']'))
print(matches('[', '}'))
print(matches('(', '('))

True
True
True
False
False
False

matches() 함수를 이용하여 괄호 문자열을 대상으로 괄호 매칭 여부를 판정하는 함수를 다음과 같이 구현할 수 있다.

def balance_checker(par_string):
    s = Stack()                # 비어 있는 스택 생성
    
    for symbol in par_string:
        if symbol in "([{":   # 여는 괄호 스택에 추가
            s.put(symbol)
        elif s.empty():       # 스택이 미리 비워지는 경우
            return False
        elif not matches(s.get(), symbol): 
            return False     # 두 괄호가 매칭 되지 않는 경우

    return s.empty()          # 최종적으로 스택이 비워졌는지 여부 확인

앞서 눈으로 쉽게 판단할 수 없는 괄호 문자열을 대상으로 위 함수를 적용하면 기대한 대로 작동한다.

print(balance_checker('{{([][])}()}'))
print(balance_checker('[[{{(())}}]]'))
print(balance_checker('[][][](){}'))
print(balance_checker('([))'))
print(balance_checker('((()]))'))
print(balance_checker('[{()]'))

True
True
True
False
False
False

6.4.2. 표현식 대상 괄호 매칭 판정#

balance_checker() 함수를 살짝 수정하면 임의의 표현식에 사용된 괄호의 매칭 여부를 판정할 수 있다. 아래 코드는 표현식에 포함된 문자 중에서 괄호가 아니면 무시하도록 하는 기능을 추가하였다.

def balance_checker(exp_string):
    s = Stack()

    for symbol in exp_string:
        if symbol not in "()[]{}":   # 괄호가 아니면 무시
            continue
        elif symbol in "([{":
            s.put(symbol)
        elif s.empty():
            return False
        elif not matches(s.get(), symbol):
            return False

    return s.empty()

이제 임의의 문자열에 대해 괄호 매칭 여부를 판정할 수 있다.

print(balance_checker('{({([][])}())}'))
print(balance_checker('[{()]'))
print(balance_checker('(A + B) * C - (D - E) * (F + G)'))
print(balance_checker('(5 + 6) * (7 + 8) / (4 + 3'))
print(balance_checker("[1, 2, (5, 3), {'a':7, 'b':9}]"))
print(balance_checker("[1, 2, (5, 3), ('a':7, 'b':9}]"))

True
False
True
False
True
False

6.5. 연습 문제#

  1. (실습) 스택

  2. (실습) 중위, 전위, 후위 표기법

Contents