[알고리즘 강의] 파트11. 스택(Stacks)

스택(Stack)

- 자료 (data elemenet)를 보관할 수 있는 (선형) 구조

- 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 -> 푸시 (push) 연산

- 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> 팝 (pop) 연산

- 후입 선출 (LIFO - Last-In First-Out) 특징을 가지는 선형 자료구조

 

스택의 동작

S=Stack()

S.push(A)
S.push(B)

r1 = S.pop() # B가 꺼내짐
r2 = S.pop() # A가 꺼내짐

 

스택에서 발생하는 오류

1) 비어 있는 스택에서 데이터 원소를 꺼내려 할 때

-> 스택 언더플로우 오류(stack underflow)

 

2) 꽉 찬 스택에 데이터 원소를 넣으려 할 때

-> 스택 오버플로우 오류(stack overflow)

 

스택의 추상적 자료구조 구현 

(1) 배열(array)을 이용하여 구현

- Python 리스트와 메서드들을 이용

 

(2) 연결 리스트 (linked list)를 이용하여 구현

- 지난 강의에서 마련한 양방향 연결 리스트 이용

 

연산의 정의

- size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함

- isEmpty() - 현재 스택이 비어 있는지를 판단

- push(x) - 데이터 원소 x를 스택에 추가

- pop() - 스택의 맨 위에 저장된 데이터 원소를 제거 (또한, 반환)

- peek() - 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)

 

배열로 구현한 스택

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]

 

연결 리스트로 구현한 스택

class LinkedListStack:
  def __init__(self):
    self.data = DoublyLinkedList()

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

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

  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

 

파이썬 라이브러리 사용

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

 

연습문제 - 수식의 괄호 유효성 검사

알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서:

1) 여는 괄호 - ( 또는 { 또는 [ - 를 만나면 스택에 푸시

2) 닫는 괄호 - ) 또는 } 또는 ] - 를 만나면:

- 스택이 비어 있으면 올바르지 않은 수식

- 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사

ㄴ 맞지 않으면 올바르지 않은 수식

3) 끝까지 검사한 후, 스택이 비어 있어야 올바른 수식

 

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[c]:
                    return False
                    
    return S.isEmpty()

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.