자바스크립트로 큐 자료구조 구현하기

스택과 마찬가지로 기술면접에서 제일 자주 등장하는 자료구조인 큐다.
구현하는 연습을 해두면 나중에 기술면접에서 도움이 될 것 같아서 직접 구현해보았다.

Queue란

큐는 선형 자료구조의 일종으로 First In First Out(FIFO, 선입선출)이라는 특징을 가지고 있다. 스택과는 반대로 먼저 들어간 원소가 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다.

기본적인 자료구조인만큼 이미지를 보면 간단하게 이해할 수 있다.

자바스크립트 큐 구현

이번에도 구현하기 전에 어느정도 구글링을 조금 해봤는데 스택과 마찬가지로 대부분의 블로그에서 메소드를 사용하여 간단하게 구현한 코드가 많아서 나는 이번에도 메서드를 사용하지 않고 구현하기로 했다.

노드 만들기

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

class를 사용해서 노드를 만들고 constructor안에 원소값을 담을 item인스턴스와 다음 노드를 가리키는 next인스턴스를 초기화 시켜줬다.

큐 만들기

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

class를 사용해 head와 tail로 큐 자료구조의 머리노드와 꼬리노드를 가리키는 인스턴스를 생성했다.
length는 현재 큐의 길이를 나타내는 인스턴스이다.

enqueue(item) 기능 구현하기

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

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

enqueue는 큐에 원소를 추가하는 함수다.
class내의 함수로 enqueue를 만들고 매개변수로 추가할 원소값을 받는다.
넘겨받은 item원소로 Node를 사용해 노드를 생성해준다.
조건문을 사용하여 큐가 비어있다면 머리노드와 꼬리노드 모두 현재 생성된 노드를 가리키게 하고, 큐에 노드가 존재한다면 꼬리노드의 다음 노드로 생성된 노드를 가리키게 한다.
그리고 꼬리노드를 생성된 노드로 변경한다.
마지막으로 큐에 노드가 추가됐기 때문에 length++로 큐의 길이를 늘려준다.

dequeue() 기능 구현하기

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

  // enqueue(item) {}

  dequeue() {
    const pop = null;
    if (!this.length) return null;
    else if (this.head === this.tail) {
      pop = this.head.item;
      this.head = null;
      this.tail = null;
    } else {
      pop = this.head.item;
      this.head = this.head.next;
    }
    this.length--;
    return pop;
  }
}

dequeue함수는 큐에서 원소를 추출하는 함수다.
enqueue와 마찬가지로 class내의 함수를 만들고 큐가 비어있을 경우 아무것도 추출하지 못하기 떄문에 null을 반환한다.
그리고 head와 tail이 동일하다면 현재 큐에 노드가 하나라는 뜻이기 때문에 pop이라는 변수에 원소값을 담고 head와 tail이 가리키는 값을 null로 바꾼다.
만약 노드가 2개 이상이라면 head의 원소값을 pop변수에 담고 머리노드를 현재 머리노드가 가리키는 다음 노드로 변경한다.
마지막으로 큐의 길이를 1줄여주고 pop을 반환한다.

size() 기능 구현하기

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

  // enqueue(item) {}

  // dequeue() {}

  size() {
    return this.length;
  }
}

size 함수는 현재 큐의 길이를 확인하는 함수다.
인스턴스로 생성한 length를 반환하여 간단하게 구현하였다.

front() 기능 구현하기

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

  // enqueue(item) {}

  // dequeue() {}

  // size() {}
  
  front() {
    return this.size() ? this.head.item : null;
  }
}

front함수는 큐의 머리노드의 원소값을 확인하는 함수다.
큐에 노드가 존재한다면 머리노드의 원소값을 반환하고 존재하지 않는다면 null을 반환한다.

back() 기능 구현하기

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

  // enqueue(item) {}

  // dequeue() {}

  // size() {}
  
  // front() {}
  
  back() {
    return this.size() ? this.tail.item : null;
  }
}

back함수는 큐의 꼬리노드의 원소값을 확인하는 함수다.
front함수와 동일하게 큐의 노드가 존재한다면 꼬리노드의 원소값을 반환하고 노드가 존재하지 않는다면 null을 반환한다.

최종 코드

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

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

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

  dequeue() {
    const pop = null;
    if (!this.length) return null;
    else if (this.head === this.tail) {
      pop = this.head.item;
      this.head = null;
      this.tail = null;
    } else {
      pop = this.head.item;
      this.head = this.head.next;
    }
    this.length--;
    return pop;
  }

  size() {
    return this.length;
  }

  front() {
    return this.size() ? this.head.item : null;
  }

  back() {
    return this.size() ? this.tail.item : null;
  }
}

이렇게 자바스크립트를 사용해 큐 자료구조를 구현해보았다.
잘 동작하는지 확인하기 위해 간단하게 테스트 코드를 작성해서 실행해보았다.

// 테스트 코드
let que = new Queue(); // 큐 자료구조 생성
console.log(que);
que.enqueue(1); // 큐에 원소 추가
que.enqueue(2);
que.enqueue(3);
console.log(que);
console.log(`que front: ${que.front()}`); // 큐의 머리노드 원소값 확인
console.log(`que back: ${que.back()}`); // 큐의 꼬리노드 원소값 확인
console.log(`que size: ${que.size()}`); // 큐의 길이 확인
console.log(`que pop: ${que.dequeue()}`); // 큐의 머리노드 추출
console.log(`que pop: ${que.dequeue()}`);
console.log(`que pop: ${que.dequeue()}`);
console.log(`que pop: ${que.dequeue()}`);
console.log(que);
console.log(`que size: ${que.size()}`);

테스트 실행 결과