[선형] 12. 원형 큐

05 Oct 2021 in 자료구조 on 선형

목차

1. 우선순위 큐 (Circular Queue)

원형큐

원형 형태를 가지며, 먼저 넣은 데이터가 먼저 나오는 FIFO(Fist In First Out) 기반의 선형 자료 구조
데이터가 꽉 찼는지 / 비어 있는지 확인 : CircularQueue.isEmpty(), CircularQueue.isFull()
데이터 추가 / 삭제 / 반환 : CircularQueue.enqueue(), CircularQueue.dequeue(), CircularQueue.getBuffer()
첫번째 데이터 / 사이즈 / 전체 삭제 : PriorityQueue.front(), PriorityQueue.size(), PriorityQueue.clear()

2. 구현하기

생성자, getBuffer(), isFull(), isEmpty()

// CircularQueue() : 초기 속성값 설정을 위한 생성자 함수
function CircularQueue(array=[], size=5){
    this.array = array
    this.size = array.length > size ? array.length : size
    this.length = array.length;
    this.head = 0
    // tail = 앞으로 새로 들어올 데이터가 추가될 위치
    this.tail = array.length
}

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

// isEmpty() : 데이터 비어있는지 확인
CircularQueue.prototype.isEmpty = function(){
    return this.length == 0
}

// isFul() : 데이터 꽉 차 있는지 확인
CircularQueue.prototype.isFull = function(){
    return this.length === this.size
}

let cq = new CircularQueue([1,2,3])
console.log(cq)
// CircularQueue {
//     array: [ 1, 2, 3 ],
//     size: 5,
//     length: 3,
//     head: 0,
//     tail: 3
//   }

console.log(cq.isEmpty()) //false
console.log(cq.isFull()) //false
console.log(Object.getOwnPropertyDescriptors(CircularQueue.prototype))

enqueue(), dequeue()

// enqueue() : 데이터 추가
CircularQueue.prototype.enqueue = function (element) {
  if (this.isFull()) return false;

  this.array[this.tail] = element;
  this.tail = (this.tail + 1) % this.size;
  this.length++;

  return true;
};

// dequeue() : 데이터 삭제
CircularQueue.prototype.dequeue = function () {
  if (this.isEmpty()) return undefined;

  let element = this.array[this.head];
  delete this.array[this.head];
  this.head = (this.head + 1) % this.size;
  this.length--;

  return element;
};

let cq = new CircularQueue([1, 2, 3],4);
cq.enqueue(5)
cq.enqueue(6)
console.log(cq)
// CircularQueue {
//   array: [ 1, 2, 3, 5 ],
//   size: 4,
//   length: 4,
//   head: 0,
//   tail: 0
// }


cq.dequeue()
cq.dequeue()
console.log(cq)
// CircularQueue {
//     array: [ <2 empty items>, 3, 5 ],
//     size: 4,
//     length: 2,
//     head: 2,
//     tail: 0
//   }

front(), size(), clear()

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

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

// clear() : 큐 초기화
CircularQueue.prototype.clear = function (size = DEFAULT_SIZE) {
  this.array = [];
  this.size = size;
  this.length = 0;
  this.head = 0;
  this.tail = 0;
};

let cq = new CircularQueue([1, 2, 3], 4);
cq.enqueue(5);
cq.enqueue(6);
console.log(cq);

cq.dequeue();
cq.dequeue();
console.log(cq);
// CircularQueue {
//     array: [ <2 empty items>, 3, 5 ],
//     size: 4,
//     length: 2,
//     head: 2,
//     tail: 0
//   }

console.log(cq.dataSize()) //2
console.log(cq.front()) //3
cq.clear()
console.log(cq) //CircularQueue { array: [], size: 5, length: 0, head: 0, tail: 0 }

3. 문제 - 대표 선출 🤔

마을에 대표를 선출해야 한다.
모두 자신이 대표가 되고 싶어 하며, 아래 규칙을 통해 대표를 선출하기로 하였다.
규칙은 먼저 원탁에 둘러 앉아 시계 방향으로 1번부터 n번까지 번호를 부여한다.
그리고 주사위를 통해 굴러나온 숫자 m의 사람을 제외하고, 그 다음으로 나온 주사위 숫자 k만큼 이동해가며 대표 후보에서 제외시킨다.
이렇게 순회하여 1명이 남을 때까지 반복해 마을의 대표를 선출하기로 하였다.
n, m, k가 주어졌을 때 대표 후보에서 제외되는 번호를 출력해주는 프로그램을 제작하시오.
입력은 n, m, k의 자연수가 주어지며, 대표 후보에서 제외되는 번호를 순차적으로 배열로 반환한다.

function CircularQueue(size) {
  this.array = new Array(size);
  this.size = size;
  this.length = 0;
  this.head = 0;
  this.tail = 0;
}

CircularQueue.prototype.enqueue = function (element) {
  this.length++;
  this.array[this.tail++ % this.size] = element;

  return true;
};

// dequeue() : 데이터 삭제
CircularQueue.prototype.dequeue = function () {
  this.length--;
  return this.array[this.head++ % this.size];
};

function answer(n, m, k) {
  let result = [];
  // 코드 구현 시작 영역
  // 1. 원탁에 후보 번호 세팅
  let cq = new CircularQueue(n);
  for (let i = 1; i <= n; i++) {
    cq.enqueue(i);
  }

  // 2. 첫번째 노드 위치로 설정
  cq.tail = cq.head = (n + m - 1) % n;

  // 3. k만큼 움직이면서 대표 후보를 제거 (제거된 번호는 result 에 추가)
  // 제거된 번호는 result 에 추가
  let count;
  result.push(cq.dequeue());
  while (cq.length != 0) {
    count = k - 1;
    while (count--) {
      cq.enqueue(cq.dequeue());
    }
    result.push(cq.dequeue());
  }
  return result;
}

let input = [
  [8, 2, 3],
  [10, 2, 3],
  [20, 5, 7],
];

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

// #1[
//   2, 5, 8, 4,
//   1, 7, 3, 6
// ]
// #2[
//    2, 5, 8, 1, 6,
//   10, 7, 4, 9, 3
// ]
// #3[
//    5, 12, 19,  7, 15, 3, 13,
//    2, 14,  6, 18, 11, 9,  8,
//   10, 17,  4, 16, 20, 1
// ]