[ ᴀʟɢᴏʀɪᴛʜᴍ ] Queue ( 큐 )

NewHa·2023년 10월 2일

ᴀʟɢᴏʀɪᴛʜᴍ

목록 보기

9/14

🌱 QUEUE ( 큐 )

👉🏻 큐 (Queue, '대기열') : 양 쪽 끝이 열려 있는 선형 데이터 구조로 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특징을 가집니다. 쉽게 말하면 우리가 실생활에서 순서를 위해 줄서는 모든 행동이 이에 해당합니다. 대표적인 예로 수강신청시 대기 순서대로 접속되는 것을 겪어 보셨을 것입니다. ~~(여기서 새로고침하면 줄의 맨 뒤로 옮겨가서 다시 줄서는 거 아시죠..?😱)~~ 입력과 출력의 방향이 각 고정되어 목록의 한 쪽 끝에서 모든 입력이 이루어지고, 다른 쪽 끝에서 모든 출력이 이루어집니다.

다른 언어의 경우 보통 내장 라이브러리로 큐를 제공하고 있습니다. 대표적으로 자바는 java.util.Queue를, 파이썬은 deque를 제공하고 있습니다. 그러나 자바스크립트의 경우 내장된 큐가 없어서 직접 자료 구조를 작성해야할 필요가 있습니다.

☀️ Type of Queue( 유형 )

다섯가지 유형의 큐가 있습니다.

입력 제한 큐(단순 큐)

한쪽 뒤에서만 입력받을 수 있고, 양쪽에서 요소 삭제가 가능한 큐 유형입니다. 이런 종류의 대기열은 FIFO를 따르지 않습니다. 최근에 삽입된 데이터를 제거해야 하고, 그러한 경우가 관련 없는 데이터, 성능 문제 등 일 수 있는 경우에 사용됩니다.

장점 : 추가되는 항목 수를 제한하여 대기열의 overflow 및 과부하를 방지, 시스템의 안정성과 예측가능한 성능을 유지하는 데 도움이 됩니다.
단점 : 제한이 너무 낮게 설정되고 아이템이 자주 폐기되는 경우, 리소스가 낭비가 발생할 수 있습니다. 제한이 너무 높게 설정되고 대기열이 꽉 차서 새 항목이 추가되지 않는 경우 대기 또는 차단으로 이어질 수 있습니다.

출력 제한 큐(간단 큐)

양쪽에서 입력을 받을 수 있고 요소 삭제는 한쪽에서만 수행할 수 있습니다. 입력이 실행될 우선 순위가 있고, 입력이 가장 먼저 실행되도록 첫 번째 위치에 배치될 수 있는 경우에 사용됩니다.

원형 큐

FIFO 원리에 따르지만, 배열의 맨 마지막 위치를 쓰면 다시 첫 번째 위치로 연결되어 큐를 채웁니다. 마지막 위치가 시작위치와 연결되는 원형구조를 띄어 '링 버퍼' 라고도 부릅니다. 마지막 위치와 시작위치를 연결하는 원형구조에 두개의 포인터가 움직이며 큐 연산을 합니다. 주로 메모리 관리, 교통시스템, CPU 스케줄링에 쓰입니다. 설정된 시간에 따라 신호등을 하나씩 반복적으로 켜거나, 운영체제가 실행 준비가 되었거나 특정 이벤트 발생을 기다리는 프로세스 대기열울 유지하는 경우에 사용되고 있습니다.

데큐(Deque, Double Ended Queue)

양쪽 끝에서 모두 삽입과 삭제 작업이 가능한 큐 데이터 구조입니다. 스택 작업과 큐 작업을 모두 지원하므로 둘 다로 사용할 수 있습니다. 요소를 제거하거나 추가해야 하는 문제를 효율적으로 해결할 수 있습니다. 데이터 처리에 더 많은 유연성이 제공되며 요소를 여러 방향으로 처리해야 하는 응용 프로그램에 사용할 수 있습니다. 구현시 이중 연결 리스트로 구현하는 게 가장 적합합니다.

우선순위 큐

각 요소에 우선순위 수준이 할당되는 대기열 유형입니다. 우선순위 수준이 높은 요소가 먼저 처리됩니다. 특정 작업이나 데이터 요소를 더 높은 우선 순위로 처리해야 하는 애플리케이션에 사용됩니다. 운영체제작업 예약 및 네트워크 패킷 예약이 있습니다. (자세한 내용은 해당 게시물을 참고하세요.)

☀️ Characteristic of Queue( 특징 )

🪴 기본 작업

Method	시간 복잡도	작 업
Enqueue(x)	O(1)	큐 끝에 요소를 추가 또는 저장합니다.
Dequeue()	O(1)	큐에서 요소를 제거합니다.
front / peek()	O(1)	큐의 front 노드의 데이터 요소를 삭제하지 않고 반환합니다.
rear()	O(1)	요소를 제거하지 않고 뒤쪽 끝에 있는 요소를 반환합니다.
isFull()	O(1)	큐가 가득 찾는 지 확인합니다.
isEmpty()	O(1)	큐가 비어 있는 지 확인합니다.

🪴 장 점

대용량 데이터를 쉽고 효율적으로 관리할 수 있습니다.
선입 선출의 원칙을 따르므로, 삽입﹒삭제 등의 작업을 쉽게 수행할 수 있습니다.
큐는 여러 소비자가 특정 서비스를 사용할 때 유용합니다.
큐는 데이터 프로세스 간 통신을 위한 속도가 빠릅니다.
큐는 다른 데이터 구조 구현에 사용될 수 있습니다.

🪴 단 점

대기열이 최대 용량에 도달해 더 이상 요소를 수용할 수 없을 때 overflow가 발생하고, 빈 큐에서 요소를 제거하려고 시도할 때 underflow가 발생합니다. 데이터가 손실될 수 있으며 애플리케이션 충돌이 발생할 수 있습니다.
우선순위가 낮은 작업이 높은 작업에 필요한 리소스를 보유할 때 우선순위 대기열에서 우선순위 반전이 발생합니다. 이로 인해 처리가 지연될 수 있고 시스템 성능에 영향을 미칠 수 있습니다.
여러 스레드 또는 프로세스가 서로 리소스를 해제하길 기다리고 있어 어떤 스레드도 진행할 수 없는 교착 상태가 발생합니다. 동시 대기열을 사용할 때 발생할 수 있으며 시스템 충돌로 이루어질 수 있습니다.
큐 크기, 액세스의 빈도, 큐에서 수행되는 작업 유형 등 다양한 요소로 인해 성능에 영향을 받을 수 있습니다. 큐 성능이 좋지 않으면 시스템 성능이 저하되고 사용자 경험이 저하될 수 있습니다.
여러 스레드라 동일한 큐에 동시에 엑세스 할 때 동기화 문제가 발생할 수 있습니다. 이로 인한 데이터 손상, 경쟁 조건 및 기타 오류가 발생할 수 있습니다.
큐는 특히 대규모 데이터 셋을 처리할 때 상당한 양의 메모리를 사용할 수 있습니다. 메모리 누수 및 기타 메모리 관리 문제가 발생하여 시스템 충돌 및 기타 오류가 발생할 수 있습니다.
중간 요소를 삽입하고 삭제하는 등의 작업에는 시간이 많이 걸립니다
클래식 큐에서는 기존 요소가 큐에서 삭제될 때에만 새 요소를 삽입할 수 있습니다.
요소를 검색하는 데 O(N)시간이 걸립니다.
큐의 최대 크기를 먼저 정의해야 합니다.

🪴 활 용

큐는 바로 처리할 필요 없이 FIFO 순서로 처리해야 하는 경우에 사용됩니다.

장치들 사이에서 데이터가 비동기식으로 전송되는 경우, 각 장치 사이에 존재하는 속도나 시간 차이를 극복하기 위해 임시기억장치의 자료구조로 큐를 사용합니다. 이를 통틀어 버퍼라고 합니다.
메인 메모리에서 여러 프로그램이 실행되는 것을 멀티 프로그래밍이라고 합니다. 이 때 여러 프로그램은 큐로 구성됩니다. 또 컴퓨터에는 차례로 실행되도록 예약된 작업을 실행할 때 큐를 사용해 구성되는 프로세서에 하나씩 할당합니다. 예컨대 CPU가 빠른 속도로 인쇄에 필요한 데이터를 만들고 여러 문서를 순서대로 인쇄 출력 버튼을 누르면, 인쇄 작업 큐에 들어갑니다. 프린터는 인쇄 작업 큐에 들어온 문서를 순서대로 인쇄합니다.
유투브와 같은 동영상 스트리밍 앱을 시청할 때, 다운로드 된 데이터가 충분하지 않은 경우 큐에 재생하기 충분한 데이터를 모았다가 재생합니다.
다양한 다른 데이터 구조, 알고리즘에서 필수 구성요소로 사용될 수 있습니다. 너비 우선 탐색 구현에서 처리해야 할 노드의 리스트를 저장할 때 대표적으로 큐를 사용합니다.
ATM 부스라인, 매표소 라인, 키보드의 키 누르기 순서, CPU 작업 스케줄링, 콜센터 고객 별 대기시간 등 다양한 곳에서 쓰입니다.

☀️ Implements of Queue ( 구현 )

🕶️ 배열로 구현

push()와 shift() 메서드로 큐의 기능을 구현할 수 있습니다. FIFO 원칙을 준수해 데이터의 삽입과 삭제가 가능하지만, 상당한 시간이 소요됩니다.

🌿 shift() method의 작동방식

Queue를 Array로 구현했을 때, 상당한 시간이 걸리는 이유는 shift()메소드의 작동방식 때문입니다.

배열의 첫번째 원소 (arr[0])에 접근해 원소를 반환하고 배열에서 제거합니다.

arr[0]의 공간이 비어있으므로 나머지 배열 원소들을 앞으로 한 칸씩 당겨서 재 정렬 을 해줍니다.

그래야 다음 shift()로 arr[0]에 접근했을 때 값을 가져올 수 있기 때문입니다.

👉🏻 즉, 두번째 과정으로 매번 shift() 메서드로 값을 가져올 때마다 재정렬을 요하므로 O(n)만큼의 추가적인 시간이 더 소요됩니다.

요소를 큐의 뒤쪽에 추가(push())하고 앞쪽에서 요소를 제거(shift())합니다.

class Queue {
  constructor() {
    this.arr = [];
  }
  
  isEmpty() {
    return this.arr.length === 0;
  }
  
  enqueue(element) {
    this.arr.push(element);
  }
  
  dequeue() {
    if(this.isEmpty()) return "Underflow!😱";
    return this.arr.shift();
  }
  
  front() {
    if(this.isEmpty()) return "큐가 비어있는걸요?🤷🏻‍♀️";
    return this.arr[0];
  }
  
  rear() {
    if(this.isEmpty()) return "큐가 비어있는걸요?🤷🏻‍♀️";
    return this.arr[this.arr.length-1];
  }
}

👉🏻 (구현은 했지만) 아주 간단한 문제가 아니라면 queue를 사용하는 문제에서 배열을 사용하는 것은 시간 초과가 날 확률이 높습니다.

🕶️ 연결리스트로 구현

연결 리스트를 사용해 큐를 구현하면 arr[0]에 접근하여 값을 반환하는 시간을 O(1) 로 해결할 수 있습니다. 배열과 달리 재정렬이 따로 필요 없기 때문에 추가적인 시간이 소요되지 않아 FIFO 원칙을 지키면서 배열보다 빠르게 접근할 수 있습니다.
다만, 연결리스트로 구현할 때 큐에서 처음과 마지막 노드를 갱신할 때를 주의해야 합니다.

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

let front = null, rear = null;

// enqueue() 작업은 뒤쪽에 새 노드를 추가하고 rear를 다음 노드로 이동하면 됩니다.
function enqueue(value) {
  let temp - new Node(value);
  
  if(rear === null) {
    front = rear = temp;
    return;
  }
  
  rear.next = temp;
  rear = temp;
}

// dequeue()는 앞쪽 노드를 제거하고 pront를 다음 노드로 이동합니다.
function dequeue() {
  if(front === null) return;
  
  let temp = front;
  front = front.next;
  
  if(front === null) rear = null;
}

✨🕶️ 객체로 구현

큐를 구현하려면 앞(front)과 뒤(rear)에 두 인덱스를 추적해야 합니다. 이 때 단순히 인덱스를 증가시키며 추적하면 front와 rear에 도달해 문제가 생길 수 있으므로 큐의 최대 크기를 먼저 정의해야 합니다. (➡️ 문제에 대한 근본적 해결책은 원형 큐로 해결할 수 있습니다.)

👀 Reference

NewHa

백 번을 보면 한 가지는 안다 👀

이전 포스트

[ ᴀʟɢᴏʀɪᴛʜᴍ ] Stack ( 스택 )

다음 포스트

[ ᴀʟɢᴏʀɪᴛʜᴍ ] Queue ( 큐 )