[자료구조] 큐 (Queue)

📚 큐 (Queue)

큐(Queue)는 한쪽 끝에서는 삽입 연산만 이뤄지고, 다른 쪽 끝에서는 삭제 연산만 이뤄지는 선형 자료구조이다.

• First In First Out; FIFO 먼저 들어온 데이터가 먼저 나가는 구조

Enqueue, Dequeue

• Enqueue는 데이터 삽입 : Rear에서 발생
• Dequeue는 데이터 삭제 : Front에서 발생

 

Front, Rear

• Front는 삭제 연산이 이뤄지는 index
• Rear은 삽입 연산이 이뤄지는 index

크기가 정해진 원형 큐 구현에 Front, Rear을 갱신해주면 쉽게 데이터를 관리할 수 있다.

---

🦋 큐의 사용사례

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현
• 프린터의 출력 처리
• 프로세스 관리
• 콜센터 고객 대기시간

---

✍🏻 큐 ADT (추상 데이터 타입)

create()	큐 생성
enQueue(data)	Rear에 데이터 삽입
deQueue()	Front에서 데이터 삭제하면서 값 return
peek()	큐에서 데이터 삭제하지 않고 Front 값 return
contains(data)	큐에 data가 포함되어 있는지 확인 true, false
isEmpty()	큐가 비어있는지 확인 (front == rear)
isFull()	큐가 가득 차있는지 확인 (front == (rear + 1))
size()	큐의 크기 반환 int return
clear()	큐의 데이터 초기화
print()	큐의 데이터 출력

---

⚙️ 큐 기능 & 동작원리

생성

1. front, rear 변수 선언
2. 큐의 크기는 원하는 크기보다 1만큼 더 할당
3. 2번과 같이 하는 이유는 초기 front, rear을 같은 위치에 잡아주기 위함

// 슈도 코드

T[] Queue; // Queue Array 생성
int front = 0;
int rear = 0; // 초기 front, rear는 같게 설정

public void createQueue(int size) {
	T[] Queue = new T[size + 1]; // size + 1을 한 후에 배열 생성
}

 

삽입

1. 큐가 가득 차있는지 확인 isFull() -> front와 rear이 같은 값인지 확인
2. 가득 차있다면 isFull() true 반환 후 종료
3. 가득 차있지 않다면 rear을 하나 증가
4. rear에 데이터 삽입(enQueue)

// 슈도 코드

public void enQueue(T item) {
	if (isFull()) {
    	return error;
    }
    
    rear = (rear + 1) % Queue.length;
    /*
     * rear + 1 을 했을 때 처음 정해준 배열의 크기를 넘을 수도 있다.
     * 그렇게 되면 에러가 나기 때문에 front != rear 이 아니라면
     * % Queue.length를 해서 다시 0부터 시작할 수 있게 한다.
     */
    Queue[rear] = item;
}

 

삭제

1. 큐가 비어있는지 확인 isEmpty()
2. 비어있다면 isEmpty() true 반환 후 종료
3. 비어있지 않다면 front 하나 증가
4. 증가한 front의 데이터 반환 (deQueue)

// 슈도 코드

public T deQueue() {
	if (isEmpty()) {
    	return error;
    }
    
    front = (front + 1) % Queue.length;
    /*
     * enQueue의 rear과 마찬가지로 %연산으로 순환 큐 관리
     */
     return Queue[front];
}

 

🤔 코드에 대한 의문

반환하려는 값을 다른 변수에 미리 저장해놓고 그 값을 반환해야 하는 것이 아닌가?

처음 큐를 만들 때 front, rear에는 데이터가 들어있지 않다고 가정하고 값이 하나라도 들어왔을 때 rear을 증가시켰다.

초기 front에는 아무값도 들어 있지 않으니 deQueue하려는 값은 현재 front위치가 아니라 그 다음 위치의 값이다.

 

그렇기 때문에 front + 1 위치에 있는 값을 반환하는 것.

 

다음 deQueue 동작을 하게되면 또다시 front + 1을 할것이기 때문에 현재 front의 값을 따로 지워줄 필요는 없다.

---

⏱️ 큐의 시간복잡도

• 삽입(Insertion) O(1)
• 삭제(Deletion) O(1)
• 검색(Search) O(n)

삽입(Enqueue)은 Front에서 이뤄지고 삭제(Dequeue)는 Rear에서 이뤄지기 때문에 한번씩만 수행하면 된다. O(1)

검색은 원하는 값을 찾을 때 까지 계속 수행해야되기 때문에 최대 O(n)의 시간복잡도를 갖는다.