스택 (Stack)

스택 (Stack)

스택이란 ⁉️

• 스택은 Last In First Out(LIFO) 즉, 가장 마지막에 들어온 데이터가 가장 처음으로 나가는 자료구조이다.
• 함수 콜 스택, 인터럽트 처리 순서 등에 스택 자료구조가 활용된다.
• 주요 연산자로는 push(), pop(), peek(), is_empty()가 있다.

스택의 연산자

1. push()
   • 자료를 top 위에 삽입하는 연산자
2. pop()
   • 자료를 top에서 꺼내는 연산자
3. peek()
   • 현재 top에 있는 자료가 무엇인지 확인하는 연산자
4. is_empty()
   • 현재 stack이 비어있는지 확인하는 연산자

스택 연산자 구현 (Python Class) 📝

class Stack:
    def __init__(self):
        self.stk = [] # 스택 초기화 

    def push(self, value):
        self.stk.append(value)

    def pop(self):
        # 현재 스택이 비어있는 상태라면 -> None 반환 
        if self.is_empty():
            return None
        else:
            return self.stk.pop()

    def peek(self):
        # 현재 스택이 비어있는 상태라면 -> None 반환
        if self.is_empty():
            return None
        else:
            return self.stk[-1]

    def is_empty(self):
        return True if len(self.stk) else False	

배열을 활용한 스택

크기가 이미 정해진 배열을 스택으로 활용하게 될 경우

• 장점
  • 메모리상 자료가 연속적으로 존재하기 때문에 동작 속도가 빠르다.
• 단점
  • 크기가 정해지는 배열 자료구조의 한계로 스택이 가득 찬 상태에서 push() 하면 Overflow 발생
  • 마찬가지로, 스택이 비어있는 상태에서 pop() 하면 Underflow 발생

Python 리스트를 활용한 스택

크기가 가변적인 리스트를 스택으로 활용하게 될 경우

• 장점
  • 크기가 가변적이므로, Overflow 와 Underflow 오류에 대해서 자유롭다.
• 단점
  • append() 과 pop() 연산을 통해서 사이즈를 지속적으로 변경해줘야 하므로 자료의 추가와 삭제가 잦은 경우 동작 속도 면에서 비효율적인 상황이 발생한다.