Queue

Queue

시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조

enqueue

데이터를 추가하는 것, queue의 맨 뒤 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)

dequeue

데이터를 추출하는 것, queue의 맨 앞 데이터를 삭제하면 완료되기 때문에 시간복잡도는 O(1)

구현 방식

Array-Based

enqueue와 dequeue 과정에서 남는 메모리가 생김, 메모리의 낭비를 줄이기 위해 주로 Circular queue 형식으로 구현

List-Based

재할당이나 메모리 낭비의 걱정을 할 필요가 없음

확장 & 활용

deque(double-ended queue)

양쪽에서 enqueue와 duque가 가능

priority queue

시간 순서가 아닌 우선순위가 높은 순서로 dequeue

Heap

우선순위큐의 구현과 일치하며 완전이진트리 구조

• 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다(min heap)
  -> root node에 저장된 값이 가장 작은 값이 된다.
  
  

Heap 구현

array를 기반으로 구현
-> 새로운 node를 힙의 '마지막 위치'에 추가해야 하는데, 이 때 array기반으로 구현해야 이 과정이 수월

• 구현의 편의를 위해 0번 째 index는 사용 x
• 완전이진트리의 특성을 활용하여 array의 index만으로 부모 자식간의 관계 정의
  - n번 째 node의 left child node = 2n
  - n번 째 node의 right child node = 2n + 1
  - n번 째 node의 parent node = n / 2
  

Heap 시간복잡도

• heap tree의 높이는 logN
• push : O(logn)
• pop : O(logn)

활용 예시

하나의 자원을 공유하는 프린터, CPU task scheduling, Cache 구현, 너비우선탐색(BFS) 등

Queue 두 개를 이용하여 Stack 구현

push() queue - q1
pop() queue - q2

1. push() : q1으로 enqueue()를 하여 데이터 저장
2. pop()
   • q1에 저장된 데이터의 개수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue(). 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 이동
   • q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환(LIFO)
   • 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap
3. 시간복잡도
   • push() : O(1)
   • pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q3로 옮겨야 하므로 O(n)