스택이란?

→ Last in First Out ( LIFO )

→ 바구니라고 생각하면 좋다.

→ 마지막에 들어간게 제일 먼저 나오는 자료 구조이다.

스택 직접 구현해보기

→ 스택을 직접 구현해보는것이 중요하다고 한다. 굉장히 간단해보이는 자료 구조이지만 실제로 구현해보자.

→ 노드 구현하기 (stack에 들어가는 노드)

→ 코드

item을 가지며 다음번째 노드를 가진다.

class Node :
    def __init__(self, item, next):
        self.item = item
        self.next = next

→ stack 구현하기

→ 스택의 기본 구조는 top을 지정해준다.

→ top은 스택에 자료가 쌓일 경우 가장 위에 있는 부분을 말한다.

class Stack :
    def __init__(self):
        self.top = None

→ is_empty : 스택이 비어있는지 확인해주는 함수

→ top이 비어있을 경우 스택에는 아무것도 없는 것.

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

→ push : 스택의 상단 top에 node를 추가해주는 함수

→ 간단하게 top에 새로운 노드를 추가해준다.

def push(self, val):
        self.top = Node(val, self.top)

→ pop : 스택의 상단을 제거하는 함수

→ top을 다음 top으로 연결해준다. 비어있을 경우 None.

def pop(self):
        if not self.top :
            return None

        node = self.top
        self.top = self.top.next

        return node.item