[자료구조] 큐

📌 참고 사이트

[자료구조] JS로 구현하는 큐 (Queue) (velog.io)

[자료구조] JS로 구현하는 큐 (Queue)

 

 

 

📋 큐 (Queue)

FIFO (First Input First Out) 원칙 하에 운용되는 자료구조이다.

가장 먼저 들어온 데이터가 가장 먼저 빠져나가야 한다.

 

 

📍 JS에서 배열을 이용하여 큐의 기능 흉내내기

배열 내장 메소드 중에서 shift()라는 메서드가 있는데, 배열의 가장 앞에 있는 요소를 제거하는 역할을 한다.

이 shift() 메소드를 통해 FIFO를 구현할 수 있다.

내부 로직은 다음과 같이 된다.

 

1️⃣ 배열의 첫 번째 요소에 접근하여 해당 값을 반환하고 배열에서 제거

2️⃣ 값은 제거되었지만 여전히 메모리 공간을 차지하고 있다.

3️⃣ 나머지 배열의 원소들을 한 칸씩 앞으로 당겨 주어야 한다.

 

앞으로 당겨주는 연산 때문에 상당한 시간이 소요되기도 한다.

따라서 데이터의 양이 매우 많거나 시간 제한이 빡센 문제에서는 시간 초과가 발생할 수 있으므로 그럴 경우 아래에서 나오는 내용과 같이 큐를 직접 구현하는 것이 도움이 될 것이다.

 

💡 배열의 첫 번째 요소(front 포인터)와 마지막 요소(rear 포인터)를 나타내는 투 포인터를 이용하는 경우 O(1)의 시간 복잡도를 보장할 수 있지만, 요소 제거 시 해당 자리에 undefined가 차지하게 되어 공간 최적화가 이루어지지 않을 수 있다.

(큐에서 값을 하나 꺼내면 front의 위치가 기존 위치 + 1로 이동, 큐에 값을 추가하면 rear의 위치가 기존 위치 + 1로 이동)

 

 

📍 JS로 큐 직접 구현해 보기 

클래스를 이용해 큐를 구현해 보도록 하자.

 

1️⃣ 큐 초기화하기

 

class Queue {
  constructor() {
    // 값을 저장할 객체
    this.storage = {};
    // 첫 번째 원소를 가리키는 포인터
    this.front = 0;
    // 마지막 원소를 가리키는 포인터
    this.rear = 0;
  }
}

 

2️⃣ 큐의 크기 구하기

객체를 사용하였기 때문에 Object.keys().length 등의 메서드를 통해 큐의 크기를 구할 수도 있지만 이는 배열로 변환하는 과정에서 O(N)의 시간 복잡도를 가지기 때문에 투 포인터를 사용해 더 빠르게 큐의 크기를 구해 볼 것이다.

위에서 봤던 맨 앞 원소를 가리키는 front와 맨 뒤 원소를 가리키는 rear 포인터를 이용하여 rear - front + 1의 방식으로 크기를 구해줄 수 있다.

예를 들어 front가 3번 인덱스를 나타내고, rear가 9번 인덱스를 나타낼 때 남아 있는 데이터의 개수(길이)는 9 - 3 + 1 = 7(개) 가 된다.

 

❗ 주의할 점

front와 rear가 같아지는 순간은 데이터가 1개만 남아있다는 것일수도 있고, 아무 데이터가 없다는 것을 의미하기도 한다.

아무 데이터가 없을 수도 있는 이유는 1단계에서 두 개의 포인터를 똑같이 0을 가리키도록 초기화했기 때문이다.

데이터가 딱 1개 남았을 상황에서 데이터를 하나 꺼내오면 front의 값은 rear를 추월하게 되고, 동시에 해당 값을 지울 때 아직 rear의 위치는 변하지 않고 있다. 따라서 this.storage[rear]에 접근하였을 때 undefined가 나오면 값이 (삭제되어) 들어있지 않다는 것을 알 수 있고, 큐에 데이터가 없다는 것을 알 수 있다.

이는 처음에 포인터를 모두 0으로 초기화했을 때에도 성립한다. 이때에도 this.storage[rear] === undefined이므로 큐에 데이터가 없다는 것을 알 수 있다.

 

class Queue {
  constructor() {
    // 값을 저장할 객체
    this.storage = {};
    // 첫 번째 원소를 가리키는 포인터
    this.front = 0;
    // 마지막 원소를 가리키는 포인터
    this.rear = 0;
  }
  
  // 큐의 크기 구하기
  size() {
    // rear가 가리키는 값이 undefined이면 들어있는 데이터가 없다는 얘기
    if (this.storage[this.rear] === undefined) {
      // 따라서 길이 0 반환
      return 0;
    }
    // rear가 가리키는 값이 유효한 경우
    else {
      // 데이터의 길이(개수) 반환
      return this.rear - this.front + 1;
    }
}

 

3️⃣ 큐에 데이터 추가하기

큐에 데이터가 삽입되는 경우, front 포인터는 그대로 유지되고, rear 포인터의 위치만 조정될 것이다.

 

여기서도 주의할 점이, 데이터가 없는 경우이다.

위에서도 살펴봤듯이 데이터가 없는 경우는 초기 상태인 front와 rear가 모두 0일 때 또는 중간에 쌓인 데이터를 모두 꺼내서 비운 경우로 나눌 수 있다.

2번째 경우에서 front와 rear를 다시 0으로 초기화 해주어 애초부터 데이터가 들어가지 않았던 상태처럼 만들어 주면 큐에 데이터를 추가할 때 항상 0번에서부터 추가하면 된다.

 

출처: [자료구조] JS로 구현하는 큐 (Queue) (velog.io)

 

class Queue {
  constructor() {
    // 값을 저장할 객체
    this.storage = {};
    // 첫 번째 원소를 가리키는 포인터
    this.front = 0;
    // 마지막 원소를 가리키는 포인터
    this.rear = 0;
  }
  
  // 큐의 크기 구하기
  size() {
    // rear가 가리키는 값이 undefined이면 들어있는 데이터가 없다는 얘기
    if (this.storage[this.rear] === undefined) {
      // 따라서 길이 0 반환
      return 0;
    }
    // rear가 가리키는 값이 유효한 경우
    else {
      // 데이터의 길이(개수) 반환
      return this.rear - this.front + 1;
    }
    
    // 큐에 요소 추가하기
    add (value) {
      // 큐에 데이터가 없는 경우
      if (this.size() === 0) {
        // 0번 위치에 값을 넣고 포인터의 위치는 그대로 유지한다.
        this.storage['0'] = value;
      }
      // 큐에 데이터가 존재하는 경우
      else {
        // rear 포인터 한 칸 뒤로 이동
        this.rear += 1;
        // rear 포인터가 가리키는 곳에 값 추가
        this.storage[this.rear] = value;
      }
    }
}

 

위에서 this.storage['0'] 으로 키 값에 문자열 '0'을 넣은 이유는 JS 객체는 키 값으로 오직 문자열과 심볼만 허용하기 때문이다.

 

4️⃣ 큐에서 데이터 제거하기

큐에서 데이터를 꺼내는 경우 맨 앞에 있는 데이터부터 꺼내기 때문에 front 포인터의 위치가 재조정되어야 한다.

위치를 재조정하기 전에 기존 위치에 담긴 값을 제거하는 과정도 있어야 한다.

역시 데이터 추가때처럼 두 포인터의 값이 동일해지는 경우에 다시 초기화시켜 0으로 유지시켜 주는 과정도 있어야 한다.

만약 데이터가 아무것도 존재하지 않은 경우라면 존재하지 않는 값에 접근을 하더라도 undefined를 반환할 뿐 에러가 발생하지는 않으므로 예외 처리는 하지 않아도 된다. 

 

class Queue {
  constructor() {
    // 값을 저장할 객체
    this.storage = {};
    // 첫 번째 원소를 가리키는 포인터
    this.front = 0;
    // 마지막 원소를 가리키는 포인터
    this.rear = 0;
  }
  
  ......
  
  // 큐에서 데이터 제거하기
  popleft() {
    // 현재 큐에서 첫번째 요소를 임시로 담을 변수
    let temp;
    // front와 rear가 같을 때 (데이터가 하나만 남았을 때) 
    if (this.front === this.rear) {
      // 현재 front에 담긴 값을 임시 변수에 가져오기
      temp = this.storage[this.front];
      // 큐의 첫번째 요소 삭제하기
      delete this.storage[this.front];
      // front가 rear의 값보다 더 커지는 것을 방지하기 위해 front와 rear을 모두 0으로 초기화
      this.front = 0;
      this.rear = 0;
    }
    // 데이터가 여러 개 있을 때 (rear가 front보다 큰 일반적인 경우)
    else {
    	// 현재 front에 담긴 값 가져오기
        temp = this.storage[this.front];
        // 큐에서 첫번째 값 삭제하기
        delete this.storage[this.front];
        // 맨 앞 요소가 삭제되었으므로 front는 바로 다음으로 이동
        this.front += 1;
    }
    // 제거된 데이터 반환하기
    return tmp;
  }
}

 

위처럼 구현한 큐를 사용해 보면 다음과 같이 동작을 잘 하는 것을 볼 수 있다.

 

// 인스턴스 생성
const queue = new Queue();

// queue에 데이터 추가하기
queue.add(1);
queue.add(2);
queue.add(3);

console.log(queue.storage);     // {0: 1, 1: 2, 2: 3}
console.log(queue.front);     // 0
consoel.log(queue.rear);     // 2

// queue에서 데이터 제거하기
queue.popleft();     // 1 반환
queue.popleft();     // 2 반환

console.log(queue.storage);     // {2: 3}
// 요소가 하나 남았을 때의 front와 rear는 같다.
console.log(queue.front);     // 2
console.log(queue.rear);     // 2

// queue의 길이 확인하기
console.log(queue.size());     // 1

// queue의 요소 다 없애고 요소 추가해보기
queue.popleft();     // 3

// 요소 하나가 남은 것을 없애고 나니 front와 rear가 0으로 초기화되었다.
console.log(queue.front);     // 0
console.log(queue.rear);     // 0

queue.push(1);
console.log(queue.storage);     // {0: 1}
// 데이터가 1개만 추가되었을 때는 front와 rear가 계속 0
console.log(queue.front);     // 0
console.log(queue.rear);     // 0

 

 

💻 전체 코드

 

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    if (this.storage[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.rear + 1;
    }
  }
  
  add(value) {
    if (this.size() === 0) {
      this.storage['0'] = value;
    } else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }
  
  popleft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front = 0;
      this.rear = 0;
    } else {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
}