선형 자료구조 - 4. 큐

큐 (Queue)

큐란 선입선출(First In, First Out) 의 특징을 가진 자료구조를 의미합니다.

 

선입선출이란 먼저 들어온 데이터가 먼저 나가는 구조를 뜻합니다.

 

보통, 입력한 순서대로 데이터를 처리할 필요가 있을 경우 사용합니다.

 

 

큐의 구조

출처 : https://galid1.tistory.com/483

 

큐에선 데이터가 한쪽으로 들어와서 한쪽으로 나가게 됩니다.

데이터가 들어오는 위치를 Rear or Back , 데이터가 나가는 위치를 Front라고 합니다.

 

큐에 데이터를 넣는 연산을 Enqueue, 큐에서 데이터를 꺼내는 연산을 Dequeue라고 합니다.

 

 

큐의 종류

큐에는 특수한 형태의 큐들이 존재하는데, 원형 큐, 우선순위 큐, 데크 등이 이에 해당합니다.

 

 

원형 큐

선형 큐에서 Dequeue연산할 경우, 값을 앞으로 재배치

선형 큐의 경우, Dequeue 연산을 하게되면 빈 부분이 생기게 되는데, 공백을 없애기 위해 모든 값들을 다시 Front쪽으로 채워주는 재배치 작업이 필요합니다.

큐 안에 있는 모든 데이터들을 이동시켜야 하다보니 성능이 좋지 않은데, 이를 해결하기 위해 나온 것이 원형 큐 입니다.

 

원형 큐 , 출처 : 파이썬 알고리즘 인터뷰

원형 큐는 포인터 두개가 계속해서 움직여 Front와 Rear를 조정해주는 구조를 가지고 있습니다. 이러한 구조를 통해 원형 구조를 만들게 되는데, 이는 데이터들을 재배치하지 않아도 되는 이점이 있습니다.

 

 

 

우선순위 큐  및 데크

우선순위 큐는 원소들에게 우선순위를 매겨 입력된 순서와 상관없이 우선순위가 높은 원소부터 꺼내는 자료구조를 뜻합니다.

 

데크는 양쪽 모두에서 넣기와 빼기가 가능한 스택과 큐의 특징을 모두 가진 자료구조를 뜻합니다. 

 

우선순위 큐와 데크는 해당 자료구조를 다룰 때 자세하게 다루도록 하겠습니다.

 

 

프로그래밍 언어로 구현

Java

자바에서는 Queue 자료구조를 다음과 같이 제공하고 있습니다.

Queue queue = new LinkedList(); // ArrayDeque를 구현체로 사용할 수도 있습니다.

queue.add(1);  // 값 넣기

queue.poll();  // 값 꺼내기

 

아래의 코드는 배열로 구현한 간단한 원형 큐입니다.

// 원형 큐
public class ExampleQueue {
   int[] arr;
   int front;
   int rear;

   public ExampleQueue(int size) {
      this.arr = new int[size + 1];
   }

   public boolean isEmpty() {
      return this.rear == this.front;
   }

   public boolean isFull() {
      return (this.rear + 1) % this.arr.length == this.front;
   }

   public void enqueue(int data) {
      if (isFull()) {
         System.out.println("큐가 가득 찼습니다.");
         return;
      }

      this.rear = (this.rear + 1) % this.arr.length;

      this.arr[this.rear] = data;
   }

   public Integer dequeue() {
      if (isEmpty()) {
         System.out.println("큐가 비어있습니다.");
         return null;
      }

      this.front = (this.front + 1) % this.arr.length;

      return this.arr[this.front];
   }
}