[자료구조] 큐에 대해서 알아보자 (자바스크립트)

안녕하세요 :)

오늘은 자료구조 '큐'에 대해서 알아보겠습니다!

 

자바스크립트에서는 Class 를 이용하여 Queue를 구현합니다.

먼저 Class 의 개념에 대해 알고 싶으시다면 아래의 문서를 참고해주세요!

http:// https://ko.javascript.info/class

 

 

---

 

 

큐(Queue)  ?

---

'First In First Out' 이라는 개념을 가진 선형 자료구조다.

단어 그대로 먼저 들어간 것이 먼저 나오고, 나중에 들어간 것이 나중에 나온다는 개념이다.

 

큐의 맨 앞을 Front 라고 부르고,

큐의 맨 뒤는 Rear 라고 부른다.

 

큐에 요소를 추가하는 것을 EnQueue,

빼는 것을 DeQueue 라고 한다.

 

 

 

큐는 놀이 동산 대기 줄?!

---

큐를 현실에 비유하면 놀이동산 대기 줄이라고 볼 수 있다.

대기자의 수를 Queue 라고 볼 수 있고, 맨 앞에 줄 선 사람이 Front, 마지막 사람이 Rear 이다.

그리고 놀이기구를 타러가는 사람은 DeQueue의 요소라고 볼 수 있고,

이제 줄을 서려는 사람은 EnQueue 라고 볼 수 있겠다.

 

 

큐의 종류

---

큐는 선형 큐와 환형 큐가 있다.

 

 

---

 

Linear Queue (선형 큐)

---

선형 큐는 배열(Array)로 표현할 수 있다. 그러나 스택과는 달리 배열로 표현하는 것이 조금 어렵다.

큐 또한 배열에 값을 순차적으로 담을 수 있으며 이 때 첫 index가 front, 마지막 index가 rear이다.

 

만약 DeQueue를 한다면 front 부터 하나씩 사라지며, 배열이기 때문에 빈 공간은 메꿔지지 않는다.

만약 EnQueue를 한다면 rear 뒤 index에서 차례대로 추가가 된다.

 

EnQueue가 반복되어 한정된 공간인 배열이 전부 꽉 찼다면 더 이상 Queue의 값을 추가할 수 없다. 

자바스크립트에서는 배열이 자유롭게 증감되기 때문에 이런 문제는 없지만, front나 rear 인덱스 값이 무한정 커질 수 있다.

따라 배열에서 공간을 더 쓰기 위해 앞당기는 작업이 필요한데 이 작업을 수행하면 선형시간(O(N))이 소요된다.

 

이런 문제를 해결할 수 있는 방법은 연결 리스트로 Queue 를 구현하는 것이다.

그렇게 되면 head는 front가 되고, tail은 rear가 된다.

연결리스트를 사용한다면 index에 대한 고민을 하지 않아도 괜찮기 때문이다.

 

---

JavaScript 에서 사용법

Array 로 구현

---

아래의 방법은 구현이 간단하기 때문에 코딩테스트에서 Queue를 사용할 때 추천한다.

아까 설명한 대로 front와 rear가 무한정 커질 수 있다는 단점은 있다.

 

class Queue {
  // 먼저 3개의 클래스 변수가 필요하다.
  // 요소를 넣을 배열 변수와 각각 front와 rear을 나타내기 위한 index 변수가 필요하다.
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  // enqueue 함수는 rear 영역에 값을 넣고 rear 인덱스를 하나 증가시키면 된다.
  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  // front 인덱스에 해당하는 값을 반환하고 증가시키면 된다.
  // 하지만 바로 반환하면 함수가 종료되기에 임시로 변수에 값을 넣어두고 삭제한 다음 인덱스 값을 증가하고 반환한다.
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  // peek 함수는 queue의 가장 앞에 있는 값을 알아내는 함수다. 프론트 인덱스에 해당하는 값을 반환한다.
  peek() {
    return this.queue[this.front];
  }

  //큐의 길이는 아래처럼 간단히 구할 수 있다.  
  size() {
    return this.rear - this.front;
  }
}

 

이처럼 큐의 구현은 생각보다 어렵지 않다.

자바스크립트에서 기본적으로 큐가 제공되지 않는 것은 아쉽지만 구현이 어렵지 않기 떄문에

한번 직접 코드를 구현해보면 코딩 테스트에서도 당황하지 않을 것이다.

이해가 안된다면 노트에 그림을 그려 차례 차례 로직을 따라가보는 걸 추천한다. :)

ex) [1, 2, 3, 4, 5] 

 

 

Linked List 로 구현

---

class Node {
  // 연결리스트 구현과 크게 다르지 않다.
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  // 생성자 부분도 마찬가지로 크게 다르지 않다.
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 연결 리스트의 append 함수와 크게 다르지 않다.
  // 연결 리스트 코드에서 가장 중요한 개념은 this.tail = newNode 는 대입보다는
  // this.tail이 newNode를 가리킨다고 보아야 한다는 것이다.
  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;
  }

  // Stack을 연결 리스트로 구현했을 때 pop 하는 경우와 동일하다.
  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size -= 1;
    return value;
  }

  // peak 함수는 head의 값을 그대로 반환한다.
  peek() {
    return this.head.value;
  }
}

이처럼 연결 리스트로 Queue를 구현하는 것도 크게 어렵지 않다!

앞서 Singly Linked List부터 Stack, Queue 차례대로 구현해보면 쉽게 이해할 수 있다.

하지만 배열로 구현하는 것보다는 조금 더 복잡하기 때문에 코딩테스트에서는 배열로 구현하는 것을 추천한다.

 

 

‼️ Shift 함수는 쓰지 마세요!

간혹 자바스크립트 Queue 구현을 shift 함수로 구현할 수 있다고 나와있는 정보가 많은데, 이는 잘못된 정보다.

자바스크립트 배열에서 shift는 선형 시간(O(N))이 걸리기 때문에 Queue에서 기대하는 로직이 수행되지 않는다.

 

정말 제대로 Queue를 쓰고 싶다면 오늘 배운 코드를 참고하여 Queue를 작성하는 것이 좋다.

 

 

---

Circular Queue (환형 큐)

---

환형 큐는 환형 연결 리스트처럼 처음(First)과 끝(Rear)이 이어져 있는 Queue다.

한정된 공간을 효율적으로 이용할 때 사용하는 자료구조이기 때문에 연결 리스트로 구현해도 상관은 없지만 크게 이점이 없다.

 

class Queue {
  // maxSize 를 받아 queue의 사이즈를 제한한다.
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  // 크기를 벗어날 경우 다시 0번 인덱스부터 시작하도록 코드를 작성함.
  // enqueue가 증가될 경우 최대 크기로 나머지 연산을 해준다.
  // 최대 크기를 벗어날 경우 다시 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(value) {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size -= 1;
    return value;
  }

  // 큐가 꽉찼는지 확인하는 함수. 이를 통해 무한정 enqueue되는 것을 막을 수 있다.
  isFull() {
    return this.size === this.maxSize;
  }

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

 

이처럼 환형 큐 구현도 어렵진 않지만 코딩 테스트에서 거의 나오지 않기 때문에 외워야 할 필요는 없다.

 

---

 

오늘은 큐에 대해 알아보았습니다!

도움이 되셨다면 좋아요 눌러주세요~! :)