[자료 구조] Queue란?

1. Linear Queue(선형 큐)란?

• FIFO(First In First Out)
• en-queue:  큐에 데이터를 넣는 작업 -- O(1)
• de-queue: 큐에서 데이터를 꺼내는 작업 -- O(n)
• 데이터가 나오는 쪽은 front, 데이터를 넣는 쪽은 rear라고 한다.

1.1 선형 큐의 단점

• 큐에 데이터가 꽉 찼다면 데이터를 추가할 수 없다.
• de-queue시 요소를 하나씩 앞으로 옮겨야 하므로 복잡도가 O(n)이다.

2. Ring Buffer(Circular Queue)란?

이미지 출처: https://camera-sdk.com/attachments/6554/circular-buffer-video-recording.jpg

• 원형큐는 배열의 맨 뒤가 맨 앞과 연결되었다고 보며 선형 큐의 문제점을 보완하기 위한 자료구조이다.
• 선형큐와 다르게 de-queue시, 배열 요소를 앞으로 옮기지 않아도 된다. enqueue시 rear 인덱스에 값을 저장하고 rear를 1 증가시킨다. dequeue시 front 인덱스의 값을 꺼내고 front를 1 증가시킨다. -- O(1)
• front: 논리적인 맨 앞 요소의 인덱스 
• rear: 논리적인 맨 뒤 요소 하나 뒤의 인덱스 (다음 요소를 인큐할 위치의 인덱스)
• 원형 큐는 오래된 데이터를 버리는 용도로 사용할 수 있다. 예를 들면 사이즈가 n인 배열에 계속 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버릴 수 있다. 

2.1 원형 큐 직접 만들기

public class IntQueue {
  private int[] queue; // 큐 배열
  private int capacity; // 큐의 용량
  private int front; // 맨 앞 요소
  private int rear; // 맨 끝 요소
  private int num; // 현재 데이터 개수
  
  // 실행 시 예외: 큐가 빈 경우
  public class EmptyIntQueueException extends RuntimeException {
    public EmptyIntQueueException() {};
  }
  
  // 실행 시 예외: 큐가 가득 찬 경우
  public class OverflowIntQueueException extends RuntimeException {
    public OverflowIntQueueException() {};
  }
  
  public IntQueue(int maxlen) {
    this.num = this.front = this.rear = 0;
  	this.capacity = maxlen;
    try {
      queue = new int[this.capacity];
    } catch(OutOfMemoryError e) {
      this.capacity = 0;
    }
  }
  
  public int enque(int x) throws OverflowIntQueueException {
    if(this.num >= this.capacity) {
      throw new OverflowIntQueueException();
    }
    this.queue[this.rear++];
    this.num++;
    
    if(this.rear == this.capacity) {
      // rear값이 capacity와 같아지는 것 방지
      this.rear = 0;
    }
    return x;
  }
  
  public int deque() throws EmptyIntQueueException {
    if(this.num <= 0) {
      throw new EmptyIntQueueException();
    }
    int x = this.queue[this.front++];
    this.num--;
    
    if(this.front == this.capacity) {
      // front값이 capacity와 같아지는 것 방지
      this.front = 0; 
    }
    return x;
  }
  
  public int peek() throws EmptyIntQueueException {
    if(this.num <= 0) {
      throw new EmptyIntQueueException();
    }
    return this.queue[this.front];
  }
  
  public void clear() {
    this.num = this.front = this.rear = 0;
  }
  
  public int indexOf(int x) {
    // front에서 rear쪽으로 선형 검색
    for(int i = 0; i < num; i++) {
      int idx = (i + this.front) % this.capacity;
      if(this.queue[idx] == x) {
       return idx;
      }
    }
    return -1;
  }
  
  public int getCapacity() {
    return this.capacity;
  }
  
  public int size() {
    return this.size;
  }
  
  public boolean isEmpty() {
  	return this.num <= 0;
  }
  
  public boolean isFull() {
  	return this.num >= this.capacity;
  }
}