[Python] Stack

• 스택(stack)의 특성
  • 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.
  • 스택에 저장된 자료는 선형 구조를 갖는다.
    • 선형구조 : 자료 간의 관계가 1대1의 관계
    • 비선형구조 : 자료 간의 관계가 1대N의 관계 (예 : 트리)
  • 스택에 자료를 넣거나 꺼낼 수 있다.
  • 후입선출(LIFO : Last-In-First-Out)
  • 마지막 삽입된 원소의 위치 : top
  • 삽입 : push, 삭제 : pop
  • 스택이 공백인가 : isEmpty, 스택의 top에 있는 원소 반환 : peek

class MyStack():
    # top 변수를 이용해서 구현
    def __init__(self):
        self.top = -1
        self.size = 10
        self.stack = [0] * self.size

    # item 을 마지막 요소 뒤에 추가
    def push(self,item):
        if self.top == self.size-1:
            print('Stack Full')
        else:
            self.top += 1
            self.stack[self.top] = item

    # 마지막 요소를 반환하고 삭제
    def pop(self):
        if self.top == -1:
            print('Empty Stack')
        else:
            self.top -= 1
        return self.stack[self.top+1]

    # peek, isEmpty도 추가로 구현
    def peek(self):
        return self.stack[self.top]

    def isEmpty(self):
        if self.top == -1:
            return 'Empty'
        else:
            return 'Not Empty'

mystack = MyStack()
mystack.push(1)
mystack.push(2)
mystack.push(3)
print(mystack.pop())
print(mystack.pop())
print(mystack.peek())
print(mystack.isEmpty())
print(mystack.pop())
print(mystack.isEmpty())
# 출력결과
# 3 2 1 Not Empty 1 Empty

 

• 응용1 : 괄호 검사

# 괄호의 짝을 검사하는 프로그램
def check(data):
    stack = []
    for i in data:
        # 여는 괄호면 스택 push
        if i == '(':
            stack.append(i)
        # 닫는 괄호면 스택 pop
        else:
            # 여는 괄호가 먼저 나왔으면
            if stack:
                stack.pop()
            # 스택이 비어있으면  -> 짝이 맞지 않아 실패
            else:
                return False
    # 모두 검사했는데 여는 괄호가 남아있다면 - > 짝이 맞지 않아 실패
    if stack:
        return False
    return True

data1 = '()()((()))'
print(check(data1))
data2 = '((()(()))'
print(check(data2))