What is Queue?
큐는 동종의 아이템들(자료형이 같은 것들)만의 그룹이고 새로운 아이템은 큐의 맨끝에 추가되고, 제거 되는 아이템은 맨 앞에서 사라진다.
이러한 특성을 FIFO(First in First Out)이라 부른다. ex). Job buffers, Network buffers
Queue
-
Logical level
-
Constructor
- Class Name
-
Transformer
-
enqueue(value)
-
dequeue( )
-
clear
-
-
Observer
-
isFull( )
-
isEmpty( )
-
-
Queue의 동작설명
-
Enqueue( )
-
Queue의 맨 끝인 rear에 추가하고자 하는 아이템의 값을 추가한다.
-
시간복잡도 : O(1)
-
-
Dequeue( )
-
Option 1 (front의 값을 제거 후 모두 앞으로 당기기)
-
front의 값을 제거한다.
-
이후 기존의 값들의 위치를 한 칸씩 앞으로 당겨 재정렬한다.
-
시간복잡도 : O(N)
-
-
Option 2 (배열을 옮기는 것이 아닌 front가 앞으로 움직인다.)
-
front의 값을 제거한다.
-
그 후 front가 가리키는 값을 기존의 front에서 한 칸 뒤로 옮긴다.
-
시간복잡도 : O(1)
-
순환하는 Queue 구조가 된다.
-
과연 Option 2는 문제가 없는 방식인가?
-
rear와
-
-
-
Circular Queue에서의 동작 구조 설명
큐는 배열로 구현된 선형의 형태를 가진다. 이에 따라, 데이터 삽입/삭제 시 데이터들을 앞 혹은 뒤로 당겨주는 과정이 필요하며, 이는 불필요한 시간 낭비를 불러일으킨다.
이러한 단점을 극복하기 위해 고안된 개념이 'Circular Queue'이다.
-
enqueue( )
-
큐가 가득 차있지 않다면, 아이템을 삽입한다. rear의 위치를 한 칸 옮겨주고, 본래 rear 자리에 아이템을 넣어준다.
-
rear = rear + 1
-
-
dequeue( )
- 큐가 비어있지 않다면, front를 한칸 옮긴다. 동시에 front에 저장되어 있던 아이템을 반환해준다.
-
front = front + 1
-
isFull( )
-
front의 값이 rear에서 1개 더한 값과 같다면 Full인 상태라고 판단한다.
-
front == rear + 1
-
-
isEmpty( )
-
front의 값이 rear에서 1개 더한 값과 같다면 Empty인 상태라고 판단한다.
-
front == rear + 1
-
-
그렇다면 isFull( )인지 isEmpty( )인지 어떻게 구분할 것인가?
-
해결책 : Reserved Space
-
실제론 데이터를 보관하지 않는 공간을 만든다.
-
front는 항상 reserved space를 가리키도록한다.
-
Queue가 isFull일 경우 rear+1 == front이다.
-
즉, (rear+1) % maxQueue == front이다.
-
Queue가 isEmpty일 경우 rear == front이다
-
한 메모리 공간을 낭비하더라도, Full과 Empty를 구분할 수 있다.
-
reserved space 공간은 Queue크기가 커질 수록 공간에 대한 부담이 줄어든다.
-
-
Big - O 시간복잡도 (Queue)
| Operation | Time Complexitiy |
|---|---|
| size( ) | O( 1 ) |
| isFull( ) / isEmpty( ) | O( 1 ) |
| enqueue(ItemType value) | O( 1 ) |
| dequeue( ) | O( 1 ) |
