📍스택(Stack)

스택(Stack)은 한 쪽 끝에서만 접근하여 데이터를 넣고 뺄 수 있는 후입선출(LIFO) 형태의 선형 자료구조이다. 비유하자면 빨래통과 같다 🧺
가장 처음 넣은 빨래는 가장 늦게 나오고, 가장 마지막에 넣은 빨래는 가장 빨리 나온다. 새로운 빨래를 넣는다면 먼저 들어간 빨래보다 위에 쌓이는 형태일 것이다.

스택(Stack)은 LIFO/FILO 순서를 따른다
LIFO : 마지막에 들어온 값이 처음으로 나가는 것
FILO : 처음 들어온 값이 마지막에 나가는 것

📍스택(Stack)의 특징

• 스택 내부의 데이터는 top을 통해서만 접근 가능하다.
  top은 가장 마지막에 들어온 데이터를 의미
• 스택에 데이터를 삽입할 때는 top위에 삽입 -> push연산
• 스택에서 데이터를 삭제할 때는 top에 위치한 데이터를 삭제 -> pop연산

스택(Stack)은 시간 순서에 따라 데이터가 쌓이므로
가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 특징을 가진다.

📍스택(Stack)의 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거하고 반환한다.
• push(item): item 하나를 스택의 가장 윗 부분에 삽입한다.
• isEmpty(): 스택이 비어 있을때 True를 반환한다.
  isEmpty()는 Stack이 비어있는지 확하는 메서드이다.
  스택이 비어 있으면 True, 데이터가 있으면 False를 반환한다.
  

🔎 데이터 추가 - push()

스택(Stack)에 데이터를 삽입하면 가장 마지막 부분(최상단)에 삽입된다.
스택에 데이터를 삽입하는 push는 인덱스를 증가하면서 이루어진다.

• 1 : 스택이 가득 차 있는지 확인
• 2 : 스택이 가득 차있다면 오류 발생 및 종료
• 3 : 스택이 가득 차 있는 상태가 아니면 Top(가장 마지막에 들어온 데이터)이 증가
• 4 : Top이 가리키는 스택의 위치에 데이터를 삽입

🔎 데이터 삭제 - pop()

스택(Stack)에 데이터를 삭제하는 작업은 가장 위에 있는(가장 마지막에 추가된 데이터) 데이터를 제거한다.

• 1 : 스택이 비어 있는지 확인
• 2 : 스택이 비어 있으면 오류 발생 및 종료
• 3 : 스택이 비어 있지 않으면 Top이 가리는 데이터를 제거
• 4 : Top값을 제거

데이터 제거에서 중요한 것은 스택이 비어있어 삭제할 데이터가 없는 경우이다.

🔎 데이터 유무 확인 - isEmpty()

isEmpty()는 Stack이 비어있는지 확하는 메서드이다.
스택이 비어 있으면 True, 데이터가 있으면 False를 반환한다.

#Node, Stack

class Node: # 어떤 값을 가져야하고 가리키는 것이 무엇인지로 구성
    def __init__(self,item,next):
        self.item = item
        self.next = next

class Stack: # 제일 처음 탑을 지정, 스택을 처음 만들었을 땐 아무것도 없으니 None
    def __init__(self):
        self.top = None

    def push(self,val): # 탑을 노드로 지정
        self.top = Node(val,self.top) # 노드에 가지고 있는 값을 넣어줌
        # 새로 만든 탑이 가리키고 있는 것이 기존의 탑

    def pop(self): #
        if not self.top: #만약에 self에 top이 비어있다면
            return None
        #  None을 리턴

        # 있다면 , 그게 아니라면
        node = self.top # 탑을 꺼내기
        self.top = self.top.next # 탑을 교체
        # 제일 마지막(위)에 있는 자료의 다음을 새로운 top으로 지정
        return node.item # 노드에 값을 반환

    def is_empty(self):
        return self.top is None
    # top이 None인지 아닌지 판단 후 넘겨줌

🤖 유효한 괄호 검사하기

def is_valid_parenthesis(s):
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    opener = "({["
    stack = []

    for char in s: # s를 쭉 순회하며
        if char in opener: # s가 여는 녀석이면 stack에 append
            stack.append(char)
        else: # 그게 아니라면, 닫는 녀석이 나왔다면 -> 스택에 맨 위의 것과 쌍이 맞아야 함
            if not stack: # 스택이 비어있다면 ( 짝이 안맞다 )
                return False # False로 끝내기
            top = stack.pop() # 그게 아니고, 짝의 개수가 맞다면 제일 위에 있는 것을 꺼내서 그것이
            if pair[char] != top: # 와야 하는 것과 다르다면
                return False # False로 끝내기

    return not stack
# 소진되지 않고 여전히 남아있다면 / 스택이 비었는지 안비었는지만 검사해서 반환

🤕