큐(Queue) : Queue is like waiting line
rear : Insertion 하는 곳
front : Deletion 하는 곳
FIFO(First-In First-Out)
먼저 들어온 데이터가 먼저 나가는 구조
ex) 입력 순서대로 데이터 처리가 필요한 경우 사용 : 프린터 출력 대기열, BFS(Breath-First Search), 식당 웨이팅 등
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)와 유사합니다. 마찬가지로 남은 공간을 확보하여야 합니다.
Dequeue
Queue에 데이터 제거
Queue가 비어 있는지 여부 확인 해야합니다.
Front
내용이 변경되지 않고, front에 있는 값을 반환합니다.
이 과정에서, Queue가 비어있는지 확인해야합니다.
Rear
Front와 마찬가지고 Rear에 있는 데이터를 반환합니다.
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.
'Computer Science > Data Structure' 카테고리의 다른 글
힙(Heap) (0) | 2023.04.18 |
---|---|
연결 리스트(Linked List) (0) | 2023.04.18 |
해시 테이블(Hash Table) (0) | 2023.04.14 |
배열(Array) (0) | 2023.04.14 |
스택(Stack) (0) | 2023.04.13 |