Queue

FIFO : First in First out 들어온 순서대로 나간다.

stack에서의 push를 여기서는 enqueue라고 한다.
stack에서의 pop은 dequeue라고 한다.

ex)
[]

enqueue(5)
[5]

enqueue(-2)
[5, -2]

dequeue() # 5
[-2]

enqueue(10)
[-2, 10]

dequeue() # -2
[10]

front에서 dequeue()가 된다.

저장공간은 items라고 부르며, list이다.

class Queue:
	def __init__(self):
    	self.items = []
        self.front_index = 0
     
    def enqueue(self, val):
    	self.items.append(val)
        
    def dequeue(self):
    	if self.front_index == len(self.items):
        	print('Q is empty')
        else:
        	x = self.items[front_index]
            self.front_index += 1
        	return x

Queue 활용 예제

Josephus 문제

n은 사람 수, k는 번째로 위의 예시에서는 6명의 사람이 두 번째 사람마다 죽는다.
1에서 시작하면 2 죽고, 4 죽고, 6 죽고, 3 죽고, 1 죽고
최종 승자는 5

<방법론>
n=9 / k=3

1) 우선 1부터 n까지 enqueue() [1,2,3,4,5,6,7,8,9]
2) k-1번째 dequeue(), 맨 앞의 1, 2 순서대로 맨 뒤로 옮기기 enqueue
즉 1 dequeue, enqueue, 2 dequeue, enqueue, 3 dequeue
[4,5,6,7,8,9,1,2]
3) 반복
[7,8,9,1,2,4,5][1,2,4,5,7,8]
... 최종 하나만 남을 때 까지

dequeue

큐의 dequeue가 아니라, stack + queue 를 합친 것을 dequeue라고 한다.

이는 마음대로 양쪽 끝으로 들어가고 나갈 수 있다.

dequeue 예시

• 슬라이딩 윈도우를 이용하여 배열에서 최대값을 찾는 예제

from collections import deque

def max_in_sliding_window(nums, k):
    result = []
    window = deque()

    for i, num in enumerate(nums):
        # 윈도우의 크기를 유지
        while window and window[0] < i - k + 1:
            window.popleft()

        # 현재 원소보다 작은 값들을 윈도우에서 제거
        while window and nums[window[-1]] < num:
            window.pop()

        window.append(i)

        # 최대값을 결과에 추가
        if i >= k - 1:
            result.append(nums[window[0]])

    return result

# 예시
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_in_sliding_window(nums, k))

https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11