📚 스택(Stack)

📚 스택(Stack)이란

한쪽으로만 자료를 넣고 뺄 수 있는 후입선출(LIFO: Last-In First-Out) 구조를 가진 자료구조.

데이터를 차곡차곡 쌓아 올린 형태이며, LIFO 구조이기 때문에 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.

📚 스택의 사용 사례

• 웹 브라우저 방문 기록(뒤로 가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

📚 스택 기본 연산

• push(): 스택에 원소 추가
• pop(): 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환
• peek(): 스택 가장 위에 있는 원소를 반환(삭제는 하지 않음)
• isEmpty(): 스택이 비어있으면 True, 비어있지 않다면 False를 반환
• size(): 스택의 원소 개수 반환

📚 파이썬으로 스택 구현하기

파이썬은 스택 자료구조는 따로 제공하지 않고, 리스트(list)를 통해 구현할 수 있다.
S.append() 리스트 맨 끝에 원소를 추가한다. 시간복잡도는 O(1)이다.
S.pop(i) 리스트의 i번째 원소를 삭제한다. S.pop(-1)은 맨 앞에 있는 원소를 삭제한다. 시간복잡도는 마찬가지로 O(1)이다.

클래스로 스택 구현

class Stack:
    # 리스트를 이용한 스택 구현
    def __init__(self):
        self.top = []
    
    # 구현 함수
    # 스택에 원소 삽입
    def push(self, item):
        self.top.append(item)
    # 스택 가장 위에 있는 원소를 삭제하고 반환
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
        else:
            print("Stack underflow")
            exit()
    # 스택 가장 위에 있는 원소를 반환
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            print("underflow")
            exit()
    # 스택이 비어있는 지를 bool 값으로 반환
    def isEmpty(self) -> bool:
        return len(self.top)==0
    # 스택의 크기를 int 값으로 반환
    def size(self) -> int:
        return len(self.top)

참고 사이트

https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

https://calmlife.tistory.com/11