[자료구조] 큐 (Queue)

큐는 선입선출(FIFO, First-In-First-Out)의 구조를 가지는 자료구조다. 한쪽 끝에 요소를 추가 (enqueue)하고, 다른 쪽 끝에서 요소를 제거(dequeue) 한다. 큐는 배열 또는 단일 연결 리스트를 통해서 구현할 수 있다.
BFS 알고리즘 또한 일반적으로 queue를 이용하여 구현한다.

시간 복잡도

동작	Big-O
Enqueue	O(1)
Dequeue	O(1)
Front	O(1)
Back	O(1)
isEmpty	O(1)

자바스크립트로 구현

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


class Queue {

  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  // Queue의 뒤에 데이터 추기
  add(value) {
    this.size++;
    let node = new QueueNode(value);
    if (!this.front) {
      this.front = node;
    } else if (!this.back) {
      this.front.next = node;
      this.back = node;
    } else {
      let back = this.back;
      back.next = node;
      this.back = node;
    }
  }

  // 맨 앞 데이터 출력
  peek() {
    if (this.front) {
      return this.front.value;
    } else {
      return null;
    }
  }

  // 맨 앞 데이터 출력 하고 삭제
  poll() {
    if (this.front) {
      this.size--;
      let front = this.front;
      this.front = front.next;
      return front.value;
    } else {
      return null;
    }
  }
}

const queue = new Queue();

queue.add(1);
queue.add(2);
queue.add(4)
console.log(queue.peek());
console.log(queue.poll());
console.log(queue.poll());
console.log(queue.poll());
console.log(`size: ${queue.size}`);

필수 문제

• LeetCode
  - Implement Stack using Queues

추천 연습 문제

• LeetCode
  - Implement Queue using Stacks
  - Design Hit Counter (LeetCode Premium)