Queue(큐)

Queue란

• 큐는 먼저 삽입된 데이터가 먼저 추출되는 자료구조(data structure) 이다.
• 예시) 게임 대기 큐는 먼저 대기한 사람이 먼저 게임에 매칭된다.
  • 큐에 여러 개의 데이터를 삽입하고 삭제하는 예시를 확인해 보자.
  • 전체연산:삽입3–삽입5–삭제–삽입7–삭제–삽입8–삭제–삽입2–삽입9

연결 리스트로 큐 구현하기

• 큐를연결리스트로구현하면,삽입과삭제에있어서𝑂 1 을보장할수있다.
• 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다.
• 머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
• 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

큐 동작 속도: 배열 vs. 연결 리스트

• 다수의데이터를삽입및삭제할때에대하여,수행시간을측정할수있다.
• 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사용할 때 수행 시간 관점에서 효율적이다.
• JavaScript에서는 Dictionary 자료형을 이용하여 큐(queue)를 구현하면 간단하다.

JavaScript 큐(Queue) 구현하기

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
}
enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
dequeue() {
const item = this.items[this.headIndex]; delete this.items[this.headIndex]; this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex]; }
  getLength() {
    return this.tailIndex - this.headIndex;
} }

// 구현된 큐(Queue) 라이브러리 사용
queue = new Queue();
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) // - 삭제() - 삽입(1) - 삽입(4) - 삭제() queue.enqueue(5);
queue.enqueue(2);				// [실행 결과]
queue.enqueue(3);				// 3
queue.enqueue(7);				// 7
queue.dequeue();				// 1
queue.enqueue(1);				// 4
queue.enqueue(4);
queue.dequeue();
// 먼저 들어온 순서대로 출력
while (queue.getLength() != 0) {
  console.log(queue.dequeue());
}

큐(Queue)의 주요 동작들

• enQueue() : 큐에 데이터를 넣는다.
• deQueue() : 큐에서 데이터를 빼낸다.
• isEmpty() : 큐가 비어있는지 확인한다.
• isFull() : 큐가 꽉 차 있는지 확인한다.
• peek() : 앞에있는 원소를 삭제하지 않고 반환한다.

큐(Queue)의 문제점

큐(Queue)를 구현하고 사용할때 큐에서 데이터를 빼내는 deQueue()함수를 쓰게되면 맨 앞에있던 값이 빠져나가게 되는데 이때 front가 한칸씩 뒤로 밀려나게 되면서 큐의 가용범위가 줄어들면서, 큐의 재사용 또한 불가능하게 됩니다.
만약에, 억지로 큐의 재사용을 하기위해서 front를 출력하고 front뒤의 인덱스를 하나씩 앞당긴다고 하더라도 불필요한 연산이 너무 많아집니다.

큐(Queue)의 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
  -처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
  - 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
  - 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	queue<int> q;		// 정수형 데이터 값이 당기기
    q.push(7);			// 값으로 7을 넣고
    q.push(5);
    q.push(4);			
    q.pop();			// 남아있는 값 중에 가장 먼저들어온 값 뻬내기
    q.push(6);			
    q.pop();
    while (!q.empty()) {			// 남아있는 데이터 하나씨 출력할 수 있도록 하기
    	cout << q.front() << ' ';		// 현재 큐에 가장 앞에 있는 값 출력
        q.pop();  		// q 에 데이터를 빼놓기
        
     }
     return 0;			// 4 6 출력
 }