Queue Data Structure

About Queue

 

Queue는 Stack 다음으로 가장 기초 적인 자료구조 중에 하나이다.

First In First Out: 먼저 들어온 데이터가 먼저 나간다.

queue 의 사전적인 의미를 찾아보면 (무엇을 기다리는 사람)줄 , 줄을 서서 기다리다.

로 해석된다.

큐는 주로 프로세스나 네트워크사이에서 자료를 주고 받을때 임시적으로 저장

하는 용도에 많이 사용된다.

ADT (Abstract Data Type)

methodname	contents
enqueue(s)	데이터 삽입
dequeue()	데이터를 꺼내고 꺼낸값을 리턴
front()	큐의 가장 앞에 있는 데이터 확인
isEmpty()	큐가 비어 있는지 확인
size()	큐의 크기

implementation

//큐
class Queue {
    constructor() {
        this.store = [];
    }

    enqueue(el) {
        this.store.push(el)
    }

    dequeue() {
        return this.store.shift();
    }

    front() {
        return this.store[0];
    }

    isEmpty() {
        return this.store.length === 0;
    }

    size() {
        return this.store.length;
    }
}

schematism queue

1. 원형 큐

   큐를 사용하다보면 배열의 앞부분 공간이 낭비되는데 이점을 활용하여서 데이터를

   내보내면 다시 앞부분부터 배열을 채워넣는 방식이다.

   그런데 자바스크립트는 배열의 길이가 정해져 있지 않다.

   의도적으로 배열의 길이를 선언 new Array(10) 해서 굳이 구현해야 할 필요성이

   있는지 의문이 들었다. 내가 생각하기에 자바스크립트의 최대장점은 유연함이기 때문에

   자바나 C++ 에 있는 엄격함을 자바스크립트에 끼워맞춰야 하나 라는 생각이 들었기

   때문이다. 원형을 떠올려보면 우로보로스가 생각난다. 이러한 꼬리물기 코드는

   enqueue(dequeue) 으로 간단하게 해결된다.

   let arr = [1, 2, 3, 4, 5];
      arr.push(arr.shift()); 
      console.log(arr) // [2, 3, 4, 5, 1];

   rear 와 완충지대를 구현한 전통적인 원형 큐는 시간이 있을때 따로 포스팅 할 계획이다.

2. 우선순위 큐

   큐는 선입선출 구조를 가지고 있는데 우선순위 큐는 선입 까지는 동일하나

   선출이 우선순위 에 따라 달라지는 구조를 가지고 있다.

   즉, 나갈땐 마음대로 나갈수 없다. 힙트리 (최소,최대) 에서 사용된다.

   책에서는 응급실 환자를 질병코드에 따라 우선순위를 부여하여 처리하는 방식에

   구현을 하고 있다.

3. 데크

   데크는 front 와 rear 즉 양방향 모두 입출력이 가능한 큐의 변형 형태 인데

   자바스크립트 배열에 있는 레퍼런스로 쉽게 표현 가능하다.

   front : unshift / shift
rear : push / pop