자료구조: Stack

Stack?

가장 마지막에 삽입된 데이터를 먼저 뺄 수 있는 방식(Last in First Out) 형식의 자료구조

 

Stack의 연산

• push(data) : data를 stack의 가장 마지막에 추가한다.
• pop() : stack의 가장 마지막에 추가된 data를 제거하고 반환한다.
• peek() : pop()과 달리 가장 최근에 마지막의 data를 반환하고, 제거하진 않는다.
• is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다.

 

Stack을 활용하는 경우

• 재귀 호출
  • 재귀적으로 함수를 호출하는 경우, 가장 마지막에 호출된 함수 부터 차례로 실행결과를 반환한다.
  • 따라서 재귀 호출의 경우 Stack을 통해 이를 가능하도록 한다.

• 수식의 괄호 검사

  • (())와 같은 괄호의 열림, 닫힘이 올바르게 쌍을 이루는지 판별하고자 할때 Stack을 활용하여 판단할 수 있다.
• 후위 표기법 변환 및 계산
  • 숫자를 stack에 넣은 후 연산 기호나 괄호를 만나면 해당 우선순위에 따라 숫자를 출력하여 중위 표기식을 후위 표기식으로 전환할 수 있으며, 계산도 가능하다.

 

Python으로 Stack 구현하기

class Stack:
    def __init__(self, size):
        self.size = size
        self.items = []

    def push(self, data):
        if len(self.items) < self.size:
            self.items.append(data)
        else:
            return -1

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

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

    def is_empty(self):
        return True if not self.items else False

• stack의 크기가 가변적이지 않다면, push할 경우에 overflow가 발생하는지도 확인하여야 한다.