Queue(큐)

1. Array로 큐를 구현

• 단점
  • DeQueue를 하면 배열 앞부분이 공백이 된다.
  • 배열에서 리얼 인덱스 값이 무한정 커질 수 있다.

javascript

class Queue {
  constructor() {
    this.queue = [];
    this.head = 0;
    this.tail = 0;
  }

  // queue 대기행렬에 데이터 입력
  // tail 쪽에 데이터가 추가됨
  enqueue(value) {
    this.queue[this.tail++] = value;
  }

  // queue 대기행렬에서 데이터 출력
  // head 쪽 데이터가 꺼내지고 데이터들이 앞으로 옮겨짐
  dequeue() {
    const value = this.queue[this.head];
    delete this.queue[this.head];
    this.head += 1;
    return value;
  }

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

  size() {
    return this.tail - this.head;
  }
}

2. Linked List로 큐를 구현

javascript

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size += 1;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size -= 1;
    return value;
  }

  peek() {
    return this.head.value;
  }
}