자료구조 03 큐 | JS

큐 | Queue

이미지 출처

• 선형 자료구조의 일종으로
• First In First Out (FIFO): 먼저 들어간 원소가 먼저 나옴
• 입력과 출력을 한 쪽 끝(front, rear)으로 제한
• 버퍼(buffer), 마구 입력된 것을 처리하지 못하고 있는 상황, BFS

enqueue: 데이터 넣기
dequeue: 데이터 빼기 + 삭제
peek: head 데이터 확인(출력하면 가장 먼저 나올 데이터)
isEmpty: 비어있는지 확인

배열을 통한 구현

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
  peek() {
    return this._arr[0];    
  }
  isEmpty() {
    return this._arr.length === 0 ? true : false;
  }
}

연결 리스트를 통한 구현

import LinkedList from '../linked-list/LinkedList';
// 기존에 제작한 LinkedList import

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }
  enqueue(value) { // push와 동일
    this.linkedList.append(value);
  }

  dequeue() { // shift와 동일
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }
  
  peek() {
    if (!this.linkedList.head) {
      return null;
    }
    return this.linkedList.head.value;
  }
  
  isEmpty() {
    return !this.linkedList.head;
  }

}

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
helloworldjavascript

Photo by Alain Pham on Unsplash