파이썬) 스택(Stack)

스택이란 자료를 보관할 수 있는 어떤 구조를 의미하는 데 데이터를 넣을 땐 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때에도 넣은 방향에서 빼야하는 조건이 있다. 이러한 특성을 후입선출(Last-In First-Out)이라 한다. 그림으로 표현하자면

 

위와 같은 스택이 있고 A가 맨 처음 삽입된 원소라 가정하자. 그 다음 삽입연산 push(B)를 실행하면 원소 B가 A위에 삽입이 된다. 

그 다음 제거(또는 반환) 연산 pop()을 실행하면 가장 최근에 삽입된, 맨 위에 있는 원소 B가 제거된다.

pop()연산은 특정 원소를 지정하지 않는 것을 볼 수 있는데 스택의 특성상 무조건 맨 위 원소를 제거하기 때문이다.

 

스택의 추상적 자료구조를 배열로 표현한 코드는 다음과 같다.

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList


class ArrayStack:

	def __init__(self):
		self.data = []

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

	def isEmpty(self):
		return self.size() == 0

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

	def pop(self):
		return self.data.pop()

	def peek(self):
		return self.data[-1]

스택의 연산은 대표적으로 위 5가지 연산이 있다. 

 

size() : 스택에 들어 있는 원소 개수 추출

isEmpty() :  스택이 비어있는지에 대해 판단

push(x) : 원소 x를 스택에 삽입

pop() : 스택의 맨 위 원소 삭제

peek() : 스택의 맨 위 원소 참조

 

연결 리스트로 표현한 코드는 다음과 같다.

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

구성은 배열의 경우와 비슷한 것을 볼 수 있다.

 

 

스택의 특성을 이용해 다양한 문제를 해결할 수 있는데 그 중 수식의 괄호 유효성 검사이다. 연산자가 포함된 어떠한 수식이 올바른 수식인지 판단할 수 있는 문제이다.

 

(A+B)같은 경우 올바른 수식이고, (A+B 같이 올바르지 않은 수식을 판단하는 문제이다. 모든 수식의 괄호는 여닫이가 있어야 하는데 한쪽에만 있는 경우 스택의 특성을 이용해 효율적으로 찾아낼 수 있다.

 

문제 설명

 

소괄호: ( )
중괄호: { }
대괄호: [ ]
를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.

 

 

문자열 expr을 차례로 읽는데 여는 괄호 ({[를 만나면 임의의 스택에 push를한다. 그 후 닫는 괄호 )}]를 만나는 경우에 두가지 경우로 나뉜다.

만약 )}]를 만난 시점에 스택이 비어있다면 ({[를 이전에 만나지 못했다는 뜻이다. 즉 수식이 A+B) 와 같은 식으로 올바르지 않은 수식이란 뜻이다.

스택이 비어있지 않다면 ({[중 무언가가 이전에 있다는 뜻인데 쌍을 이루는 괄호인지 검사를 해야한다. 이 방법은 코드에서 설명하겠다.

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
            S.push(c)
        elif c in match:
            if S.isEmpty():
                return False
            else:  
                t=S.pop()
                if t != match[c]:
                    return False
     return S.isEmpty()

여는 괄호 ({[를 만나는 경우 push를 이용해 스택에 삽입한다.

 

닫는 괄호 )}]를 만나고 스택이 비어 있으면 위에서 설명한대로 False를 리턴하도록 한다. 이 때 isEmpty()를 이용해 스택이 비어있는지 검사한다.

 

닫는 괄호 )}]를 만나고 스택이 비어 있지 않은 경우 쌍을 이루는 괄호인지 검사를 하는데 이는 딕셔너리를 이용했다.

위의 match 변수는 dict이라고 부르는 데이터 타입이다. 어떤 닫는 괄호를 여는 괄호와 대응시킨 것을 볼 수 있다. 

t=S.pop()은 스택의 맨 마지막 원소를 빼내오는 연산인데 이는 마지막에 읽힌 닫는 괄호 )}]중 하나이고 여는 괄호와 쌍을 이루는지 딕셔녀리 match[c]와 비교해 유효성 검사를 하는 것이다.

 

 

후입선출의 특성을 가지는 스택은 push와 pop 두 연산을 제공하는 간단 자료구조지만 컴퓨터 내부, 응용 프로그램 작성 등 여러 곳에서 쓰인다고 한다.