[ Data Structure ] 🍡 큐(Queue)

📚 큐(Queue)의 개념

큐(Queue) 는 '줄을 서다' 라는 뜻을 가지고 있다.
큐는 먼저 들어간 데이터가 먼저 나오는 자료구조이다.
큐역시 스택과 마찬가지로 생활 속에서 쉽게 예를 찾아볼 수 있는데

식당에 줄을 선 순서대로 식당에 입장장할 때를 생각해보면 된다.

이런 큐(Queue) 의 특징을 선입선출 또는 FIFO(first in first out)이라고 한다.

그리고 스택과 마찬가지로 큐도 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

 

⚙️ 큐(Queue)의 동작 원리

그럼 큐(Queue) 에서 원소가 이동하는 과정을 다음과 같이 그림으로 그려서 알아보도록 하겠다.

 

1. 우선 빈 큐(Queue) 를 하나 선언해주겠다.

 

 

2. 해당 큐에 원소 2 를 삽입하는데 빈 큐이므로 제일 앞에 삽입을 한다.( push에 해당한다. )

 

이어서 5 를 삽입하는데 ( push에 해당한다. )
5 는 2 다음으로 삽입했으니까 5 는 2 보다 뒤에 있게된다.

 

 

3. 이제 2 번과 같은 상태 큐에서 pop을 하게되면
다음과 같이 나중에 들어온 5 가 아니라 먼저 들어온 2 가 먼저 나오게 된다.

 

그리고 나서 이어서 pop을 한 번 더 진행하면 5 가 빠져나오게 된다.

 

그럼 이제 모든 원소가 큐(Queue) 에서 빠져나오게된 상태이므로 다음과 같이 텅 비어있다.

 

스택(Stack) 은 먼저 들어온게 나중에 빠져나오지만
큐(Queue) 의 경우 먼저 들어온게 먼저 빠져나오는 것을 알 수 있다.
 

 

⚖️ 큐(Queue)의 정의, ADT

큐(Queue) 의 ADT 를 정의해보고 큐가 실제로 동작하는 원리를 살펴보자

- 큐(Queue)의 ADT

구분	정의	설명
연산	isFull	큐에 들어 있는 데이터 개수가 maxsize인지 확인 후 boolean 값으로 반환
"	isEmpty	큐에 들어 있는 데이터가 하나라도 있는지 없는지 확인후 boolean 값으로 반환
"	push	큐에 데이터를 push 한다.
"	pop	큐에서 처음에 push한 데이터를 pop하고, 해당 데이터를 반환한다.
상태	front	큐에서 가장 처음 pop한 위치를 기록한다.
"	rear	큐에서 최근에 push한 데이터의 위치를 기록한다.

 

✨ 큐(Queue)의 동작 구현하기

그럼 위와 같이 정의한 내용을 바탕으로
다음과 같이 큐(Queue)의 동작을 구현해 보자

class Queue {
  _queue = [];
  _maxSize = 10;
  constructor(maxSize) {
    this._maxSize = maxSize;
  }

  isFull(){
    return this._queue === this._maxSize;
  }

  isEmpty(){
    return this._queue.length === 0;
  }

  push(item){
    this._queue.unshift(item);    
  }

  pop(){
    return this._queue.pop();
  }

  front(){
    return this._queue.at(-1);
  }

  rear(){
    return this._queue.at(0);
  }
}

const queue = new Queue();

console.log(queue._queue); // []
console.log(queue.isEmpty()); // true

queue.push(1); // -> [1] 
queue.push(2); // -> [2, 1]
queue.push(3); // -> [3, 2, 1]

console.log(queue._queue); // rear -> [3, 2, 1] -> front

console.log(queue.rear()); // rear: 3
console.log(queue.front()); // front: 1

queue.pop(); // [3, 2] -> 
queue.pop(); // [3] -> 

console.log(queue._queue); // rear -> [3] -> front

 

🤔 큐(Queue)는 언제 쓸까?

이처럼 먼저 들어온 것을 먼저 처리하는 큐(Queue) 의 동작 방식은
프로그래밍 언어에서 많이 활용되고 있다.

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐(Queue) 가 활용된다.

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 요청하면
  서버는 요청이 들어온 순서대로 작업을 처리하는데 이때 큐(Queue)를 활용할 수 있다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나
  마우스 움직임을 처리할 때 큐(Queue) 를 활용할 수 있다.

 

📝 문제 풀이

그럼 지금까지 학습한 큐(Queue) 의 개념을 활용해서 해당 문제들을 풀어보고
풀이과정을 각 코드 마다 주석으로 작성하겠다.

💯 : 풀어서 정답인 문제
👀 : 참고해서 풀은 문제
🧪 : 정답을 보고 분석한 문제

 

💯 [ 문제 15 ]. 요세푸스 문제

문제 : 코딩 테스트 합격자 되기 - 자바스크립트 편

function solution(n, k){
  const queue = []; // 계산을 처리할 Queue
  const answerQueue = []; // 출력할 값을 담아놓는 Queue

  // 1부터 n명 까지의 사람들을 queue에 순서대로 채운다.
  for(let i=1; i<=n; i++) queue.unshift(i); // rear -> [ 5, 4, 3, 2, 1 ] -> front

  // queue에 요소가 존재할 때
  while(queue.length){    

    // queue의 front에서 제거, rear에 추가 동작을 k번 만큼 반복
    for(let i=0; i<k; i++){ 
      const item = queue.pop(); // queue의 front에 pop!
      queue.unshift(item); // queue의 reart에 push!
    }            

    const item = queue.pop(); // pop!       
    answerQueue.push(item); // 출력할 값을 담아놓는 answerQueue 삽입한다.        
  }      

  return answerQueue.at(0); // answerQueue의 rear에 들어있는 요소를 반환
}

console.log(solution(5, 3)); // 3
console.log(solution(5, 2)); // 4

 

👀 [ 문제 16 ]. 기능개발

문제 : 프로그래머스 - 기능개발

• ⏰ 시간초과

function solution(progresses, speeds) {
  const date = []; // 각 기능이 완료될 때까지 걸리는 일수를 저장
  let count = 0; // 작업이 진행된 날짜를 카운팅

  // progresses 배열에 요소가 있을 동안
  while (progresses.length) {

    // progresses의 첫 번째 작업이 100 이상 완료된 경우
    if (progresses[0] >= 100) {
      progresses.shift(); // 첫 번째 작업을 배열에서 제거
      speeds.shift();  // 그에 해당하는 첫 번째 속도도 제거

      // 작업 완료까지 걸린 날짜 count를 date 배열에 추가
      date.push(count);

      // count를 초기화하여 다음 작업의 날짜를 다시 계산
      count = 0;
      
    } else { // 작업이 100이상 완료 안될 경우
      
      // progresses[0]에 해당하는 작업을 speeds[0]만큼 더 진행
      progresses[0] += speeds[0];

      // 하루가 지났으므로 count 증가
      count++;
    }
  }

  const answer = []; 
  let c = 1; // 같은 날 배포될 기능의 개수를 카운팅하는 변수
  let stack = []; // 완료된 작업 날짜를 추적할 스택

  stack.push(date.shift()); // 첫 번째 작업의 완료 날짜를 스택에 추가
  
  // date 배열에 요소가 있는 동안
  while (date.length) {
    const top = stack.at(-1);  // 스택의 top 값을 가져옴 (마지막으로 배포된 작업의 완료 날짜)
    // top이 다음 작업의 완료 날짜보다 크거나 같으면(같은 날 배포 가능)
    if (top >= date.at(0)) {
      c++; // 배포될 기능의 개수를 증가
      date.shift(); // 완료된 작업을 date에서 제거
      
    } else { // 다음 작업이 더 늦게 완료되는 경우
      
      answer.push(c); // 배포될 기능의 개수를 결과 배열에 추가
      c = 1; // 카운트 초기화          

      // 현재 작업의 완료 날짜를 스택에 추가하여 새로운 기준 top으로 설정
      stack.push(date.shift());
    }
  }

  // 마지막 남은 배포될 기능의 개수를 결과 배열에 추가
  answer.push(c);

  return answer;
}

console.log(solution([93, 30, 55], [1, 30, 5])); // [2, 1]
console.log(solution([95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1])); // [1, 3, 2]

 

원하는 결과값을 얻었으나 시간초과가 걸려부럿다..


다른 코드와 비교해서 다음과 같이 시간초과를 해결했다.

- 시간초과 해결

function solution(progresses, speeds) {
  const date = [];  // 각 기능이 완료되기까지 걸리는 시간을 저장

  // progresses 배열을 순회해 각 작업이 완료되기까지 필요한 시간을 계산
  for (let i = 0; i < progresses.length; i++) {
    // 100%가 될 때까지 남은 작업량을 속도로 나누어 완료까지 필요한 날짜 계산
    // Math.ceil을 사용해 올림하여 소수점 이하 날짜를 처리
    let time = Math.ceil((100 - progresses[i]) / speeds[i]);

    // 계산된 완료 각 시간들을 date 배열에 추가
    date.push(time);
  }

  const answer = [];
  let count = 1;  // 기능의 개수
  let current = date[0]; // 첫 번째 기능이 기준이 되는 완료 날짜

  // date 배열을 순회하면서 배포 가능한 작업 그룹을 계산
  for (let i = 1; i < progresses.length; i++) {

    // 현재 기준 날짜보다 늦게 완료되는 작업들이 있는지 확인
    if (current >= date[i]) { 

      // 기준 날짜보다 늦지 않은 작업들은 같은 배포 그룹에 포함
      count++;

    } else {
      // 기준 날짜보다 늦게 완료되는 작업이 있다면 완료
      answer.push(count); // 현재 그룹의 작업 개수를 answer 배열에 추가
      count = 1;  // 카운트를 1로 초기화
      current = date[i];  // 새로운 기준 날짜로 변경
    }
  }

  // 마지막으로 남은 작업일을 answer에 추가
  answer.push(count);

  return answer; 
}

console.log(solution([93, 30, 55], [1, 30, 5])); // [2, 1]
console.log(solution([95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1])); // [1, 3, 2]

while 문으로 해당 요소가 존재할 때 까지 루프를 도는 방식으로 하지않고
shift() 메서드를 사용하지 않은 방향으로 코드를 작성해 시간초과를 해결했다.

 

💯 [ 문제 17 ]. 카드뭉치

문제 : 프로그래머스 - 카드뭉치

function solution(cards1, cards2, goal) {    

    // 중첩 반복으로 goal만큼 순회해 cards1, cards2 요소와 각각 비교한다.
      for(let i=0; i<goal.length; i++){
        for(let j=0; j<goal.length; j++){          
              // i에 순회하는 goal요소와 j로 순회하는 cards1가 같을 때 해당 cards1 요소를 제거 
              // 일치하지 않을 경우 cards2로 위에 작업을 처리
            if(cards1[j] === goal[i]) cards1.shift();                           
            else if (cards2[j] === goal[i]) cards2.shift();                     
        }
    };    

    // cards1, cards2를 하나의 배열로 결합
    const result = [...cards1, ...cards2];    

      /**
     * - 결합된 배열 result에 요소가 있을 경우 goal요소중에서 result에 포함되어 있는게 하나라도 있으면       
     *  'Yes' 그렇지 않으면 'No'를 반환
     * - 예외일 경우 'Yes'반환
     */
    if(result.length)!goal.some(str => result.includes(str)) ? 'Yes' : 'No'
      else return 'Yes';      
}

console.log(solution(
  ["i", "drink", "water"],
  ["want", "to"],
  ["i", "want", "to", "drink", "water"]
)); // "Yes"

console.log(solution(
  ["i", "water", "drink"],
  ["want", "to"],
  ["i", "want", "to", "drink", "water"]
)); // "No"

 

회고
스택(Stack) 이랑 비슷한 느낌이라 개념은 이해 됐다.
그런데 막상 난이도가 있는 문제를 풀때는 적용하기 힘들다.. 🥲

 

출처

• 코딩 테스트 합격자 되기 - 자바스크립트 편
• 프로그래머스