[ch09]스택,큐

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ]

---

* 괄호 문제

- 열린 괄호면 stack 에 넣기 

- 닫힌 괄호 만나면 해당 괄호의 열린 괄호가 stack 에 있는지 확인

- 마지막에 stack 에 열린 괄호가 있다면 짝이 맞지 않는 것

stack = []
table = {   ')':'(',
            ']':'['.
            '}':'{', }
            
for char in s:
	if char not in table:
		stack.append(char)
	elif not stack or table[char] != stack.pop():
		return False
        
return len(stack) == 0

---

* 빗물 트래킹 / 온도 / 주식 등등

- 더 낮은 or 더 높은 값 나올때까지 각 요소들은 얼마나 기다리거나 걸리는지 

-> stack 으로 풀기

: stack 에 값 넣어놓고, 더 낮은 or 더 높은 값 나오면 스택에 쌓아둔 값이랑 비교

: while stack 동안 비교 ( stack 에서 꺼내야 할 값이 여러 개 일 수 있으니까 )

 

+ 해당 인덱스에 매핑되는 값 변경하기

res = [0] * len(temperatures)
# 길이만큼 0값으로 초기화 후 인덱스로 값 변경

---

* 원형 큐 

- Enqueue : rear 가 가리키는 곳에 value 저장, rear 증가 

-> 증가 시에 전체 길이로 나눈 나머지 

 def enQueue(self, value: int) -> bool:
        if self.queue[self.rear] is None:
            self.queue[self.rear] = value
            self.rear = (self.rear + 1 ) % len(self.queue)
            return True
        else:
            return False

- Dequeue : front 가 가리키는 곳에 value 삭제, front 증가

def deQueue(self) -> bool:
        
        if self.queue[self.front] is not None: # 값이 있으면
            self.queue[self.front] = None
            self.front = (self.front+1) % len(self.queue)
            return True
        else:
            return False