Queue란? (선입선출)

큐는 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식
스택은 한 곳 (top) 에서만 추가, 추출이 이루어지지만, 큐는 데이터를 쌓는 곳(rear)있고 반대쪽에선 데이터를 내보내는 곳 (front)이 있다.

• FIFO(First In First Out) 방식 : 양쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조, 제일 처음에 들어온 데이터가 가장 빨리 나가는 방식이다. 선입선출이라는 특징을 갖는다.( LILO(Last In Last Out)라고도 부른다.)

• 선입선출 특징때문에 큐는 주로 데이터가 입력된 순서대로 처리해야할때 사용한다.

큐의 주요 속성

• 속성 front / rear
• front : 데이터를 제거하는 위치, dequeue연산을 할 위치
• rear : 데이터를 추가하는 위치, enqueue연산을 할 위치

대표 메소드

• shift() : 맨 앞에 데이터를 반환하고 해당 데이터를 큐에서 제거
• enqueue : queue에 값을 집어넣는다(front에서 데이터를 추가)
• dequeue : queue에서 값을 빼내온다. (rear에서 데이터를 제거)
• isEmpty : queue안에 데이터가 비어있는지 확인
• SIze : queue의 크기를 확인한다.

예시) 한가지 예시로 Queue에 대해 쉽게 이해해본다. → 톨게이트를 통과하는 차들

• 톨게이트 출구 : front 데이터를 제거하는 위치

• 톨게이트 입구 : rear 데이터를 추가하는 위치
  먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.

• 가장 일찍 진입한 자동차 → 가장 먼저 톨게이트를 통과한다.
  다시 말해, 가장 늦게 진입한 자동차 → 가장 늦게에 나간다.

큐 구현 방법

정적어레이로 큐의 동작 구현방식을 본다면? 대표적으로 두개의 변수가 필요하다.

• first(front) : 젤 처음에 데이터를 가리킬 변수 임시정의

• next(front) : 다음 데이터가 들어갈 장소를 알려주는 변수 임시정의

1. 처음 큐가 주어질때, 아무 데이터도 없는 상태에선 first와 next가 같은 곳을 가리킨다.
2. enqueue(queue,A) → A라는 값이 들어왔을때 first는 A를 가르키고 next는 다음 데이터가 들어올 곳을 가리킨다.
3. enqueue(queue,A) → B라는 값이 두번째로 들어왔을때 first는 제일 처음 들어온 A를 기억해야하기 때문에 그대로 있고, next는 다음 칸으로 넘어가서 다음데이터가 들어올 곳을 가리킨다.
4. dequeue(queue) → 제일 처음들어왔던 A가 빠지고, first는 한칸 앞으로 이동한다. next는 그 자리를 그대로 지키고 있다.

Array을 활용하여 Queue로 사용 예시!

* 상기하기 → 자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없습니다.
    
- 배열로 자료구조 Queue 구현하기 → 선입선출 특징을 구현한다면?
    

array.shift()

• 앞에서 부터 요소를 제거한다. → 가장 일찍 들어간 데이터가 가장 일찍 제거된다.
  

        // const array = new Array() 미리 정의된 Array 객체를 사용합니다.
        const queue = [];
        
        queue.push(1); // [1]
        queue.push(2); // [1, 2]
        queue.push(3); // [1, 2, 3]
        queue.push(4); // [1, 2, 3, 4]
        queue.push(5); // [1, 2, 3, 4, 5]
        
        console.log(queue); // [1, 2, 3, 4, 5]
        
        queue.shift(); // [2, 3, 4, 5]
        queue.shift(); // [3, 4, 5]
        
        console.log(queue); // [3, 4, 5]

코딩하는 거니 https://www.youtube.com/watch?v=Vfg6-AWGsCw&list=PLLcbGhhl4sQCiZxLuqDDDH6q-rc4wyaKe&index=7
코드스테이츠