본 포스팅은 아래의 출처를 참고하여 정리한 것입니다.
https://www.youtube.com/watch?v=PIidtIBCjEg&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=1

Queue

• 선입선출, FIFO (First In First Out)
• 삽입: enqueue
• 삭제: dequeue
• 2개의 index 필요
  • enqueue 될 값이 어느 index에 위치하는지: append
  • dequeue 될 값이 어느 index에 위치하는지: front_index
• Queue의 items는 파이썬의 list로 생성 (enqueue: append)
• dequeue를 위해 dequeue가 될 index를 가리키는 front-index 변수 필요

class Queue:
	def __init__(self):
    	self.items = [] # 빈 리스트
        self.front_index = 0
        
    def enqueue(self, value):
    	self.items.append(value)
    
    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는 실제로 리스트 안의 값들을 다 지운 것이 아닌 그대로 남아있음!
• dequeue할 때마다 front_index를 하나씩 증가해주면서 위치만 바꾸어주는 것이지, 리스트 안의 값들을 실제로 삭제하는 것이 아님!

Queue 활용 예 - Josephus problem

• n = 6, k = 2: 6명의 사람이 있을 때 매 2번째 사람마다 죽음
• 최종적으로 살아남는 유일한 한 사람이 누구인지 구하는 문제
• 활용 원리
  • 생존자는 큐에 다시 dequeue 후에 다시 enqueue하고(나중에 다시 차례를 돌아야하므로), k번째 사람은 dequeue만 작동

---

Deque (Stack + Queue)

• 새로운 자료구조 Deque (덱)
• 양쪽 끝으로 삽입/삭제 모두 가능
• python에서는 deque class 제공

from collections import deque

deq = deque()

# 맨 왼쪽에 데이터를 삽입
deq.appendleft(9)

# 맨 오른쪽에 데이터를 삽입
deq.append(0)

# 맨 왼쪽 데이터를 반환 및 삭제
deq.popleft()

# 맨 오른쪽 데이터를 반환 및 삭제
deq.pop() 

데크 (deque)의 메서드

• append(item): item을 데크의 오른쪽 끝에 삽입.
• appendleft(item): item을 데크의 왼쪽 끝에 삽입.
• pop(): 데크의 오른쪽 끝 요소를 리턴하는 동시에 데크에서 삭제.
• popleft(): 데크의 왼쪽 끝 요소를 리턴하는 동시에 데크에서 삭제.
• extend(list): 배열(list)을 순환하면서 데크의 오른쪽에 추가.
• extendleft(list): 배열(list)을 순환하면서 데크의 왼쪽에 추가.
• remove(item): item을 데크에서 찾아 삭제.
• rotate(n): 데크를 n만큼 회전(양수면 오른쪽, 음수면 왼쪽)