[자료구조] 스택 (python)

스택

스택은 한 쪽 끝으로만 데이터를 넣고 뺄 수 있는 자료구조로, LIFO의 특성을 지닌다.
즉, 가장 늦게 삽입된 데이터가 가장 먼저 나오는 구조!

Ctrl+z같은 기능을 구현할 때 사용된다.

# 노드 클래스
class Node:
    # 생성자
    def __init__(self, data):
        self.data = data
        self.next = None

# 스택 (링크드 리스트로 구현)
class Stack:
    # 생성자
    def __init__(self):
        self.head = None

    # 추가
    def push(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            return

        new_node.next = self.head   # 새 노드의 다음 값을 head로 변경
        self.head = new_node        # head를 새 노드로 변경

    # 삭제
    def pop(self):
        if self.is_empty():
            return "stack is empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head

    # 가장 위의 값 출력
    def peek(self):
        if self.is_empty():
            return "stack is empty"
        return self.head.data

    # 비어있는 지 확인
    def is_empty(self):
        return self.head is None

• 스택은 데이터의 삽입/삭제가 빈번하기 때문에, 배열보다는 링크드 리스트로 구현하는 것이 바람직하다.
• push, pop 메소드를 보면 head포인터에서, 즉 한 쪽 끝에서만 삽입/삭제가 구현된 것을 확인할 수 있다.
• 실제로 사용할 땐, [] list를 사용한다.