스택(Stack)

스택은 선입후출 알고리즘이다 (LIFO: Last In, First Out)

한쪽 끝(top)에서만 삽입(push)과 삭제(pop)이 일어난다

김치 냉장고에서 맨 아래 김치를 꺼내기 위해서

위의 김치를 꺼내듯이 스택도 마지막에 들어간 데이터부터 먼저 꺼내야 한다

코드 리뷰

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

    def push(self, x):
        self.data.append(x)

    def pop(self):
        return self.data.pop() if self.data else None

    def peek(self):
        return self.data[-1] if self.data else None

    def is_empty(self):
        return not self.data

Stack 클래스의 data가 데이터가 모여있는 리스트이다

push()를 하면 리스트에 값이 추가되고

pop()을 하면 맨 마지막 data가 나오게 된다

peek()는 맨 마지막의 data의 값을 볼 수 있다

is_empty()는 stack이 비었는지 확인 할 수 있다

시간 복잡도

연산	시간 복잡도	설명
push()	O(1)	리스트 끝에 추가
pop()	O(1)	리스트 끝에서 제거
peek()	O(1)	마지막 요소 조회
검색 / 삭제	O(N)	특정 값을 검색하거나 중간 요소 제거 시