[딩코딩코 2025 코딩테스트 필수 알고리즘] - 12. 스택

본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.

코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요

👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기

본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

---

스택

스택이란 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조이다.
특징으로는 LIFO : Last In First Out 인 후입선출 구조를 가지고 있다.

실생활적인 예시로는 빨래통을 생각해보면 된다.
가장 밑에 있는 빨래를 뺄 수 없고, 가장 위에서만 빨래를 빼거나 넣을 수 있다.

즉, 가장 최근에 넣은 걸 먼저 뽑고 예전에 넣은 걸 늦게 뽑고 싶을 때 사용하면 된다.

스택 구현

스택이라는 자료구조는 다음 기능을 제공한다.

• push(data) : 맨 앞에 데이터 넣기
• pop() : 맨 앞의 데이터 뽑기
• peek() : 맨 앞의 데이터 보기
• isEmpty() : 스택이 비었는지 안 비었는지 여부 반환

스택을 구현하려고 하는데 어떻게 구현하면 좋을까?
데이터를 넣고 뽑는 걸 자주하는 자료 구조인 링크드 리스트와 유사하게 구현할 수 있다.

push

스택에 push 하려면 어떻게 되어야 할까?
제일 위에 있는 데이터가 입력한 데이터가 되어야 한다.

링크드 리스트처럼 새로운 head 를 지정하려면
새로운 값을 담은 새로운 노드를 만들고,
그 노드의 다음 노드를 현재의 head 로 지정하고,
그 노드를 head 로 지정하면된다.

def push(self,value):
    new_head = Node(value)
    new_head.next = self.head
    self.head = new_head

pop

스택에 pop 을 하면 어떻게 되어야 할까?
제일 위에 있는 데이터가 빠져야 한다.

링크드 리스트처럼 head 를 제거하려면,
현재 head 의 값을 다른 변수에 저장해 둔 다음,
head 가 지칭하는 노드를 현재 head 의 다음 값으로 지정한다.
그리고 아까 저장해둔 head 를 반환해주면 된다.

def pop(self):
    if self.is_empty():
        return "Stack is empty"
    delete_head = self.head
    self.head = self.head.next
    return delete_head

peek

제일 위에 있는 노드를 반환해주면 된다.

def peek(self):
    if self.is_empty():
        return "Stack is empty"
    return self.head.data

is_empty

비어있는지 아닌지는 head 가 None 인지 아닌지 여부를 반환하면 된다.

def is_empty(self):
    return self.head is None