자료구조&알고리즘_큐

큐 (Queue)

First In First Out (먼저 삽입된 item이 먼저 삭제된다)
라는 개념을 가진 선형 구조이다.

[사진출처]
https://galid1.tistory.com/483

큐에는 선형 큐와 원형 큐가 있다.

선형 큐 (Linear Queue)

1. 배열로 표현하기

• Enqueue로 데이터를 추가하다가 Dequeue를 할 때 앞에 빈공간이 생긴다.
• Front나 Rear의 값이 무한정 커질 수 있다.
• 공간을 더 쓰기 위해 배열을 앞당기는 작업이 필요하다.

2. 연결리스트로 표현하기

• 배열에서의 문제를 어느정도 해결한다.
• 연결리스트의 head는 Front가 되고 tail은 Rear가 된다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  
  peek() {
    return this.queue[this.front];
  }
  
  size() {
    return this.rear - this.front;
  }

😨 Shift 함수는 쓰지 말 것
shift함수는 선형시간이 걸리기 때문에 큐에서 기대하는 로직이 수행되지 않는다!
(shift 자주썼는데...)

const queue = [1,2,3];
queue.push(4);
const value = queue.shift(); // O(n)
console.log(value); // 1

원형 큐 or 환형 큐 (Circular Queue)

한정된 공간을 효율적으로 이용할 때 사용한다.

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 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() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size -= 1;
    return value;
  }
  
  peek() {
    return this.queue[this.front];
  }
  
  isFull() {
    return this.size === this.maxSize;
  }

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스