[자료구조] 큐(Queue)

 

• FIFO(First In First Out), LILO(Last In Last Out) 즉 선입선출의 규칙를 가지고 있는 자료구조이다. FILO(First In Last Out) 의 규칙을 가지고 있는 스택(Stack) 과는 반대의 성격을 가지고 있다. 
• 데이터의 삽입, 삭제가 빨라서 데이터의 입출력이 자주 일어나는 경우 사용한다.
• 프린터 작업 처리 , CPU task scheduling, BFS, Cache

 

용어

• Front (Head) : 논리적으로 가장 앞에 있는 데이터의 위치, 데이터를 Dequeue 할 수 있는 위치이다.
• Rear (Tail) : 논리적으로 마지막에 있는 데이터의 위치, 데이터를 Enqueue 할 수 있는 위치이다.
• Enqueue : Queue에 데이터를 삽입. Rear에 데이터를 넣고 Rear의 위치를 한 칸 뒤로 물려준다. O(1)
• Dequeue : Queue에서 데이터를 가져옴. Front의 데이터를 가져오고 Front의 위치를 한 칸 뒤로 물려준다. O(1)

 

형태

Queue는 구현 방식에 따라 여러가지 장 단점을 가지게 된다.

 

ArrayQueue

• ArrayList로 만들어진 Queue이다. 
• Enqueue, Dequeue가 반복되면서 Front와 Rear의 값이 커지기만 하기 때문에 Front 앞에 위치한 빈 data의 크기만큼 메모리 낭비가 발생한다. 

 

CircularQueue

https://prepinsta.com/data-structures-algorithms/circular-queue/

• 기본적으로 ArrayList의 형태를 가지고 있다.
• ArrayList에서 메모리 낭비 문제를 해결하기 위한 구현방법이다. 
• Rear값이 Capacity값에 도달할 경우 Rear값이 0으로 갱신되어 Enqueue시 Front앞의 낭비되던 memory를 사용할 수 있다.
• Array base의 자료구조이기 때문에 size가 capacity에 도달시 resize가 발생한다.

 

LinkedQueue

• LinkedList와 비슷한 구조를 가지고 있다.
• 값을 Enqueue 할 때마다 새 노드를 생성하여 기존 Rear node에 link 시킨다. 
• 크기를 미리 지정하지 않아도 돼서 resize가 일어나지 않는다 (메모리 낭비가 일어나지 않는다.)
• 하지만 새 노드를 추가할 때마다 할당이 일어나기 때문에 resize가 일어나지 않는다고 가정하면 ArrayQueue에 비해 Enqueue가 느리다.

 

Reference

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

https://devlog-wjdrbs96.tistory.com/246

https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

http://olliesworkshops.blogspot.com/2015/11/array-queue.html