CSdataStructure

Queue

, , ,

Queue란?


위 파이프 사진처럼 Queue는 순서대로 들어오고 순서대로 나간다고 생각하면 됩니다.

Queue (DFS, 너비탐색)

  • Queue는 FIFO (First Input First Out) 구조를 갖습니다.
  • 들어오는 순서대로 인덱스를 지정해서 순서대로 실행 할 수 있도록 만들어진 구조입니다.
  • 일반적으로 javascript는 Stack의 구조를 갖는데 먼저 들어온 데이터를 우선적으로 처리할 때 사용합니다.

큐의 추상적 데이터형 (ADT , abstract data type)

  • enqueue : push를 이용하여 데이터를 넣음
  • dequeue : shift를 이용하여 데이터를 꺼냄.(처음 데이터)
  • front : 데이터의 가장 처음 값을 확인만 함.
  • isEmpty : 데이터가 비어있는지 확인.
  • clear : 데이터 초기화 (빈 배열을 할당하여 초기화)
  • print : 남아있는 배열의 데이터를 문자열로 출력.

Queue을 javascript로 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const queue = () => {
  let items = [];
  this.enqueue = (element) => {
    return items.push(element);
  };
  this.dequeue = () => {
    return items.shift();
  };
  this.front = () => {
    return items[0];
  };
  this.isEmpty = () => {
    return items.length === 0;
  };
  this.clear = () => {
    items = [];
  };
  this.size = () => {
    return items.length;
  };
  this.print = () => {
    console.log(items.toString());
  };
}

Queue를 이용하여 데이터 입출력 구현 (본인: javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const Queue= () => {
  let inbox = [];
  let outbox = [];
  this.enqueue = (elem) => {
    if (outbox.length>0){
      inbox = outbox.reverse();
    }
    return inbox.push(elem)
  }
  this.dequeue = () => {
    while(inbox.length>0){
      outbox.push(inbox.pop());
    }
    return ''+inbox.pop();
  }
}

Queue를 이용하여 우선순위를 비교 우선순위가 높은 것을 Queue로 구현 (강사님: javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const PriorityQueue = () => {
  let items = [];
  const QueueElement = (element, priority) => {
    this.element = element;
    this.priority = priority;
  }
  this.enqueue = (element, priority) => {
    const queueElement = new QueueElement(element, priority);
    if(!items.length) {
      items.push(queueElement);
    } else {
      let added = false;
      for(let i = 0; i<items.length; i++){
        if(queueElement.priority < items[i].priority) {
          items.splice(i,0,queueElement);
          added = true;
          break;
        }
      }
      if(!added){
        items.push(queueElement);
      }
    }
  }
  this.dequeue = () => {
    return items.shift;
  }
  this.front = () => {
    return items[0];
  }
  this.size = () => {
    return items.length;
  }
  this.clear = () => {
    items = [];
  }
  this.print = () => {
    console.log(''+items);
  }
}

배운점

  • Queue가 어떻게 구현되는지 배웠습니다.
  • 데이터를 가공 할 때 우선순위를 매겨 우선 실행히 되어야 할 data를 우선실행되도록 하는 방법도 배웠습니다.
공유하기