[Python 자료구조] 스택 (Stack)

💡 Goal
- 스택을 이해한다.
- 스택을 파이썬으로 구현한다.
- 스택 특징 2가지 이상 말하기.

개념

---

LIFO(Last In First Out)으로 동작하며 데이터간 순서를 약속하는 추상자료형

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

마치 스시를 다 먹고 접시를 쌓아 올리는 형태와 같은 개념으로 처음 쌓은 접시가 가장 나중에 제거

특징

---

• 스택의 활용
  • 컴퓨터 내부 프로세스 실행 구조의 함수 동작
    • 함수는 가장 나중에 호출된 것이 가장 먼저 종료
  • 웹 브라우저 방문 기록
  • 역순 문자열 생성
• 구조가 단순해 구현이 쉬움
  • 데이터를 삽입, 삭제, 접근이 가능한 자료형
• 파이썬으로 코드를 구현할때 deque를 사용하거나 list를 사용
  • 스택은 단순히 빠른 성능을 위해 사용되기에 배열 구조를 활용해 구현
  • deque → doubly-ended-queue
• 데이터 저장 및 읽기 속도가 빠름

시간복잡도 O(1)

python list로 스택을 구현할 수 있지만 list는 resize시 동적배열의 크기를 생성하고
값을 복사하기 때문에 2n의 시간복잡도 즉, O(n)이 발생 (이럴 경우 deque를 사용하면 해결)

코드 구현

---

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

    def __len__(self) -> int:
        return len(self.items)

    def clear(self):
        self.items = []

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

    # 스택의 가장 위에 원소 1개를 제거후 남은 리스트 반환
    def pop(self):
        if not self.is_empty():
            return self.items.pop(-1)
        else:
            print("underflow")
            exit()

    # 가장 위에 있는 원소 1개 반환
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            print("underflow")
            exit()

    # 스택이 존재하는지 체크
    def is_empty(self) -> bool:
        return len(self.items) == 0

stack = Stack()

print(stack.is_empty())

if stack.is_empty(): stack.push(1)

stack.push(10)
stack.push(5)
stack.pop()
print(stack.items[0])

print(stack.items) # 1, 10
print(stack.peek()) # 10

References

• https://www.codeit.kr/courses/data-structures