[선형] 10. 큐

in 자료구조 on 선형




1. 큐 (Queue)

큐

  • 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료 구조
  • 데이터 전체 획득 / 비어 있는지 확인 : Queue.getBuffer(), Queue.isEmpty()
  • 추가 / 삭제 : Queue.enqueue(), Queue.dequeue()
  • 첫번째 데이터 / 사이즈 / 전체 삭제 : Queue.front(), Queue.size(), Queue.clear()
  • 줄 서기 구조



2. 큐 구현하기

기본

// Queue() : 생성자 함수로 초기 데이터 설정
function Queue(array){
    this.array = array ? array : []
}

// getBuffer() : 객체 내 데이터 셋 반환
Queue.prototype.getBuffer = function(){
    return this.array.slice()
}

// isEmpty() : 객체 내 데이터 o/x
Queue.prototype.isEmpty = function () {
    return this.array.length === 0
}

let queue = new Queue([1,2,3])
console.log(queue) //Queue { array: [ 1, 2, 3 ] }

let data = queue.getBuffer()
console.log(data) //[ 1, 2, 3 ]
console.log(data === queue.array) //false
console.log(queue.isEmpty()) //false
console.log(Object.getOwnPropertyDescriptors(Queue.prototype))



enqueue(), dequeue()

// enqueue() : 데이터 추가
Queue.prototype.enqueue = function (element){
    return this.array.push(element)
}

// deuqeue() : 데이터 삭제
Queue.prototype.deuqeue = function (){
    return this.array.shift()
}

let queue = new Queue([1,2,3])
console.log(queue) //Queue { array: [ 1, 2, 3 ] }

queue.enqueue(3)
queue.enqueue(4)
console.log(queue) //Queue { array: [ 1, 2, 3, 3, 4 ] }

queue.deuqeue()
console.log(queue) //Queue { array: [ 2, 3, 3, 4 ] }



front(), size(), clear()

// front() : 가장 첫 데이터 반환
Queue.prototype.front = function () {
  return this.array.length === 0 ? undefined : this.array[0];
};

// size() : 큐 내 데이터 개수 확인
Queue.prototype.size = function () {
  return this.array.length;
};

// clear() : 큐 초기화
Queue.prototype.clear = function () {
  this.array = [];
};

let queue = new Queue([1, 2, 3]);
console.log(queue); //Queue { array: [ 1, 2, 3 ] }

queue.deuqeue();
console.log(queue); //Queue { array: [ 2, 3, 3, 4 ] }
console.log(queue.front()) //2
console.log(queue.size()) //2
queue.clear()
console.log(queue.size()) //0



3. 큐 최적화

  • 방식 개선 : enqueue / dequeue 방식을 push/shift 에서 index로 변경
  • shift 는 O(n)
  • index 는 O(1)
// Queue() : 생성자 함수로 초기 데이터 설정
function Queue(array) {
  this.array = array ? array : [];
  this.tail = array ? array.length : 0;
  this.head = 0;
}

// enqueue() : 데이터 추가
Queue.prototype.enqueue = function (element) {
  //   return this.array.push(element);
  return (this.array[this.tail++] = element);
};

// deuqeue() : 데이터 삭제
Queue.prototype.deuqeue = function () {
  //   return this.array.shift();
  if (this.tail === this.head) {
    return undefined;
  }
  let element = this.array[this.head];
  delete this.array[this.head++];
  return element;
};

// dequeue 하면
// Queue { array: [ <1 empty item>, 4, 2, 3, 5, 6, 7 ], tail: 7, head: 1 }



benchmark

  • 성능 측정 : enqueue/dequeue 성능 비교
  • queue1 : push/shift
  • queue2 : index
  • 배열의 내장 함수는 대부분 O(n)이므로 알고리즘 해결시는 가능한 index 로 접근하여 시간복잡도 낮추기
let queue1 = new Queue1()
let queue2 = new Queue2()

function benchmark(queue, enqueue){
    let start = Data.now()
    for (let i =0; i<count; i++){
        enqueue?queue.enqueue() : queue.deuqeue()
    }
    return Data.now() - start
}

console.log("enqeueu1: " + benchmark(queue1, 1) + "ms") //enqeueu1: 7ms
console.log("enqeueu1: " + benchmark(queue2, 1) + "ms") //enqeueu2: 6ms

console.log("dequeue1: " + benchmark(queue1, 0) + "ms") //deqeueu1: 4968ms
console.log("dequeue2: " + benchmark(queue1, 0) + "ms") //dequeue2: 8ms



4. 문제 - 큐 만들기

자연수를 저장하는 큐를 만들고자 한다. 입력으로 주어지는 큐 명령어를 처리하는 프로그램을 작성하시오.
명령어의 종류는 총 6가지이며, 아래와 같으며, 명령에 따라 반환된 값을 result 배열에 넣도록 한다.

  • enqueue X : 자연수 X를 큐 뒤쪽에 넣는다.
  • dequeue : 큐 앞쪽에 있는 값을 제거하고 그 값을 반환한다. 만약 값이 없다면 -1을 반환한다.
  • empty : 큐가 비어 있다면 1, 아니면 0을 반환한다.
  • size : 큐에 들어있는 자연수 개수를 반환한다.
  • front : 큐 앞쪽에 값이 있다면 해당 값을, 없다면 -1을 반환한다.
  • back : 큐 뒤쪽에 값이 있다면 해당 값을, 없다면 -1을 반환한다.


if (!Array.prototype.enqueue) {
  Array.prototype.enqueue = function (element) {
    this.push(element);
  };
}

if (!Array.prototype.dequeue) {
  Array.prototype.dequeue = function () {
    if (this.length === 0) return -1;
    return this.shift();
  };
}

if (!Array.prototype.empty) {
  Array.prototype.empty = function () {
    return this.length === 0;
  };
}

if (!Array.prototype.size) {
  Array.prototype.size = function () {
    return this.length;
  };
}

if (!Array.prototype.front) {
  Array.prototype.front = function () {
    if (this.length === 0) return -1;
    return this[0];
  };
}

if (!Array.prototype.back) {
  Array.prototype.back = function () {
    if (this.length === 0) return -1;
    return this[this.length - 1];
  };
}

function answer(cmds) {
  let result = [];

  // 코드 구현 시작 영역
  let queue = [];
  for (let i = 0; i < cmds.length; i++) {
    switch (cmds[i]) {
      case "dequeue":
        result.push(queue.dequeue());
        break;
      case "empty":
        let temp = queue.empty() ? 1 : 0;
        result.push(temp);
        break;
      case "size":
        result.push(queue.size());
        break;
      case "front":
        result.push(queue.front());
        break;
      case "back":
        result.push(queue.back());
        break;
      default:
        queue.enqueue(Number(cmds[i][8]));
        break;
    }
  }

  // 코드 구현 종료 영역
  return result;
}

let input = [
  ["enqueue 1", "enqueue 2", "dequeue", "dequeue", "dequeue"],
  [
    "enqueue 3",
    "enqueue 4",
    "enqueue 5",
    "enqueue 6",
    "front",
    "back",
    "dequeue",
    "size",
    "empty",
  ],
  [
    "enqueue 7",
    "enqueue 8",
    "front",
    "back",
    "size",
    "empty",
    "dequeue",
    "dequeue",
    "dequeue",
    "size",
    "empty",
    "dequeue",
    "enqueue 9",
    "empty",
    "front",
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i]));
}

//#1[ 1, 2, -1 ]
//#2[ 3, 6, 3, 3, 0 ]
//#3[
//  7,  8, 2, 0,  7,
//  8, -1, 0, 1, -1,
//  0,  9
//]

function Queue 만든 후 prototype 통해 메소드들 만들어 줘도 된다!

enqueue X 얻기 위해 cmds[i].split(" ")[0] 👍



5. 문제 - 카드 뽑기

친구와 카드 게임을 하려고 한다.
카드는 총 n장 있으며, 1부터 n까지 번호가 차례대로 붙어 있다.
카드의 순서는 1번 카드가 가장 위에 있고 N번 카드가 가장 아래인 상태로 놓여 있다.
이때 맨 위에 있는 한 장을 빼서 나누고, 그 다음 맨 위에 있는 한 장을 아래로 집어 넣으면서, 모든 카드를 분배할 때까지
카드 한장씩 빼고 넣는 작업을 반복한다.
이러한 규칙으로 분배된 카드의 순서를 알려주는 프로그램을 작성하시오.
입력 값은 자연수가 주어지며, 규칙에 따라 분배되는 카드의 순서를 기록해 배열 형태로 반환하시오.

function answer(n) {
  let result = [];

  // 코드 구현 시작 영역
  let queue = [];
  for (let i = 1; i <= n; i++) {
    queue.enqueue(i);
  }

  while (1) {
    result.push(queue.dequeue());
    queue.enqueue(queue.dequeue());
    
    if (queue.size() === 1){
        result.push(queue.dequeue())
        break
    }
  }

  // 코드 구현 종료 영역
  return result;
}

let input = [4, 7, 10];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i]));
}

// #1[ 1, 3, 2, 4 ]
// #2[
//   1, 3, 5, 7,
//   4, 2, 6
// ]
// #3[
//   1, 3,  5, 7, 9,
//   2, 6, 10, 8, 4
// ]



6. 문제 - 프린터 출력 🤔

새로 구매한 프린터는 우선 순위를 고려해 프린트 결과물을 출력해주기 때문에 아래 규칙으로 동작한다.
현재 등록된 프린트 문서들의 우선순위를 확인하고, 가장 높은 우선순위 문서가 먼저 출력되며
현재 선택된 문서가 가장 높은 우선순위 문서가 아니라면, 취소되고 다시 뒤쪽 순서로 설정돼 추가된다.
만약, 3개의 문서 a,b,c가 대기 상태이고, 중요도가 1,2,3이라면
abc > bca > cab > c출력 > ab > ba > b출력 > a > a출력으로 동작한다.
현재 등록된 문서 우선순위를 보고, 내가 등록한 문서가 언제 출력될 지 계산하는 프로그램을 작성하시오.
입력은 우선순위와 0번부터 시작하는 문서 번호가 주어지고, 주어진 문서번호가 출력될 순서를 반환한다.

function Queue() {
  this.array = [];
}

Queue.prototype.enqueue = function (element) {
  this.array.push(element);
};

Queue.prototype.dequeue = function () {
  if (this.length === 0) return -1;
  return this.array.shift();
};

Queue.prototype.front = function () {
  if (this.length === 0) return -1;
  return this.array[0];
};

Queue.prototype.max = function () {
  return Math.max(...this.array);
};

function answer(priorities, select) {
  let result = -1;

  // 코드 구현 시작 영역
  // 1. 큐 내 우선순위가 가장 높은 문서를 확인
  // 2. 그 문서가 나올 때까지, 나머지 문서는 dequeue > enqueue (순서 바꿈)
  // 3. 문서 번호 select 를 찾을 때까지 계속 반복
  let vq = new Queue(); // 인덱스
  let pq = new Queue(); // 우선순위

  for (let i = 0; i < priorities.length; i++) {
    vq.enqueue(i);
    pq.enqueue(priorities[i]);
  }

  let count = 0;
  while (true) {
    // 출력
    if (pq.front() === pq.max()) {
      count++;
      if (vq.front() === select) {
        result = count;
        break;
      } else {
        vq.dequeue();
        pq.dequeue();
      }
    } else {
      vq.enqueue(vq.dequeue());
      pq.enqueue(pq.dequeue());
    }
  }

  // 코드 구현 종료 영역
  return result;
}

let input = [
  [[3], 0],
  [[3, 4, 5, 6], 2],
  [[1, 1, 5, 1, 1, 1], 0],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i][0], input[i][1]));
}

// #1 1
// #2 2
// #3 5