스택... 지난번에 백준에서 현욱은 괄호왕이야!!!문제를 풀려고 했을때 지금 나올 스택을 활용하여 해결하고자 했으나, 역시 응용이 안됐다. 기본기의 부족때문일까...
스택
미로에서 길을 찾는 문제와 같이 삽입 순서와 삭제 순서를 역순으로 하여 풀어야 하는 문제들이 있는데, 이럴때 쓰는 자료 구조가 스택입니다.
스택의 예로는 대부분 팬케이크와 연탄에 빗대어 표현하곤 한다. 팬케이크는 아래로부터 차곡차곡 쌓이며 위에서부터 차근차근 먹는다. 이를 후입선출(나중에 들어온 요소가 먼저 나가는 방식), LIFO(Last in first out)라고 부른다.
스택은 배열로 간단하게 구현할 수 있지만 배열로 구현할 경우 이후에 크기를 변경하는게 어렵다. 언제나 그렇듯 파이썬은 예외다. C에서 스택을 구현할 경우 가장 이상적인 모델은 앞서 익힌 연결 리스트 방식을 사용하는 것이라고 한다.
스택에서는 삽입과 삭제를 push, pop이라고 부르는데 push는 팬케이크를 쌓는 것, pop은 팬케이크를 먹는 것이라고 생각하면 된다.
C 언어에서 스택을 구현할 때는 top과 배열을 이용해서 간단하게 구현했었다. 다만 파이썬으로 작업하면서 굳이 top이 필요한지 의문이 들었고 이 페이지의 소스코드에선 top이 등장하지 않는다.
이유는 간단하다 단순 연결 리스트를 활용해서 구현할 것이기 때문이다. head가 top이 되면 된다. (결국 그게 탑인가?) 필자의 말에서 top의 의미는 숫자형의 변수를 의미하며 물론 size를 기억하려면 top은 있는게 좋겠다. 스택에 쌓여질 노드의 구조는 아래와 같다.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
def __str__(self):
return str(self.data)단순 연결 리스트와 동일한 구조의 노드이지만 이번엔 next가 아니라 prev를 사용하였다. 스택의 경우 앞서 말했듯 후입선출의 구조이므로 나중에 들어온 개체가 무조건 헤드가 될 예정이다.
PUSH
def push(self, data):
new_node = Node(data)
if self.head == None:
# 헤드가 없는 경우(최초 PUSH)
self.head = new_node
return
# 새 노드의 이전 링크 저장
new_node.prev = self.head
# 헤드 교체
self.head = new_nodePOP
def pop(self):
node = self.head
try:
# 스택이 비어있는 경우 대비
value = node.data ; del node
self.top -= 1
self.head = self.head.prev
except:
# 스택이 비어있는 경우
value = None
return value스택 전체 소스코드
class Node:
def __init__(self, data):
self.data = data
self.prev = None
def __str__(self):
return str(self.data)
class Stack:
def __init__(self):
self.head = None
self.top = 0
def __str__(self):
print_stack = '<=> [ '
node = self.head
while True:
try:
print_stack += str(node)
if node.prev == None:
break
node = node.prev
print_stack += ', '
except:
break
print_stack += ' ]'
return print_stack
def push(self, data):
new_node = Node(data)
if self.head == None:
self.head = new_node
return
new_node.prev = self.head
self.head = new_node
self.top += 1
def pop(self):
node = self.head
try:
value = node.data ; del node
self.top -= 1
self.head = self.head.prev
except:
value = None
return value
if __name__=="__main__":
m_stack = Stack()
m_stack.push(5)
m_stack.push(4)
m_stack.push(3)
print(m_stack)
print('Stack pop :', m_stack.pop())
print(m_stack)
print('Stack pop :', m_stack.pop())
print('Stack pop :', m_stack.pop())
print(m_stack)<=> [ 3, 4, 5 ]
Stack pop : 3
<=> [ 4, 5 ]
Stack pop : 4
Stack pop : 5
<=> [ None ]스택 응용하기
아까 서두에서 잠시 등장했지만 스택을 어떻게 활용할 수 있을까? 참고하는 책에서도 괄호의 수식을 검사하는데 아주 적합하다고 평가한다. 여기서는 언급했던 백준 문제를 다루진 않지만 응용한다면 해결이 충분해 보인다.
여는 괄호가 등장하면 스택에 push해주고 닫는 괄호가 등장하면 스택에서 pop을 해주고 닫는 괄호와 일치한지 검사한다. 같으면 아직까지는 올바른 수식이고 다르면 틀린 수식이다. 올바른 수식인 상태로 성공적으로 끝나면 정말로 올바른 수식인 것이다.
if __name__=="__main__":
m_stack = Stack()
calcul1 = '[(A+B)*(A+C)]/(B-C)'
calcul2 = '[(A+B)*(A+C]/B-C)'
is_pair = False
for cal in calcul2:
if cal == '(' or cal == '[':
m_stack.push(cal)
print(m_stack)
if cal == ')':
if m_stack.pop() == '(':
is_pair = True
else:
is_pair = False
if cal == ']':
if m_stack.pop() == '[':
is_pair = True
else:
is_pair = False
if is_pair:
print('calcul2 :',calcul2,'은 올바른 수식 입니다.')
else:
print('calcul2 :',calcul2,'은 잘못된 수식 입니다.')파이썬에선 별도의 스택을 구현하지 않아도 리스트를 스택처럼 활용할 수 있다. 아래는 간단한 예제 코드이다.
m_stack = []
m_stack.append(4)
m_stack.append(7)
print(m_stack)
print("POP Element :", m_stack.pop())
print(m_stack)
print("POP Element :", m_stack.pop())
print(m_stack)
Ghost