stack 스택 python

stack 스택 python

스택은 LIFO(Last Input First Out, 후입 선출)입니다. 나중에 들어온 것이 가장 먼저 꺼내게 됩니다.

함수 호출이 끝나고, 이전 context로 돌아 갈 때 사용 됩니다.

스택에 원소를 넣는 작업을 push, 원소를 꺼내는 작업을 pop이라고 합니다. 두 연산은 O(1)에 이루어져야 합니다.

스택을 활용한 문제를 쉽게 예로 들면 괄호 (), {}, [] 앞 뒤로 짝을 맞추는 Parentheses 문제에서 사용 가능합니다.

Parentheses 은 한 번 열린 괄호는 반대편에서 순서대로 닫혀야 합니다. 

{ { { { } } } { { } } } { }

{ 여는 괄호라면 push()로 넣고, }는 괄호라면 pop()로 꺼내서 괄호와 서로 맞춰보면 됩니다. 다르다는 것은 { 열고 } 닫은 개수가 같지 않다는 것이니 False 입니다. 이 풀이는 밑에서 보시죠!

stack 구현

https://github.com/KimJeongChul/algorithm-python/blob/master/data-structure/stack.ipynb

stack은 python list에 append()와 pop()이라는 것을 통해서 구현이 되어 있습니다.

따로 C++에서 STL stack 라이브러리를 이용하거나 따로 구현할 필요도 없죠. 

class로 구현을 해본다면 다음과 같습니다.

class Stack(list):     push = list.append # push     pop = list.pop # pop         def is_empty(self):         if not self:             return True         else:             return False

위의 클래스를 사용해본다면,

stack = Stack() stack.push(1) print("stack", stack) stack.push(2) print("stack", stack) # stack [1, 2] stack.push(3) print("stack", stack) # stack [1, 2, 3] stack.pop() print("stack", stack) # stack [1, 2]

list 없이 구현해야 된다면, Node(data, next)를 새로 class로 구현합니다.

class Node:     def __init__(self, data):         self.data = data         self.next = None # 자신과 연결된 다음 Node를 가르킴 class Stack:     def __init__(self):         self.head = None         def is_empty(self):         if not self.head:             return True         else:             return False         def push(self, data):         node = Node(data)         node.next = self.   head # head는 나중에 들어온 node가 된다.         self.head = node         def pop(self):         if self.is_empty():             return None         result = self.head.data # 현재 head의 data를 반환         self.head = self.head.next # head를 바꿔줍니다.         return result         def element(self):         top = self.head         head = self.head         result = [head.data]         while head.next != None:             head = head.next             result.append(head.data)         self.head = top         return result[::-1] # reverse 정렬

        

사용하는 법은

stack = Stack() stack.push(1) print("stack", stack.element()) stack.push(2) print("stack", stack.element()) # stack [1, 2] stack.push(3) print("stack", stack.element()) # stack [1, 2, 3] stack.pop() print("stack", stack.element()) # stack [1, 2]

자 마지막으로 위에서 설명한 짝이 맞는 괄호인지 살펴보는 Parentheses  문제 풀이법을 보죠.

stack을 이용해 구현하면 간단합니다. 괄호의 종류는 다양합니다. 여는 괄호 { [ (, 닫는 괄호 } ] )가 있습니다.

[1] 들어오는 문자열을 하나씩 확인합니다.
[2] 여는 괄호에 들어오는 문자라면 ( if t in open_), stack에 push로 넣습니다.

[3] 닫는 괄호 문자라면 pop을 해내고, 같은 괄호로 열려서 닫히는지 확인해야겠죠?

[4] 확인하는 방식은 문자열의 같은 인덱스에 위치하는지 확인하면 됩니다. 문자열.find()를 써서 open_과 close_ 인덱스가 같다면 같은 괄호일 것입니다.

[5] 최종적으로 stack이 모두 비었는지 확인을 합니다.(if not stack), 비어있다면 True, 아직도 괄호가 남아있다면 False겠죠.

def solution(test):     stack = []     for t in test:         open_ = '{[('         close_ = '}])'         if t in open_: # push             stack.append(t)         else: # pop             if open_.find(stack.pop()) != close_.find(t):                 # 괄호 {} [] () 일치하지 않는다면 Alse                 return False     if not stack:         return True     else:         return False