큐(Queue)

큐(Queue) : Queue is like waiting line

 

Queue의 예시

rear : Insertion 하는 곳

front : Deletion 하는 곳

FIFO(First-In First-Out)

먼저 들어온 데이터가 먼저 나가는 구조

ex) 입력 순서대로 데이터 처리가 필요한 경우 사용 : 프린터 출력 대기열, BFS(Breath-First Search), 식당 웨이팅 등

 

Queue의 구조

Queue의 기본 구조 예시

 

- Enqueue : Queue에 데이터 추가

- Dequeue : Queue에 데이터 제거

(Queue) Front : retrieve the element at the front

(Queue) Rear : retrieve the element at the rear

 

Queue Operation

- Enqueue : Queue에 데이터 추가

- Dequeue : Queue에 데이터 제거

(Queue) Front : retrieve the element at the front

(Queue) Rear : retrieve the element at the rear

 

Enqueue

Queue에 데이터 추가

After Insertion, new element이 Rear가 됩니다.

Stack의 Insertion(Push)와 유사합니다. 마찬가지로 남은 공간을 확보하여야 합니다.

Enqueue 예시

 

Dequeue

Queue에 데이터 제거

Queue가 비어 있는지 여부 확인 해야합니다.

Dequeue 예시

 

Front

내용이 변경되지 않고, front에 있는 값을 반환합니다.

이 과정에서, Queue가 비어있는지 확인해야합니다.

Front 예시

 

Rear

Front와 마찬가지고 Rear에 있는 데이터를 반환합니다.

Rear 예시

 

Example

Queue Operation Example

 

 

 

 

 

Queue 메소드

poll() : 큐의 가장 앞에 있는 요소를 제거하고 반환합니다. 큐가 비어있다면 null을 반환합니다. 

peek() : 큐의 가장 앞에 있는 요소를 반환하지만 제거하지는 않습니다. 큐가 비어있다면 null을 반환합니다. 

contains(Object o) : 큐에 특정 요소(o)가 포함되어 있는지 여부를 반환합니다. 

size() : 큐의 현재 크기(요소의 개수)를 반환합니다. 

isEmpty() : 큐가 비어있는지 여부를 반환합니다. 

clear() : 메소드는 Queue에 있는 모든 요소를 제거하여 Queue를 비웁니다.

add(item) : 큐에 요소(item)를 추가합니다.

           성공 -> True 반환

           실패 -> 큐가 이미 가득차 있는 경우 -> IllegalStateException 에러 발생)

offer(item) : 큐에 요소(item)를 추가합니다.

           성공 -> True 반환

           실패 -> False 반환

remove() : 큐의 가장 앞에 있는 요소를 제거하고 반환합니다. 큐가 비어있다면 예외를 발생시킵니다. 

element() : 큐의 가장 앞에 있는 요소를 반환하지만 제거하지는 않습니다. 큐가 비어있다면 예외를 발생시킵니다. 

remove(Object o): 큐에서 특정 요소(o)를 제거합니다. clear(): 큐의 모든 요소를 제거합니다.

 

 

시간 복잡도(Time Complexity)

삽입(Insertion) = O(1)

삭제(Deletion) = O(1)

검색(Search) = O(n)

 

 

 

 

 

 

Reference

- Chapter 4. Queues, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.