Queue(큐)
가장 처음으로 삽입된 원소가 가장 먼저 제거되는 FIFO(First In, First Out) 형태의 자료구조
한 쪽에서는 삽입만 이루어지고 다른 한 쪽에서는 삭제만 이루어지는 선형구조
큐의 종류에는 일반적인 큐 외에도 덱과 우선순위 큐 등이 있음
Deque: Double Ended Queue(덱)
- 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐
- 큐와 스택을 합친 형태
Priority Queue(우선순위 큐)
- 들어가는 순서에 관계없이 큐에서 dequeue 될 때, 우선순위가 높은 데이터가 먼저 처리됨
- Array와 Linked List로 구현하면 성능이 저하되므로 주로 Heap을 이용하여 구현
Queue의 연산
enqueue/push(item)
- item 하나를 큐의 맨 뒷 부분에 추가
- 큐가 가득 찼을 때 enqueue 되면 큐 오버플로우가 일어남
dequeue/pop()
- 큐의 맨 앞 부분에 있는 item을 제거
- 큐가 비어있을 때 dequeue 되면 큐 언더플로우가 일어남
front()
- 큐의 맨 앞 부분의 item을 반환
rear()
- 큐의 맨 뒷 부분의 item을 반환
isEmpty()
- 큐가 비어있다면 True를 반환하고 비어있지 않다면 False를 반환
size()
- 큐의 size를 반환
시간복잡도
Search(검색)
- 특정 데이터를 찾을 때는 순차적으로 접근하여 찾으므로 시간복잡도 O(n)
Insert(삽입)
- 큐는 맨 뒤에 데이터를 삽입하므로 시간복잡도 O(1)
deletion(삭제)
- 큐는 맨 앞의 데이터를 삭제하므로 시간복잡도 O(1)
구현
큐의 종류에는 선형 큐, 원형 큐, 링크드 큐가 있음
Array
Linear Queue(선형 큐)
- 기본적인 큐의 형태
- 막대 모양으로 된 큐로, 크기가 제한되어 있음
- front와 rear이 고정되지 않고 움직인다면 배열의 끝에 도달할 때 배열에 남은 공간이 있어도 접근이 불가하므로 활용할 수 없음
- front를 한쪽에 고정한다면 데이터가 추가/삭제될 때마다 데이터들을 이동시켜야므로 비효율적
Circular Queue(원형 큐)
- 선형 큐의 문제점을 보완하고자 나옴
- 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 '(index+1)%배열의 사이즈'를 이용하여 인덱스 0으로 순환되는 구조를 가짐
- 크기가 제한되어 있고 구현이 복잡함
Linked List
Linked Queue(링크드 큐)
- 큐의 크기를 쉽게 늘릴 수 잇어 오버플로우가 발생하지 않음
- 원형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리함
참조
https://ko.wikipedia.org/
https://velog.io/@misun9283/Queue
