ring 방식 int queue 자바 구현 코드

 

 

자료구조 중 하나인 queue를 ring 방식으로 구현한 코드이다.

 

이 코드에서 front와 rear 변수는 큐의 원소들이 저장된 배열에서 현재 프런트(front)와 리어(rear)의 위치를 나타낸다.

- front: 큐에서 가장 앞에 있는 원소의 인덱스를 가리킨다. deque() 연산이 발생하면 front 값이 증가한다. 즉 한 칸씩 이동한다.

- rear: 큐에서 가장 뒤에 있는 원소의 다음 위치를 가리킨다. enque() 연산이 발생하면 rear는 값이 증가한다. 즉 한 칸씩 이동한다.

 

1. 인큐(enqueue()) 연산: 

rear 인덱스가 큐의 맨 뒤에 위치하고 있는 상태에서 인큐가 발생하면 rear는 배열의 처음으로 되돌아간다. 이렇게 하면 배열의 처음부터 빈 공간이 있을 때까지 데이터를 저장할 수 있다. 이는 큐를 원형 구조로 만들어 용량을 최대로 활용하는 것이다.

 

예를 들어, rear이 배열의 마지막 인덱스에 도달하면 인큐 연산 발생 시 rear은 0으로 초기화된다. 이렇게 하여 다음 인큐가 발생하면 0부터 데이터를 저장할 수 있도록 한다.

 

2. 디큐(dequeue())연산: 

front 인덱스는 디큐 연산이 발생할 때마다 한 칸씩 이동한다. 이렇게 하여 가장 오래된 데이터가 큐에서 제거되고 front는 다음 요소를 가리키게 된다. 즉, 큐의 특성인 FIFO 로직을 수행한다. 

디큐 연산으로 인해 front가 배열의 마지막 인덱스에 도달하면 front는 0으로 초기화된다. 이렇게 하면 다음 디큐가 발생하면 0부터 요소를 제거할 수 있다.

 

 

이와 같이 front와 rear 변수를 조정하여 큐의 원형 구조를 유지하면서 데이터를 관리한다.

package datastructure.queue.intringqueue;

public class IntQueue {
   private int max;
   private int front;
   private int rear;
   private int currentCounts;
   private int[] queue;

   public IntQueue(int capacity) {
      currentCounts = 0;
      front = 0;
      rear = 0;
      this.max = capacity;

      try {
         queue = new int[max];
      } catch (OutOfMemoryError e) {
         max = 0;
      }
   }

   /**
    * 큐에 데이터를 인큐한다. 인큐에 성공하면 인큐한 값을 그대로 반한한다. 그러나 큐가 가득차서 인큐할 수 없다면 예외를 던진다.
    *
    * 인큐하기 전의 rear 값이 배열의 끝 값이라면 이후의 reqr 값이 배열의 마지막 요소를 초과하여 가리키 않도록 rear의 값이 max와 같아지면 그 다음 순번은 배열의 처음인 0으로 변경해준다.
    * @param value
    * @return
    */
   public int enque(int value) {
      if (currentCounts >= max) {
         throw new IllegalStateException("큐가 가득 찼습니다");
      }
      queue[rear++] = value;
      currentCounts++;

      if (rear == max) {
         rear = 0;
      }
      return value;
   }

   /**
    * 큐에서 데이터를 디큐하고 그 값을 반환한다. 큐가 비어있으면 예외를 던진다.
    *
    * 디큐 하기 전의 front 값이 배열의 끝 값이라면 이후의 front 값이 배열의 마지막 요소를 초과하여 가리키지 않도록 front의 값이 max와 같아지면 그 다음 순번은 배열의 0으로 변경해준다.
    * @return
    */
   public int deque(){
      if (currentCounts<=0){
         throw new IllegalStateException("큐가 비어 있습니다");
      }
      int value = queue[front++];
      currentCounts--;

      if (front==max){
         front =0;
      }
      return value;
   }

   public int peek(){
      if (currentCounts<=0){
         throw  new IllegalStateException("큐가 비어 있습니다");
      }
      return queue[front];
   }

   /**
    * 큐의 배열에서 value 값이 저장되어 있는 위치를 알아낸다.
    *
    * front에서 rear로 선형 탐색을 수행한다. 스캔의 시작은 배열의 첫 요소가 아니라 큐의 첫 요소, 즉 프런트이다.
    * 따라서 idx의 계산은 (i + front) % max이다.
    * @param value
    * @return
    */

   public int indexOf(int value){
      for (int i =0; i< currentCounts; i++){
         int idx = (i + front) % max;
         if (queue[idx] == value){
            return idx;
         }
      }
      return -1;
   }

   public void clear(){
      currentCounts = 0;
      front =0;
      rear=0;
   }

   public int capacity(){
      return max;
   }

   public int size(){
      return currentCounts;
   }

   public boolean isEmpty(){
      return currentCounts<=0;
   }

   public boolean isFull(){
      return currentCounts>=max;
   }


   public void dump(){
      if (currentCounts<=0){
         throw new IllegalStateException("큐가 비어 있습니다");
      }

      for (int i =0; i< currentCounts;i++){
         System.out.println(queue[(i + front) % max]);
      }
   }



}

 

package datastructure.queue.intringqueue;

public class IntQueueMain {
    public static void main(String[] args) {
        IntQueue queue = new IntQueue(5); // 용량(capacity)이 5인 큐 생성

        // 큐에 값 추가
        queue.enque(1);
        queue.enque(2);
        queue.enque(3);
        queue.enque(4);
        queue.enque(5);

        System.out.println("큐의 크기: " + queue.size()); // 큐의 크기 출력: 5
        System.out.println("큐가 가득 찼는가? " + queue.isFull()); // 큐가 가득 찼는지 여부 출력: true

        System.out.println("큐의 맨 앞 요소: " + queue.peek()); // 큐의 맨 앞 요소 확인: 1


        int removedValue = queue.deque();         // 큐에서 값 제거
        System.out.println("제거한 값: " + removedValue); // 제거된 값 출력: 1

        System.out.println("큐의 크기: " + queue.size()); // 큐의 크기 출력: 4

        // 큐 비우기
        queue.clear();
        System.out.println("큐의 크기: " + queue.size()); // 큐의 크기 출력: 0
        System.out.println("큐가 비었는가? " + queue.isEmpty()); // 큐가 비어 있는지 여부 출력: true
    }
}