배열로 큐를 구현할 수 있지 않을까?!

algorithm 스터디 주제였던 Queue에 대해서 발표를 마친 뒤,
팀원으로 부터 '배열과 큐의 차이점'에 대한 질문을 받았다.

이때까지만 해도 list는 저장방식인 것이고, queue는 처리방식이니까
queue가 list에 포함되는 개념이 아닐까 라는 생각을 했었다.

그렇다면 list로도 queue를 구현할 수 있지 않을까? 라는 의문이 들어 실험해 보았다.
우선 각각의 정의에 대해서 알아보자.

list와 queue

구분	정의	특성	목적
list	연속된 메모리에 데이터를 나열해서 저장하는 '자료구조'	저장 방식	빠른 조회
queue	먼저 들어온 것이 먼저 나가는 FIFO 규칙	처리 방식	순차적 처리

list로 queue를 구현할 수 있을까?

arr = []

arr.append(1)
arr.append(2)
arr.append(3)
print(arr) # [1, 2, 3]

print(arr.pop(0)) # 1
print(arr.pop(0)) # 2
print(arr.pop(0)) # 3

위와 같이 들어온 순서대로 빼내는 형태는 구현 가능하지만,
내부적으로는 아래와 같이 처리된다.

print(arr.pop(0)) # 1 
# 첫번째 pop으로 1을 뽑아냈을 때 2가 1이 있던 자리인 인덱스 0으로 이동

print(arr.pop(0)) # 2
# 두번째 pop으로 2을 뽑아낼 때 3이 인덱스 0으로 이동

만약 데이터가 10만, 100만, … 이라면?
아래와 같이 하나의 데이터를 pop 하여 추출할 때마다 자리를 이동해야하기 때문에 시간 초과될 것이다.

1. pop(0) 실행

[1][2][3][4]
 ↑
pop(0)

2. 메모리 이동

[2][3][4][ ]
 ↑  ↑  ↑
 값들이 전부 왼쪽으로 shift

그러면 queue는 어떤 방식으로 값을 처리할까?

deque로 구현한 큐는 popleft()로 요소를 빼내고 나면,
메모리 값은 '그대로 유지'된 채, head 인덱스만 이동한다.

1. 초기 상태

[ _ _ 1 2 3 4 _ _ ]
      ↑
      head

2. popleft() 실행

[ _ _ 1 2 3 4 _ _ ]
        ↑
        head