큐 (Queue)

Jun 2k (Jun2)·2023년 9월 25일

CS지식 WIL cs공부 자료구조&알고리즘

자료구조&알고리즘

목록 보기

7/19

큐(Queue)

First In First Out 이라는 개념을 가진 선형 자료구조이다.
종류는 2가지로 Linear Queue와 Circular Queue가 존재한다.

출처: 이선협 강사님 데브코스 강의 자료

큐 자료구조는 놀이기구를 타기 위한 대기 줄로 비유할 수 있다.

EnQueue : 이제 막 줄을 서려고 하는 사람
DeQueue : 놀이기구를 탈 차례가 된 사람
Front : 대기줄의 맨 첫 번째 사람
Rear : 대기줄의 맨 마지막 사람

선형 큐

Array로 구현

선형 큐는 배열로 구현할 수는 있지만 몇 가지 문제가 발생한다.

큐의 Front 요소를 DeQueue 하게 되면 배열의 자리를 계속 남아있으므로 메모리를 차지하게 된다.
큐의 Rear 요소를 EnQueue 하게 되면 배열 크기가 조정되어야 한다. JavaScript는 유동적으로 제어되기 떄문에 큰 문제는 되지 않는다. 하지만 그 크기가 무한정 커질 수도 있는 문제가 있다.
따라서 공간을 더 확보하기 위해 요소들을 앞당기는 작업이 필요하다. 이 작업은 선형 O(n) 시간복잡도가 소요된다.

Linked List로 구현

Head는 Front, Tail은 Rear가 된다.
배열과 다르게 index에 대한 고민은 하지 않아도 된다.

출처: 이선협 강사님 데브코스 강의 자료

JavaScript 내 큐 구현

Array로 구현하기

class Queue {
  constructor() {
    this.queue = []; // 배열로 구현
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    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(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

Linked List로 구현하기

// Linked List로 구현
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;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

shift 함수는 쓰지 말기!!

shift 함수는 O(n) 시간 복잡도가 소요되므로 큐를 구현할 때는 비효율적이다.

Circular Queue

Front와 Rear가 이어져 있는 큐
Linked List로 구현해도 되나 크게 이점은 없다.

Array로 구현하기

최대 사이즈를 지정한다.
Front나 Rear의 인덱스가 최대 사이즈를 벗어날 경우 다시 0번 인덱스부터 시작하도록 구현한다.

// Circular Queue를 배열로 구현

class Queue {
  constructor(maxSize) {
    // 원형 큐는 최대 사이즈가 존재
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  enqueue(value) {
    if (this.isFull()) {
      console.log('Queue is full.');
      return;
    }
    this.queue[this.rear] = value;
    // rear 값이 최대 사이즈를 벗어날 경우 초기화
    this.rear = (this.rear + 1) % this.maxSize;
    this.size += 1;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size -= 1;
    return value;
  }

  isFull() {
    return this.size === this.maxSize;
  }

  peek() {
    return this.queue[this.front];
  }
}

const queue = new Queue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
queue.enqueue(16); // Queue is full.
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
console.log(queue.size); // 2
console.log(queue.peek()); // 4
queue.enqueue(16);
queue.enqueue(32);
console.log(queue.isFull()); // true