[자료구조] 스택

정의

기본적인 자료 구조의 한 가지로, 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO : Last In First Out)으로 되어 있다.

연산

스택의 핵심 연산은 push와 pop이며, 스택의 길이에는 제한을 두어 오버 플로우가 발생할 수 있도록 한다.

class Stack(object):
    def __init__(self, limit):
    	self.stack = []
        self.limit = limit
        
    # stack의 내용을 print
    def __str__(self):
    	return ''.join([str(i) for i in self.stack])
        
    def push(self, data):
    	if len(self.stack) >= self.limit:
            print("Stack Overflow!!!)
        else:
            self.stack.append(data)
            
    def pop(self, data):
    	if len(self.stack) <= 0:
            return -1
        else:
            return self.stack.pop()

이 외에도 peek라는 연산이 존재한다. peek는 pop을 하지 않고 스택의 top이 가리키는 데이터를 확인할 수 있다.

def peek(self):
    if len(self.stack) <= 0:
        return -1
    else:
        return stack[len(self.stack) - 1]

스택의 활용

스택은 알게모르게 다양한 곳에서 활용된다. 웹 서핑을 하면서 '뒤로 가기' 버튼을 누르면 가장 최근에 열린 페이지부터 다시 보여주며, 재귀 함수도 스택을 사용한다.

컴퓨터의 경우 사칙 연산을 이해할 때 후위 표기법을 사용하는 데 이 경우도 스택이 사용된다.

후위표기법

진행 과정

① 피연산자는 스택에 넣지 않고 출력한다.
② 연산자는 스택이 비었으면 스택에 push한다.
③ 연산자는 스택이 비어있지 않으면 스택에 있는 연산자와의 우선순위를 비교해 스택에 있는 연산자의 우선순위보다 같거나 크다면
스택에 있는 연산자를 pop한 후 출력하고 현재 연산자는 스택에 push한다.
④ 만약 ③에서 현재 연산자의 우선순위가 더 크면 현재 연산자를 push한다.(pop 수행 X)
⑤ 수식이 끝나면 스택이 빌 때까지 pop을 한 후 출력한다.

괄호가 있는 경우

① '(' 는 무조건 push한다.
② ')' 는 stack에서 '('가 나올 때까지 pop을 한 후 출력한다.
③ '(' 가 스택에 push된 후 ')'가 나올 때까지 '('가 pop되면 안 되므로 '('의 우선 순위는 제일 낮다.
④ 괄호는 출력하지 않는다.

백준 - 후위 표기식

priority = {
    '*':2,
    '/':2,
    '+':1,
    '-':1,
    '(':0
}
stack = []
for i in '(' + input() + ')':
    if i.isalpha():
        print(i, end='')
    elif i == '(':
        stack.append(i)
    elif i == ')':
        while True:
            p = stack.pop()
            if p == '(':
                break
            print(p, end='')
    else:
        while stack[-1] != '(' and priority[i] <= priority[stack[-1]]:
            print(stack.pop(), end='')
        stack.append(i)

카카오를 비롯한 코딩 테스트에서도 거의 매번 한 문제씩은 출제되는 문제인 듯 싶다. 기초를 탄탄히!