큐

GoGoDev·2022년 4월 13일

coding test

Coding-Test Study

목록 보기

7/8

큐

FIFO(First In First Out)의 개념을 가진 선형 자료구조다.

게임에서 큐를 잡는다라고 하는데, 여기서 큐는 자료구조의 큐와 같은 의미이다. 먼저 게임 대기열에 진입을 한 사람은 조건이 충족되었을 때, 가장 먼저 게임에 들어갈 수 있다.

Linear Queue (선형 큐)

배열로 선형 큐 표현

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  
  deqeue() { // 맨 먼저 들어온 값이 나간다.
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  
  peek() {
    return this.queue[this.front];
  }
  
  size() {
    return this.rear - this.front;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue)
console.log(queue.dequeue()); // 1

console.log(queue.size()); // 2
console.log(queue.peek()); // 2

console.log queue

스택과는 다르게 큐는 배열에서 사용하기 어렵다.
배열에서 DeQueue가 일어나면 배열의 값은 사라지지만 배열 자체는 존재하게된다. 또한 EnQueue를 하게 되면 배열의 크기만큼 추가가 가능하지만 배열의 크기보다 더 많은 데이터를 넣는다면 Overflow가 발생할 것이다. 자바스크립트에서는 배열의 크기를 지정하지 않으면 무한정 커질 수 있으므로 Front나 Rear의 크기 또한 무한정 커질 수 있다.
이를 방지하기 위해 삭제된 배열을 빈 값으로 두는 것이 아니라 뒤에 있는 값들을 앞으로 당겨와야하는데 이때 $O(n)$ 이 소요된다.

연결리스트로 선형 큐 표현

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  enqueue(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1;
  }
  
  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size -= 1;
    return value;
  }
  
  peek() {
    return this.head.value;
  }
}

연결리스트로 큐를 표현하려면 연결리스트의 Head를 Front로 두고 tail은 Rear가 된다. 연결리스트를 사용하면 배열과 달리 Index에 대한 고민을 안해도 된다.

Circular Queue

Front와 Rear가 이어져있는 Queue이다.
한정된 크기를 효율적으로 사용하기 위해 사용한다.

class CQueue {
  constructor(maxSize) { // 크기 지정
    this.queue = [];
    this.maxSize = maxSize
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(value) {
    if (this.isFull()) {
      console.log('queue is full');
      return;
    }
    this.queue[this.rear++] = value;
    this.rear = this.rear + 1 % this.maxSize;
  }
  
  deqeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    return value;
  }
  
  isFull() {
    return this.size === this.maxSize;
  }
  
  peek() {
    return this.queue[this.front];
  }
}

maxSize를 통해 queue의 크기를 정한다. front 또는 rear가 maxSize를 벗어난 경우, 첫번째 인덱스로 가도록 구현한다.
rear가 증가되고 나서 최대 크기로 나머지로 나누면 어느 지점에 rear를 둘지 알 수 있다.
isFull을 통해 무한정 늘어나는 queue를 방지할 수 있다.