[4주차] Queue

+++🍒class 사용시 아래 메소드만 사용하게 제한할 것🍒+++

(Stack) push, pop
(Queue) push, shift

---

1. Queue 개념

• FIFO (선입선출)

• Queue는 '대기열'이라는 뜻을 가지며, 동시에 처리 못하는데 서버 감당 안 될 때 자주 사용됨 (ex. 콘서트 티켓팅, 수강신청)

• 편의상 Enqueue를 디큐, Dequeue 를 인큐라고 부르겠다

• Enqueue란, 뒷쪽(Rear)에서 data push()하는 동작

• Dequeue란, 앞쪽(Front)에서 shift()하는 동작

• 스택과 유사한 자료구조, 둘 다 배열로 쉽게 구현 가능 (BUT 문제점 존재)
  ❓어떤 문제점인가❓
  -- 배열은 선언시 크기 결정되므로 overflow 또는 underflow 에러 발생 가능성
  

시간복잡도 O(1)
공간복잡도 = O(n) ( = queue.length )

+++🍒참고🍒+++
연결리스트로 Queue 구현시 -> 공간복잡도 O(n)

• 이유 : Node 개수 = 메모리 개수
  ❓Node에는 data, prev, next 총 3개니까 O(3n) 아닌 이유❓
  -- 이유 : 시간복잡도에선 지수 > 계수 (차이 미미함).. O(n) 과 O(3n)은 같은 것

+++⭐️ 연결리스트로 Queue 구현시 주의점 ⭐️+++

• dequeue 시간복잡도를 O(1)로 만들어줘야 함
• 힌트 : removeFirst() 메소드 별도로 추가해줘야 함 (= 사실상 배열의 dequeue)

2. Queue 구현하기

class Queue {
    arr = [];

    enqueue(value) { //push
        return this.arr.push(value);
    }

    dequeue() { // shift
        return this.arr.shift();
    }

    peek() { // top, first 
        return this.arr[0]; // arr.at(0)
        // Stack과 달리 마지막 'arr.at(-1)'이 아닌 처음 것
    }

    get length() {
        return this.arr.length;
    }
}

3. 실행 결과

const queue = new Queue();

console.log(
    queue.enqueue(1), // 1
    queue.enqueue(3), // 2
    queue.enqueue(5), // 3
    queue.enqueue(2), // 4
    queue.enqueue(4), // 5
    queue.length, // 5 ... 여기까지 Stack과 똑같음
    
    // [1, 3, 5, 2, 4]
    // [3, 5, 2, 4]
    queue.dequeue(), // 1
    queue.peek(), // 3 
)