[파이썬, 자료구조 알고리즘] Stack

Stack

 

빨래통에 빨래감을 담은 후 꺼내려고 할 때, 가장 마지막에 담은 빨래감을 가장 먼저 꺼내게 되듯이,

데이터를 한 곳에서만 넣고 뺄 수 있고, 마지막에 넣은 데이터를 가장 먼저 꺼낼 수 있는 Last In First Out 자료 구조.

 

처음부터 구현을 할 수 있어야 한다고 해서 직접 해보기로.

 

Stack에 들어가는 기본 단위를 Node이라고 한다. 이해하기 쉽게 Node를 빨래감이라고 하면,

빨래감 노드은 두가지로 구성된다. 내가 갖고 있는 빨래감과 다음에 넣을 빨래감을 가리키는 역할.

class 빨래감:
	def __init__(self, item, next) # 갖고있는 빨래감, 다음 빨래감을 가리키는 포인터
		self.item = item
   		self.next = next

 

 

그 다음은 스택(빨래통)을 만들어주면 되는데, 처음에는 빨래통이 비어있을 테니까 top에 None값을 주고

class Stack:
    def __init__(self): # 처음엔 빨래통이 비어있으니까 None
        self.top = None

 

push : 빨래통(Stack)에 빨래 넣기 (우리가 빨래통에 빨래를 넣을 떄 당연히 맨 위에 쌓이듯이 위치는 top)

    def push(self, new_빨래): # 빨래통에 새로 넣을 new_빨래
        self.top = 빨래감(new_빨래, self.top) # 맨 위를 새로 넣어줄 빨래로 업뎃

 

pop 빨래통에서 빨래 꺼내기

(빨래통에서 맨 위의 빨래감을 꺼내면 당연히 통에 있던 맨 위 빨래감은 없어지고, 그 아래에 놓여있던 빨래감이 맨 위에 놓인 빨래감이 된다. 이 당연한 개념을 생각하면서 이해하면 좀 쉽다.)

맨 위에 옷을 꺼낸 다음, 그 아래 옷을 다시 맨 위로 지정해줘야 다시 순서대로 착착 꺼낼 수 있기 때문에 self.top.next가 필요하다.

    def pop(self):# 꺼낼 때 
        if self.top is 빨래감: # 빨래통 비어있으면 
            return None # 없으니까 None 반환
        
        # 빨래통에 옷이 있으면
        빨래감 = self.top # 현재 빨래감 맨 위의 옷 확인
        self.top = self.top.next # 빨래감 맨 위의 옷 바로 아래있는 옷을 체크
        return 빨래감.item # 맨 위에 있었던 옷 꺼내

 

is_empty 빨래통 비었는지 확인

    def is_empty(self): # 빨래통이 비었는지를 보려면
        return self.top is None # 우리가 꺼내고 빼고 할 수 있는 곳은 top 한 곳이니 top이 None인지만 보면 된다

 

---

 

스택을 활용해서 유효한 괄호 문제를 풀어보면 된다.

Q: Given a string s containing just the characters '(',  ')' , '{',  '}',  '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example3:
Input: s = "(]"
Output: false

 

열린 괄호는 동일한 유형의 괄호, 올바른 순서로 닫아야 한다는 것. ( ) [ ] { } 얘네가 제대로 짝을 이루는지 확인하는 문제 .

내일 이어서 풀어보는 걸로.. 한 문제 푸는데 넘 오래 걸려서... 진도가 안나간다ㅠㅠ

 

근데.. 강의가 너무 나긋나긋해서일까... 수면유도 asmr 같다ㅠㅠㅠ 안그래도 어려운데 큰일이다ㅠㅠ