Javascript 자료구조 2. 큐(queue)

오늘 공부할 자료구조는 큐입니다!

큐(Queue)

1. 큐란?

큐는 스택과 함께 많이 사용되는 기본적인 자료구조로 일렬로 늘어선 줄을 의미하기도 하며, 입구와 출구가 분리되어있는 자료구조입니다! 우리가 줄을 서서 대기한다면 먼저 선 사람이 먼저 나오게되죠?!

그 원리를 이용한 자료구조가 큐이며 선입선출[First In First Out] 특성을 가지게 돼요!

 

2. 큐의 연산?

큐의 연산에는 두가지가 존재해요.

첫번째는 enqueue를 통한 입력, 두번째는 dequeue을 통한 제거 (플러스로 queue의 길이 ..!?)

큐의 입구는 뒤(rear)에 있기 때문에 enqueue는 뒤로 입력, dequeue은 앞(front)에서 제거하는 구조로 되어있어요!

 

3. 시간복잡도?

enqueue : O(1)

dequeue : O(1)

search : O(n)

 

4. 구현 (Javascript)

사실 stack과 마찬가지로 queue도 Javascript에서 리스트로 쉽게 사용할 수 있어요. (기본적으로 push와 shift가 구현되어있어요!)

하지만 데이터의 양이 많은 리스트라면 shift()를 통한 연산은 최대 O(n)의 연산을 갖기 때문에 시간초과가 나는 문제들이 생겨요! 처음에 단순히 shift도 O(1)로 생각하고 남발할 수 있는데 조심해야합니다ㅎㅎ

 

그렇기때문에 연결리스트를 통해 queue를 구현해보도록 할께요!

 

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

class Queue {
  #size = 0;
  constructor() {
    this.front = null;
    this.rear = null;
  }
  enqueue(val) {
    const node = new Node(val);
    this.#size++;
    if (!this.rear) this.front = node;
    else this.rear.next = node;
    this.rear = node;
  }
  dequeue() {
    if (!this.front) throw new Error('Element does not exist.');
    this.#size--;
    const val = this.front.val;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    return val;
  }
  size() {
    return this.#size;
  }
  getQueue() {
    let queue = [];
    let head = this.front;
    while (head) {
      queue.push(head.val);
      head = head.next;
    }
    return queue;
  }
  search(n) {
    if (n >= this.#size) throw new Error('Index can not access.');
    let idx = 0;
    let head = this.front;
    while (head) {
      if (idx === n) return head.val;
      head = head.next;
      idx++;
    }
  }
  getFront() {
    if (!this.front) return null;
    return this.front.val;
  }
  getRear() {
    if (!this.rear) return null;
    return this.rear.val;
  }
}

여기서 search는 n번째 인덱스를 찾는 과정이에요!

 

위와 같이 직접 Queue를 구현해 볼 수 있으니 연결리스트를 통해 구현하는 연습을 꼭 해보도록 해봐요!