[파이썬 자료구조] 스택(stack) - 스택의 개념, 구현, 스택을 활용한 수식의 괄호 검사

스택이란?

• 후입 선출 형태의 선형 자료구조. -> 가장 최근에 집어넣은 자료부터 꺼낸다.

출처: https://levelup.gitconnected.com/my-journey-to-learning-data-structures-from-scratch-stacks-1179494fd8f2

push → 집어 넣는 것.

pop → 빼는 것.

 

 

1. 스택 연산의 정의

• size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함
• isEmpty() - 현재 스택이 비어 있는지를 판단
• push(x) - 데이터 원소 x를 스택에 추가
• pop() - 스택의 맨 위에 저장된 데이터 원소를 제거 (또한, 반환)
• peek() - 스택의 맨위에 저장된 데이터 원소를 반환( 제거하지 않음)

 

2. 스택에서 발생하는 오류

1. 스택 언더 플로우 (stack underflow) : 비어있는 스택에서 데이터 원소를 꺼내려 할 때
2. 스택 오버 플로우 (stack overflow) : 꽉 찬 스택에 데이터 원소를 넣으려 할 때

 

3. 스택을 추상적 자료구조로 구현

1. 배열 → python 리스트와 메서드 들을 이용

class ArrayStack:
    def __init__(self): # 스택을 초기화
        self.data=[]
    def size(self): # 스택의 크기 리턴
        return len(self.data)

    def isEmpty(self): # 스택이 비어있는지 판단
        return self.size()==0
    
    def push(self,item): # 데이터 원소를 추가
        self.data.append(item)

    def pop(self): # 데이터 원소 삭제(리턴)
        return self.data.pop()
    
    def peek(self): # 스택의 꼭대기 원소 반환
        return self.data[-1]

 

   2. 연결리스트 (linked list) 를 이용하여 구현 → 지난 강의에서 마련한 양방향 연결 리스트 이용

from dd import * # 이미 만들어 놓은 더블링크드 리스트 파일을 불러온다.
# https://polarmin.tistory.com/9 이곳에 가면 더블링크드 리스트 코드가 나와 있습니다.
class LinkedListStack:
    def __init__(self):
        self.data=DoublyLinkedList()
    
    def size(self):
        return self.data.getLength()
    
    def isEmpty(self):
        return self.size()==0 # return에 불리언이 있으면 True 혹은 False를 반환한다.
    
    def push(self,item):
        node=Node(item)
        self.data.insertAt(self.size()+1,node)

    def pop(self):
        return self.data.popAt(self.size())

    def peek(self):
        return self.data.getAt(self.size()).data

 

이미 만들어진 스택 라이브러리도 있다. import해서 사용할 수 있다.

from pythonds.basic.stack import Stack
s=Stack()
dir(s)
# __doc__, __init__, __module__, isEmpty, items, peek, 
# pop, push, size

 

연습문제 (수식의 괄호 검사)

class ArrayStack:
    
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]


def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
            S.push(c)

        elif c in match:
            if S.isEmpty(): # 스택이 비어 있는지 확인.
                return False
            else:
                t=S.pop() 

                if t != match.get(c): # 짝이 맞는지 확인
                    return False
    return S.isEmpty() # 짝을 다 맞춘후 스택이 비어있으면 True. 한개 이상 남아있으면 False