[자료구조] - (2) 스택(Stacks) with Python — 다은이의 컴퓨터 공부

스택(Stacks) 역시 추상적 선형 자료 구조 중 하나이다.

본 게시글은 Python 코드로 작성되었습니다.

1. 스택의 구조

기본적으로 스택은 넣을 때는 한쪽 끝에서 밀어넣어야 하고(push), 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야한다.(pop) 간단히 그림으로 나타내면 다음과 같다.

이와 비슷한 선형 자료구조 큐(Queue)는 좀 다르다. 큐는 '선입선출'의 구조로서, 먼저 들어간 요소가 가장 먼저 나오는 구조이다. 기본적으로 스택은 한쪽에서 꺼내고 빼고를 하는 반면, 큐는 한쪽에서 들어가면 다른쪽에서 나온다! 그리고 스택은 가장 마지막에 들어간 요소가 가장 먼저 나온다 (후입선출)

스택에는 정해진 저장 공간이 있다. 따라서 비어있는 스택에서 원소를 꺼내려 하거나, 꽉찬 스택에 데이터 원소를 넣으려고 할 때 문제가 발생한다. 이러한 문제들을 각각 Stack underflow, Stack overflow라고 칭한다.

2. 스택의 연산 및 구현

스택의 연산에는 총 5가지가 있다. 각각은 다음과 같다.

1) Size : 현재 스택에 들어있는 원소의 수를 반환
2) isEmpty() : 현재 스택이 비어있는지를 판단
3) push(x) : 데이터 원소 x를 스택에 추가
4) pop() : 스택의 맨 위에 저장된 원소를 제거 (맨 마지막에 들어온게 맨 먼저 나옴)
5) peek() : 스택의 꼭대기(맨 마지막으로 push된, 앞으로 pop의 대상이 되는) 원소를 반환

이들은 각각 Python의 배열과 양방향 연결리스트로 구현될 수 있다.

# Python의 리스트로 스택 구현하기
class ArrayStack:

    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]

양방향 연결리스트로도 동일한 작업을 수행할 수 있다.

# 양방향 연결리스트 정의
class Node:
    def __init__(self, item):
    	self.data = item
        self.prev = None
        self.next = None   # 양방향으로 연결된 모습
    
class DoublyLinkedList:
    def __init__(self, item):
    	self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None
 
 # 양방향 연결리스트로 스택 구현
 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

3. 스택의 활용

1) 수식의 괄호의 유효성 검증하기

수식의 소괄호, 중괄호, 대괄호가 맞게 쓰였는지 판단하는 알고리즘을 스택을 통해 구현할 수 있다. 수식을 왼쪽부터 한글자씩 읽어서, 여는 괄호 (,{,[ 를 만나면 스택에 push 하고, 닫힌 괄호를 만나면 스택에서 pop하여 딕셔너리의 쌍을 이루는 괄호인지 검사한다. 끝까지 검사한 후에는 스택에 비어있어야 올바른 수식이다.

이를 python을 통해 구현해보자.

Point는 열린괄호와 닫힌괄호를 딕셔너리를 통해 쌍을 지어주는 것이다! (닫힌 괄호를 key로 지정하기)

def solution(expr):
    match = {')' : '(', 
             '}':'{', 
             ']':'['
            }         # 맞는 괄호를 딕셔너리로 지정
    
    S = ArrayStack()
    for c in expr:
        if c in '({[':    # 여는 괄호를 스택에 넣음
            S.push(c)
            
        elif c in match:  # 닫힌 괄호(key)일 때
            
            if S.isEmpty():  # 만약 스택이 비어있으면 False
                return False
            
            else:
                t = S.pop()
                if t != match[c]:  # 스택에 담긴 괄호(열린괄호)와 닫힌 괄호가 같지 않으면
                    return False
                
    return S.isEmpty()   # 끝까지 검사한 후 스택이 비어있어야 올바른 수식

2) 중위표기법(Infix notation)을 후위표기법(Postfix notation)으로 변환

우선 중위표기법은 연산자가 피연산자들의 사이에 위치하는 일반적인 수식 표기법이다. ex) (A+B) * (C+B)
하지만 후위표기법은 연산자가 피연산자들의 뒤에 위치하는 수식 표기법이다. ex) AB + CD +*

이러한 중위표기법을 후위표기법으로 스택을 이용해 바꾸는 알고리즘을 설계할 수 있다. 우리는 연산자의 우선순위를 지키기 위해 스택을 사용한다. 일반적인 프로세스는 다음과 같다.

우선 연산자의 우선순위를 설정하는 딕셔너리를 만들어야한다.

# 우선순위 딕셔너리
prec={
    '*':3, '/':3, '+':2, '-':2, '(':1
}

그리고 중위표현식을 왼쪽부터 한글자씩 읽어나가며,

1) 피연산자이면 그냥 출력
2) 여는 괄호이면 스택에 push, 닫는 괄호이면 여는 괄호가 나올 때까지 스택에서 pop
3) 연산자이면 스택에서 이보다 높(같은) 우선순위의 것들을 pop
4) 마지막에는 스택에 남아있는 연산자들을 모두 pop한다.

이를 코드로 구현해보면 다음과 같다.

# 인자로 앞 함수의 리스트가 주어짐

# 스택의 array class 정의
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]

    
def solution(S):
    prec={
        '*':3, '/':3, '+':2, '-':2, '(':1
    }
    answer = ''
    opStack = ArrayStack()

    for c in S:
        
        ## 1. 사칙연산자일 때 
        if c in '*/+-' :
            while not opStack.isEmpty():   # 비어있지 않을 때(peek 예외 회피)
                 
                # 새로운 연산자의 우선순위가 높을 때
                if prec[opStack.peek()]<prec[c]:  
                    break
                
                answer += opStack.pop()
            
            opStack.push(c)
        
        ## 2. 열린 괄호일 때
        elif c == '(':
            opStack.push(c)
        
        ## 3. 닫힌 괄호일 때
        elif c == ')':
            # 열린 괄호가 되지 않을때까지
            while not opStack.peek() == '(':
                answer += opStack.pop()
                
            opStack.pop()   # 스택 초기화
             
                
        ## 4. 피연산자일 때
        else: 
            answer += c # 그냥 append
            
            
    # 마지막 스택에 남아있는 것들 전부다 pop해서 answer에 삽입
    while not opStack.isEmpty():
        answer += opStack.pop()
    
    return answer

solution('(A+B)*(C+D)')

그리고 이 후위표현식을 연산할 때는 피연산자일 때 스택에 push하고, 연산자를 만나면 스택에서 피연산자를 pop해 연산하여 스택에 push하면 된다.