10강 자료구조 큐(Queue)

큐는 FIFO ( First In First Out) 규칙의 순차적 자료구조이다.

enqueue는 stack의 append에 해당하는 삽입으로 가장바깥에 들어간다.
dequeue는 stack의 pop에 해당하는 삭제로 가장 안쪽에 있는것을 없앤다.

stack은 말미잘, queue는 동물로 생각하면 편하다.
stack은 맨 위만 신경쓰면 됐는데 queue는 가장 안쪽과 바깥쪽, 두개의 인덱스를 알아야 한다.
front-index, rear

class Queue:
	def __init__(self): 생성자
    	self.items = [] # 빈 리스트
        self.front-index = 0
    def enqueue(self, value):
    	self.items.append(val)
    def dequeue(self):
    	if self.front-index == len(self.items):
        	print("Q is empty")
            return None
        else:
        	X = self.items[front-index]
            self.front-index += 1
            return X

dequeue에서 else:를 보면 실제로는 items[front-index]의 값을 제거하지 않고 front-index의 값을 하나 올려서 제거된거처럼 작동하게 한다.
그렇게 front-index가 증가하다가 len과 같아지면 모두 제거한 것이므로 Q is empty를 출력한다.

Josephus problem이 있는데, n명이 있을때 매 K번째 사람마다 제외시키는 것이다.
이것도 queue로 풀면 1,2는 dequeue, enqueue 하여 맨뒤에 다시 붙이고 3은 dequeue만 하여 값을 제거한다.
뒤 숫자도 계속 이런식으로 반복하면서 매 3번째 숫자는 새로 추가하지 않으면 정상적으로 작동한다.