자료구조(5) - 큐

큐(Queue)란?

큐(queue)는 사전적으로 대기줄이라는 의미로, 먼저 추가한 데이터를 먼저 반환/삭제하는 형태의 자료구조이다.

큐의 특징

• 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO-First In First Out)구조이다.
• 선형과 원형이 존재한다.

---

선형 큐(Linear Queue)와 원형 큐(Circular Queue)

선형 큐(배열 기반 - push, shift 사용)

• enqueue(삽입)
  1. 크기가 5인 배열을 생성
  2. push()로 데이터를 추가
  3. 배열의 앞쪽부터 데이터가 추가됨
• dequeue(삭제)
  1. shift()로 배열의 제일 앞 데이터 제거
  2. 뒤에 이어서 존재하던 데이터들이 앞으로 이동

선형 큐(배열 기반 - front, rear 사용)

• enqueue(삽입)
  1. 크기가 5인 배열을 생성
  2. rear 위치의 인덱스에 데이터 추가
  3. 데이터 추가 후, rear + 1 시켜서 위치 변경
  * front: 원소를 꺼낼 위치, rear: 새로운 원소를 저장할 위치
• dequeue(삭제)
  1. front 위치의 데이터를 제거
  2. 데이터 제거 후, front + 1로 위치 변경

선형 큐(Linear Queue)의 한계
shift()를 사용하여 원소를 삭제한 경우, 뒤에 존재하던 원소들이 앞으로 이동하면서 O(n) 시간 복잡도가 발생한다. 또한, 원소의 경우가 적다면 문제가 크지 않지만 1만개라고 가정한다면 삭제에 따른 원소 이동으로 인해 오버헤드가 발생할 가능성이 있다.
front를 사용하여 원소의 인덱스 위치를 삭제한 경우, 삭제 후 front가 다음 인덱스로 이동하면서 빈 공간이 생기게 된다. 예를 들어, [0]에 빈 공간이 존재하고, 그 이후의 공간에 원소가 전부 존재하는 경우 해당 큐는 가득 찬 것으로 인식되어 빈 공간에 원소를 추가하지 못하게 된다.

위와 같은 문제점을 보완하기 위해 원형 큐라는 개념이 생겨났다.

원형 큐

원형 큐에서 rear와 front값은 식을 이용하여 지정해준다.
queue가 가득 찬 상태인지 확인하기 위한 변수인 count를 선언해준다.
식을 이용하여 조정해주기 때문에 삽입과 삭제가 반복되어도 여유 공간을 활용할 수 있다.

• front = (front + 1) % max
• rear = (rear + 1) % max
• count: enqueue일 경우 +1, dequeue일 경우 -1

* 식은 구현 방법에 따라 달라질 수 있음
1. max가 4인 큐를 만들고, front, rear, count의 값을 0으로 설정
2. enqueue를 실행할 때, rear의 위치에 원소를 추가
3. enqueue가 완료 되었으면, count와 rear 값을 위 식의 결과로 업데이트
rear = (0 + 1) % 4, count = 0 + 1
rear = (1 + 1) % 4, count = 1 + 1
rear = (2 + 1) % 4, count = 2 + 1
rear = (3 + 1) % 4, count = 3 + 1
1. dequeue를 실행할 때, front 위치의 원소를 삭제 및 반환
2. dequeue가 완료 되었으면, count와 front 값을 위 식의 결과로 업데이트
front = (0 + 1) % 4, count = 4 - 1
front = (1 + 1) % 4, count = 3 - 1
rear = (0 + 1) % 4, count = 2 + 1

---

예제

기본 연산
JavaScript에는 큐와 관련된 내장 라이브러리가 없기 때문에, 큐 자료구조를 직접 구현해야 한다. 다른 언어에서는 Java의 java.util.Queue나 Python의 collections.deque와 같은 큐 자료구조를 제공하는 내장 라이브러리가 있어 쉽게 사용할 수 있다.

큐를 구현하는 방법에는 배열 기반 선형 큐, 연결 리스트 기반 선형 큐, 그리고 원형 큐가 있다. 각 구현 방식에 따라 front와 rear의 초기값을 설정하는 방식이 달라질 수 있으며, 이는 주로 구현 방법과 사용자 선호에 따라 결정된다.

front와 rear의 개념은 여러 방식으로 이해될 수 있다.

• 맨 앞의 원소, 맨 뒤의 원소를 나타내는 지점.
• 데이터를 꺼낼 위치(front)와 데이터를 추가할 위치(rear)를 나타내는 지점.

아래는 JavaScript로 작성된 큐 구현 예제이다. 이 예제에서 front와 rear의 초기값은 0으로 설정되었다. front는 큐에서 데이터를 꺼낼 위치를, rear는 데이터를 추가할 위치를 나타낸다.

선형 큐(배열을 이용한 큐)

• 연산 구현

  class ArrayLinearQueue {
      constructor(maxSize = 5) {
          this.queue = [];
          this.maxSize = maxSize;
      }
  
      enqueue(item) {
          if (this.isFull()) {
              console.log("Queue is full");
              return;
          }
          this.queue.push(item); 
          console.log(`Enqueued: ${item}`);
      }
  
      dequeue() {
          if (this.isEmpty()) {
              console.log("Queue is empty");
              return null;
          }
          const item = this.queue.shift();
          console.log(`Dequeued: ${item}`);
          return item;
      }
  
      peek() {
          if (this.isEmpty()) {
              console.log("Queue is empty");
              return null;
          }
          return this.queue[0];
      }
  
      size() {
        	return this.queue.length;
      }
  
      isEmpty() {
        	return this.queue.length === 0;
      }
  
      isFull() {
        	return this.queue.length >= this.maxSize;
      }
  }

• 사용 예시

  const queue = new ArrayLinearQueue();
  //
  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);
  queue.enqueue(40);
  queue.enqueue(50);
  queue.enqueue(60);  // Queue is full
  //
  console.log(`Peek: ${queue.peek()}`);  // Peek: 10
  console.log(`Size: ${queue.size()}`);  // Size: 5
  console.log(`Is empty: ${queue.isEmpty()}`);  // Is empty: false
  console.log(`Is full: ${queue.isFull()}`);  // Is full: true
  //
  queue.dequeue();
  queue.dequeue();
  console.log(`Peek after dequeue: ${queue.peek()}`);  // Peek after dequeue: 30
  console.log(`Size after dequeue: ${queue.size()}`);  // Size after dequeue: 3

원형 큐

• 연산 구현

  class CircularQueue {
      constructor(maxSize = 5) {
          this.queue = new Array(maxSize);
          this.maxSize = maxSize;
          this.front = 0;  // 데이터 꺼낼 위치
          this.rear = 0;   // 데이터 추가할 위치
          this.count = 0;  // 큐에 있는 원소 개수
      }
  
      enqueue(item) {
          if (this.isFull()) {
              console.log("Queue is full");
              return;
          }
          this.queue[this.rear] = item;
          this.rear = (this.rear + 1) % this.maxSize;  // rear 위치를 순환
          this.count++;
          console.log(`Enqueued: ${item}`);
      }
  
      dequeue() {
          if (this.isEmpty()) {
              console.log("Queue is empty");
              return null;
          }
          const item = this.queue[this.front];
          this.queue[this.front] = undefined;  // 큐에서 원소 제거
          this.front = (this.front + 1) % this.maxSize;  // front 위치를 순환
          this.count--;
          console.log(`Dequeued: ${item}`);
          return item;
      }
  
      peek() {
          if (this.isEmpty()) {
              console.log("Queue is empty");
              return null;
          }
          return this.queue[this.front];
      }
  
      size() {
          return this.count;
      }
  
      isEmpty() {
          return this.count === 0;
      }
  
      isFull() {
          return this.count === this.maxSize;
      }
  }

• 사용 예시

  const queue = new CircularQueue();
  //
  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);
  queue.enqueue(40);
  queue.enqueue(50);
  queue.enqueue(60);  // Queue is full
  //
  console.log(`Peek: ${queue.peek()}`);  // Peek: 10
  console.log(`Size: ${queue.size()}`);  // Size: 5
  console.log(`Is empty: ${queue.isEmpty()}`);  // Is empty: false
  console.log(`Is full: ${queue.isFull()}`);  // Is full: true
  //
  queue.dequeue();
  queue.dequeue();
  console.log(`Peek after dequeue: ${queue.peek()}`);  // Peek after dequeue: 30
  console.log(`Size after dequeue: ${queue.size()}`);  // Size after dequeue: 3

배열 기반 선형 큐는 데이터 제거 시 배열의 첫 번째 원소를 제거하기 위해 shift 메서드를 사용한다. 이 메서드는 첫 번째 원소를 제거한 후 모든 원소를 앞으로 한 칸씩 이동시키기 때문에 O(n)의 시간 복잡도를 가지며, 성능 저하와 오버헤드를 초래한다.
또한, front와 rear 포인터를 사용해 배열의 인덱스를 이동시키며 큐를 관리하는 방식을 사용할 수도 있는데, 이 경우 삭제된 원소의 공간을 재사용하지 못해 메모리 낭비가 발생할 수 있다.

원형 큐는 고정된 크기의 배열을 사용하여 큐의 크기를 제한하고, front와 rear 포인터를 사용하여 원형 구조로 큐를 관리한다. 이 방식은 큐의 크기가 고정되어 있어 큐가 가득 차면 더 이상 원소를 추가할 수 없는 문제가 발생한다. 즉, 초기 설정한 크기보다 많은 데이터를 처리할 수 없어 유연성이 떨어진다.

반면에, 연결 리스트 기반 선형 큐는 큐의 크기에 제한이 없어 데이터 양의 변화에 유연하게 대응할 수 있다. 또한, enqueue, dequeue 연산에서 노드의 포인터만 변경하면 되기 때문에 원소 이동과 같은 성능 문제가 없다. 마지막으로, 연결 리스트는 노드가 필요한 경우에만 메모리를 사용하므로 메모리 낭비가 없다.

따라서, 배열 기반 선형 큐와 원형 큐의 단점은 연결 리스트 기반 선형 큐로 보완할 수 있다.

선형 큐(단일 연결 리스트를 이용한 큐)

• 연산 구현

  class Node {
      constructor(data) {
        this.data = data;
        this.next = null;
      }
  }
  class LinkedListLinearQueue {
      constructor() {
          this.front = null;
          this.rear = null;
          this.count = 0; // size를 count로 변경
      }
  
      enqueue(data) {
          const newNode = new Node(data);
  
          if (this.isEmpty()) this.front = newNode;
          else this.rear.next = newNode;
  
          this.rear = newNode;
          this.count++; // count 증가
      }
  
      dequeue() {
          if (this.isEmpty()) return null;
  
          const dequeuedData = this.front.data;
          this.front = this.front.next;
          this.count--; // count 감소
  
          if (this.isEmpty()) this.rear = null;
  
          return dequeuedData;
      }
  
      peek() {
          if (this.isEmpty()) return null;
          return this.front.data;
      }
  
      size() {
          return this.count;
      }
  
      isEmpty() {
          return this.count === 0;
      }
  
      isFull() {
          // 큐의 크기 제한이 없으므로 항상 false 반환
          return false;
      }
  }

• 사용 예시

  const queue = new LinkedListLinearQueue();
  //
  console.log(queue.isEmpty()); // true
  //
  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);
  //
  console.log(queue.peek()); // 10
  console.log(queue.size()); // 3
  //
  console.log(queue.dequeue()); // 10
  console.log(queue.peek()); // 20
  console.log(queue.size()); // 2
  //
  console.log(queue.isEmpty()); // false
  //
  console.log(queue.dequeue()); // 20
  console.log(queue.dequeue()); // 30
  console.log(queue.isEmpty()); // true
  //
  console.log(queue.dequeue()); // null (큐가 비어있음)

연결리스트 기반 선형 큐는 배열 기반 선형 큐와 원형 큐의 단점을 보완해주지만, 단점도 존재한다.
첫 번째로, 노드에는 데이터와 포인터가 존재하기 때문에 배열 기반보다 메모리 사용량이 많다. 두 번째로, 원소를 삽입할 때마다 새로운 노드를 할당하고, 제거할 때는 노드를 해제해야한다. 이러한 동적 메모리 할당과 해제는 오버헤드를 발생시킬 수 있다. 마지막으로 배열 기반 큐에 비해 구현이 복잡하다.

배열 기반 선형 큐, 연결 리스트 선형 큐, 원형 큐는 각 장단점이 존재하기 때문에 상황에 맞게 선택하여 사용하는 것이 중요하다.

---

시간 복잡도

---

큐 사용 예시

• 주문 처리
• 프린터 작업 관리
• 프로세스 스케줄링
• 데이터 스트리밍
• 티켓 시스템
  
  

요약
큐(Queue)는 선입선출(FIFO: First In, First Out) 방식의 자료구조로, 먼저 들어간 데이터가 먼저 나오는 구조를 가진다. 큐의 기본 연산에는 요소를 추가하는 enqueue, 요소를 제거하는 dequeue, 맨 앞의 요소를 확인하는 peek, 큐의 크기를 반환하는 size, 큐가 비어있는지 확인하는 isEmpty, 큐가 가득 찼는지 확인하는 isFull이 있다.

큐는 배열 또는 연결 리스트를 이용해 구현할 수 있으며, 공간 낭비를 줄이기 위해 원형 큐를 사용할 수 있다. 배열을 이용한 큐는 고정 크기의 배열을 사용하여 빠른 액세스를 제공하지만, 공간 낭비와 크기 한계가 존재힌다. 연결 리스트를 이용한 큐는 동적 메모리 할당을 통해 크기 제약이 없고 효율적인 삽입과 삭제가 가능하지만, 추가 메모리 오버헤드가 발생할 수 있다. 원형 큐는 배열의 순환 구조를 이용하여 공간 낭비를 최소화하고 효율적인 크기 관리가 가능하다.

큐는 주문 처리, 프린터 작업 관리, 프로세스 스케줄링, 데이터 스트리밍, 티켓 시스템 등 다양한 실세계 문제를 해결하는 데 사용된다. 큐의 사용은 데이터의 순서와 효율적인 처리가 중요한 상황에서 특히 유용하다.

[참고 자료]

https://velog.io/@hysong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue
https://oh-potato.tistory.com/6