TIL(Today I Learn) - #3. Data Structure - Queue

Queue에 대해 알아보도록 하겠습니다.

Queue란 들어오고 나가는 방향이 양쪽 2개인 Data Structure를 말합니다.

들어왔던 방향 그대로 나가기 때문에 가장 먼저 들어온 데이터가 가장 먼저 나가게 됩니다.
이것을 FIFO(First In First Out)라고 합니다.

Queue의 실제 사용 예시

캐시(Cache) 구현
우선순위가 같은 작업 예약 (인쇄 대기열)
선입선출이 필요한 대기열 (티켓 카운터)
콜센터 고객 대기시간
프린터의 출력 처리
프로세서 처리

Queue Data structure의 methods

• enqueue(item)
• dequeue()
• front() //peek()
• isEmpty()
  

Queue Data structure의 property

• Array를 사용한 Queue
  front, rear, size, arrQueue
• Linked list를 사용한 Queue
  front, rear

Queue 이미지

배열로 구현한 큐의 단점은 크기를 미리 정해야 하고, 그 크기를 넘어서면 error가 발생한다는 것입니다. 반면 연결리스트로 구현하면 큐의 크기(size)를 미리 정할 필요가 없습니다.

Array를 사용한 Queue 구현

pseudo code

enqueue(item) 
- size를 1 증가 시킨다.
- rear를 1 증가 시킨다. 
- rear 위치에 값을 할당한다.

dequeue() 
- front 위치에 있는 값을 반환한다.
- front 위치에 있는 값을 삭제한다.
- 모든 요소의 index 값을 1 감소 시킨다.

front()
- 만약 비어있으면(index가 -1(초깃값)이라면), 찾지 못했다는 메세지를 반환한다.
- front 위치에 있는 값을 반환한다.

isEmpty()
- index가 -1이면 true, 아니면 false

Linked list를 사용한 Queue 구현

pseudo code

enqueue(item) 
- 새로운 node객체를 생성자를 이용하여 만든다.
- tail의 포인터가 새로운 node를 가리키도록 한다.
- tail에 새로운 node를 할당한다.

dequeue() 
- 만약 비어있으면, 아무것도 하지 않는다.
- 임시 변수에 head를 할당한다.
- head에 head가 가리키고 있던 node를 할당한다.
- 임시 변수를 삭제한다.

front()
- 만약 비어있으면, 찾지 못했다는 메세지를 반환한다.
- head node(front)의 데이터를 반환한다.

isEmpty()
- head가 null이면 true, 아니면 false