[JavaScript] 큐(Queue), 원형 큐(Circular Queue) 구현하기

큐(Queue)

FIFO(First In First Out) 개념을 가진 선형 자료구조로 먼저 들어간 값이 가장 먼저 나온다.

• DeQueue: 큐의 출력
• EnQueue: 큐의 입력

Array로 표현하기

array로 표현 시 간단하지만 front와 rear가 무한정 커질 수 있다는 단점이 있다.

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;
  }

  // front 인덱스에 해당하는 값 반환.
  peek() {
    return this.queue[this.front];
  }

  // 큐의 크기 반환.
  size() {
    return this.rear - this.front;
  }
}

Linked List로 표현하기

Linked List로 표현 시 front가 head, rear가 tail로 표현된다.

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;
  }
}

원형 큐(Circular Queue)

Front와 Rear가 이어져있는 Queue로 한정된 공간을 효율적으로 이용 가능.

maxSize를 정해서 큐의 크기를 제한하고, Front나 Rear가 크기를 벗어나면 다시 0번 인덱스부터 시작한다.

Array로 표현하기

class CircularQueue {
  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;
    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];
  }
}