[자료구조/알고리즘]Queue

자료구조 Queue에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다.

코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다.

Achievement Goals

• Queue 자료구조에 대해 이해한다
  • Queue 자료구조가 가진 특징을 학습한다.
  • Queue 자료구조를 사용하기 적합한 상황을 이해한다
  • 다른 자료구조 와의 차이점을 이해하기 위해 자료 구조 내부를 직접 구현한다.
  • Queue 자료구조를 배열로 대체해볼 수 있다.

1. Queue

Queue 란

• Queue도 Stack과 비슷하게 데이터를 순서대로 쌓는 자료구조이다.
• Stack과는 다르게, 먼저 들어온 건이 먼저 나오는 구조이다.
  • 선입선출 , Firts-In-First-Out (FIFO) OR Last-In-Last-Out(LILO) 구조의 자료구조이다.
  • 데이터가 입력된 순서대로 처리될 때 주로 사용된다.

Queue의 실사용

1. 프린터에서 여러 문서를 출력할 때
   • 출력할 문서가 임시 기억장치(Queue)에 저장된다.
   • 프린터는 Queue에 들어온 순서대로 출력을 진행한다.
2. 버퍼 (Buffer)
   • 일정한 처리 속도를 갖는 CPU와 달리 대부분의 컴퓨터 장치는 이벤트가 불규칙적으로 발생한다.
   • 규칙적으로 처리하기 위해 Buffer를 사용한다.
   
   
   이 사이트에서 가져온 그림

즉, 컴퓨터와 프린터 사이의 데이터 통신은 아래와 같다.

• cpu는 프린터보다 데이터를 처리하는 속도가 빠르다.
• cup는 빠른 속도로 데이터를 만들고 Queue에 저장 후 다른 작업을 처리한다
• 프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄한다.

Queue의 시간 복잡도 (Big-O)

• 데이터 삽입 : 뒤에 데이터를 삽입하므로 시간 복잡도는 O(1)이다.
• 데이터 삭제 : 맨 앞의 자료를 삭제하므로 시잔 복잡도는 O(1)이다.
• 데이터 탐색 : 맨 앞의 요소부터 맨 마지막까지 검색을 해야 하므로 시간 복잡도는 O(n)이다.

Queue ADT의 정의

• Queue : 배열 또는 Object로 정의됨 queue 그 자체
• front : Queue의 맨 앞에 저장된 요소 확인
• reare : Queue의 맨 뒤에 저장된 요소 확인
• Queue를 대표하는 연산
  • equeue : Queue의 맨 뒤에 요소 추가
  • dequeue : Queue의 맨 앞에서 요소 삭제
  • toSrging : Queue의 의 모든 요소를 문자열로 반환
  • empty : Queue의 남은 요소가 있는지 확인

이 ADT를 기반으로 Queue를 구현해보자. 먼저 Class로 구현을 해보고 JS Array로 구현을 해본다.

Queue의 구현

• Class를 사용하여 Queue를 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }

  // Queue에 데이터를 추가할 수 있어야 한다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // 가장 먼서 추가된 데이터가 가장 먼저 추출되어야 한다.
  dequeue() {
    // 빈 큐에 연산을 적용해도 에러가 발생하지 않아야 한다.
    if (!this.size()) return;

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

const queue = new Queue();

queue.size(); // 0
for (let i = 1; i < 10; i++) {
  queue.enqueue(i);
}
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
console.log(queue.size()); // 7
console.log(queue.enqueue(10));
console.log(queue.size()); // 8
console.log(queue.dequeue()); // 3
console.log(queue.dequeue()); // 4
console.log(queue.size()); // 6

Array를 사용하여 Queue를 구현

/*-----------------------------------------------------------------*/
// 배열로 Queue를 구현한다.
/*- Queue : 배열 또는 Object로 정의됨 queue 그 자체
-  front : Queue의 맨 앞에 저장된 요소 확인
-  reare : Queue의 맨 뒤에 저장된 요소 확인
-  Queue를 대표하는 연산
    - equeue : Queue의 맨뒤에 요소 추가
    - dequeue :  Queue의 맨 앞에서 요소 삭제
    - toSrging : Queue의 의 모든 요소를 문자열로 반환
    - empty : Queue의 남은 요소가 있는지 확인 
*/


const queueArray = [];

for (let i = 0; i < 10; i++) queueArray.push(i);

console.log(queueArray);

queueArray.shift();
queueArray.shift();
queueArray.shift();

console.log(queueArray);