🔑스택이란?

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조

스택이란 자료 구조는 "빨래통"을 떠올리자!
이런 자료 구조를 Last In First Out 이라고 해서 LIFO 라고 부른다.

🤷‍이런 자료 구조는 왜 필요할까!?

예를 들어 컴퓨터의 되돌리기(Ctrl + Z) 기능을 보자!
직전에 했던 행동을 되돌리고 싶을 때 사용하는 기능인데,
이를 위해서는 내가 했던 행동들을 순서대로 기억해야 하므로 스택을 사용한다.

👀스택의 구현

스택 이라는 자료 구조에서 제공하는 기능은 다음과 같다.

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

한 번, 직접 구현해보자

그 전에! 과연 스택은 뭘로 구현하면 좋을까?!
데이터 넣고 뽑는 걸 자주하는 자료 구조이기 때문에
앞서 배웠던 Linkedlist와 유사하게 구현할 수 있다.

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


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

    def push(self, value):                 # 현재 [4] 밖에 없다면
        new_head = Node(value)             # [3] 을 만들고!
        new_head.next = self.head          # [3] -> [4] 로 만든다음에
        self.head = new_head               # 현재 head의 값을 [3] 으로 바꿔준다.

    def pop(self):
        if self.is_empty():                  # 만약 비어있다면 에러!
            return "Stack is empty!"
        delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
        self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
        return delete_head                   # 그리고 제거할 node 반환

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

        return self.head.data

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

사실 상 python의 list와 동일한 개념이기 때문에
실제 코딩테스트에서는 list를 활용한다.