큐(Queue)?

먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조.

큐의 구현

큐는 연결리스트(linked list) 로 구현할 수 있다.

프로퍼티

1. front = null
2. rear = null
3. size = 0

enqueue(value)

큐의 맨 뒤에 데이터를 삽입한다.
1. 제일 앞(front)이 null이라면 생성된 노드를 front로 지정한다.
2. 제일 뒤(rear)가 있다면 생성된 노드를 rear.next로 저장한다.
3. rear를 생성된 노드로 지정한다.
4. size를 늘린다.

dequeue()

큐의 맨 앞에서 데이터를 제거한다.
1. 삭제할 노드가 없다면 삭제하지 않는다. (rear === null)
2. 삭제할 노드를 임시로 저장한다.
3. front를 front.next가 가리키는 노드로 대체해준다.
4. size를 줄인다.
5. 임시로 저장한 노드를 반환한다.

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
  getSize(){
    return this.size;
  }
  isEmpty(){
    return this.rear === null;
  }
  enqueue(data){
    const node = new Node(data);
    if(this.size === 0) this.front = node;
    if(this.rear) this.rear.next = node;
    this.rear = node;
    this.size++;
  }
  dequeue(){
    if(rear === null) return null;
    const temp = this.front.data;
    this.front = this.front.next;
    this.size--;
    return temp;
  }
}