[자료구조] Queue 구현하기

 

직접 그린 큐

 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.

출처 - 위키백과

 

구현하기

class Queue<T> {
  private size = 0;
  private currSize = 0;
  private queue: Array<T> = [];
  private first = 0;
  private rear = 0;
  constructor(size: number) {
    this.size = size;
  }

  enqueue(value: T): Queue<T> {
    if (this.currSize >= this.size) {
      throw new Error('queue is overflow');
    }

    this.queue[this.rear] = value;
    this.rear++;
    this.currSize++;

    if (this.rear === this.size) {
      this.rear = 0;
    }

    return this;
  }

  dequeue(): T {
    if (this.currSize <= 0) {
      throw new Error('queue is empty');
    }

    const currValue = this.queue[this.first];
    this.first++;
    this.currSize--;

    if (this.first === this.size) {
      this.first = 0;
    }
    return currValue;
  }

  peek(): T {
    if (this.currSize <= 0) {
      throw new Error('queue is empty');
    }
    return this.queue[this.first];
  }
}

export default Queue;

 

사용하기

const myQueue = new Queue(3);
myQueue.enqueue(10);
myQueue.enqueue(9);
myQueue.enqueue(8);

console.log(myQueue);

myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();

console.log(myQueue);

myQueue.enqueue(8);
console.log(myQueue.peek());

결과

 

선형 큐의 단점을 보완한 원형 큐로 구현 하였다. 

스택과는 반대되는 개념이다.