[자료구조] 순열자료구조 Stack

Stack이란?

LIFO

Last In First Out: 마지막에 들어온것을 먼저 내보내는 자료구조

값을 추가할땐 push라고 하며 빼낼땐 pop이라고한다

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, value):
        self.items.append(value)
        
    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print('Stack is empty')
        
    def top(self):
        try:
            return self.items[:-1]
        except IndexError:
            print('Stack is empty')
    
    def __len__(self):
        return len(self.items)

Stack클래스에 구현해 놓은 기능

• push : 하나의 값을 추가한다
• pop : 마지막 값을 삭제하고 그 값을 리턴한다
• top : 마지막 값을 리턴한다(삭제되지 않는다)
• len : 인스턴스의 총 길이를 리턴한다

Stack에서 지원하는 메서드들의 시간복잡도

push,pop,top은 n(1)의 시간복잡도를 가진다 하지만 len()은 어떨까?

답은 n(1)이다 이유는 python의 list가 길이를 항상 관리하고 있기때문에 그렇다고한다.

Stack을 활용한 문제

input = '[][[]'    # x
input = '[][][]'   # o
input = ']][][['   # x

위와같이 괄호의 쌍이 맞는지에 대한 문제를 스택방식으로 풀어보자

input_str = '[[][]]'
stack = Stack()

def test(input_str):
    for i in input_str:
        if i == '[':              
            stack.push(i)    # '['를 만난다면 stack에 push
        else if i == ']':
            stack.pop()      # ']'를 만난다면 stack을 pop
        else:                    
            return False # 괄호를 제외한 문자가 나온다면 에러

    if len(stack) > 0:
        return False   # 최종적으로 stack의 길이가 0보다 크면 짝이 안맞다는의미
    else:
        return True

 

여러종류의 괄호를 스택방식으로 풀어보기

input = '[]{}()' # o
input = '{]{]'   # x
input = '[()()]' # o

input_str = '[()()]'
stack = Stack()

def test(input_str):
    config = {
        '(' : ')' ,
        '[' : ']' ,
        '{' : '}'
    }
    for i in input_str:
        if i in config.keys():              
            stack.push(confg[i])    # 여는 괄호를 만난다면 stack에 상응하는 닫는괄호를 push
        elif i in config.values():  # 닫는 괄호를 만나면
            if stack.pop() != i:    # stack.pop()과 i 가 같지않다면 False
                return False
            else:
               stack.pop()      # 같다면 stack을 pop()
        else:                    
            return False # 괄호를 제외한 문자가 나온다면 에러

    if len(stack) > 0:
        return False   # 최종적으로 stack의 길이가 0보다 크면 짝이 안맞다는의미
    else:
        return True

사실 파이썬에서는 이런 과정없이 쉽게 푸는방법이 있다.!

def test(str):
    while str.find('()')!= -1 or str.find('[]') != -1 or str.find('{}') != -1:
        str = str.replace('()', '')
        str = str.replace('[]', '')
        str = str.replace('{}', '')
        print(str)
    
    if len(str):
       return False
    else:
       return True