PostsSeriesLabsAlgo

자료구조

큐와 덱

줄을 서면 앞사람부터

급식 줄에 8명이 서 있습니다. 오는 일을 하나씩 처리하세요. 새 손님은 줄 맨 뒤에 섭니다

먼저 맞혀 보세요. 선생님이 오지 않는다면 이 줄에서 5번 손님은 몇 번째로 받을까요?

받은 순서아직 없음

누른 횟수 0
  • 먼저 들어온 게 먼저 나가는 줄 = 큐(queue)
  • 앞에도 뒤에도 서고, 앞에서도 뒤에서도 나갈 수 있는 줄 = 덱(deque)

파이썬에서는 둘 다 deque 하나로 만듭니다.

줄은 양 끝에서만 바뀐다

  • 서는 곳 — 맨 뒤. 새 손님은 앞사람을 밀어내지 못한다
  • 받는 곳 — 맨 앞. 그래서 먼저 선 사람이 먼저 받는다
  • 선생님과 종 — 앞에 서기와 뒤에서 나가기는 처음 두 버튼에 없었다. 양쪽 끝을 모두 쓰면 덱
  • 가운데 — 아무도 건드리지 않는다. 일은 늘 양쪽 끝에서만 생긴다

코드는 양 끝에서 넣고 빼는 두 줄이 전부다

다음을 눌러 한 줄씩 넘기며 맨 뒤에 서고 맨 앞에서 나가는 걸 보세요. 위 ① 의 앞 여섯 가지 일과 같습니다.

받은 순서아직 없음

리스트 pop(0) 이었다면 당긴 칸 0deque 는 0

다음을 눌러 한 줄씩 넘겨 보세요

len(q) = 8

serve_line.py
  1. 1from collections import deque
  2. 2def serve_line(line, events):
  3. 3 q = deque(line)
  4. 4 served = []
  5. 5 for e in events:
  6. 6 if e == 0:
  7. 7 served.append(q.popleft())
  8. 8 else:
  9. 9 q.append(e)
  10. 10 return served
0 / 22
  • q.popleft() — 맨 앞 사람이 나간다. 남은 사람은 움직이지 않는다
  • q.append(e) — 맨 뒤에 선다
  • deque(line) — 줄 서 있던 리스트를 deque 로 바꾼다. 파일 맨 위에 from collections import deque

같은 줄을 리스트로 만들고 pop(0) 으로 받으면 어떻게 될까요? 맨 앞이 비면 남은 사람을 한 칸씩 당겨야 합니다. 플레이어 아래의 당긴 칸 숫자가 그만큼입니다.

리스트 pop(0) · 100,000명4,999,950,000칸
deque popleft · 100,000명0칸
10만 명을 모두 받을 때 옮기는 칸 수. 이 컴퓨터에서 직접 재 보니 리스트 약 0.6초, deque 약 0.003초였습니다.

1번부터 8번까지 선 줄에서 [받기, 9번 도착, 받기, 받기, 10번 도착, 받기] 를 하면 받는 순서는?

한 줄이어도 느리거나 터지는 자리가 있다

  • list.pop(0) — 맨 앞을 빼면 나머지를 한 칸씩 당긴다. 10만 개를 모두 빼 보니 리스트 약 0.6초, popleft() 약 0.003초
  • q[i] 로 가운데 읽기 — deque 는 양쪽 끝만 빠르다. 10만 개의 가운데 칸을 2천 번 읽어 보니 리스트 약 0.0001초, deque 약 0.0075초
  • 빈 줄에서 받기 — IndexError: pop from an empty deque 가 난다. if q: 로 먼저 확인한다
  • deque(maxlen=3) — 가득 찬 줄에 넣으면 반대쪽 사람이 사라진다. deque([1, 2, 3], maxlen=3) 에 append(4) 하면 deque([2, 3, 4])

문제에서 이 말이 보이면

먼저 온 순서BFS양쪽 끝에서 넣고 뺀다

격자 BFS 도 이 줄로 돕니다. 가까운 칸부터 차례로 꺼내야 하니 먼저 넣은 칸이 먼저 나옵니다.

다음 장에서는 사물함을 번호 대신 이름으로 찾는 해시를 봅니다.