원형 큐 (Circular Queue)

구조

원형 큐(Circular Queue)는 보통의 큐의 확장시켜 마지막 요소가 첫 요소에 연결된 형태이다.

 

원형 큐는 보통의 큐의 가장 큰 제약 사항을 해결한다.

 

보통의 큐에서는 push 후 pop을 하면 사용이 불가능한 빈 공간이 생기지만,
원형 큐에서는 큐의 끝에 다다르면 다시 큐의 시작부터 데이터를 삽입한다.

 

https://www.programiz.com/dsa/circular-queue

 

구현 코드

import java.util.Scanner;

public class Main {
    static class Queue {
        private int front = 0;
        private int rear = 0;
        private int size = 0;
        private int[] arr = new int[100];

        public Queue(int size) {
            this.create(size);
        }

        public Queue() {
            this.create(10);
        }

        public void create(int size) {
            this.size = size;
            this.front = 0;
            this.rear = 0;
        }

        public void push(int number) {
            if (size <= rear) {
                System.out.println("Overflow");
            } else {
                arr[rear++] = number;
            }
        }

        public void pop() {
            if (rear <= front) {
                System.out.println("Underflow");
            } else {
                arr[front++] = 0;
            }
        }

        public int front() {
            if (rear <= front) {
                return -1;
            } else {
                return arr[front];
            }
        }

        public int size() {
            return rear - front;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int size = scan.nextInt();
        Queue q = new Queue(size);

        int loopCnt = scan.nextInt();

        for (int i = 0; i < loopCnt; i++) {
            int op = scan.nextInt();
            int number = 0;

            switch (op) {
                case 1:
                    number = scan.nextInt();
                    q.push(number);
                    break;
                case 2:
                    q.pop();
                    break;
                case 3:
                    number = q.front();
                    if (number < 0) System.out.println("NULL");
                    else System.out.println(number);
                    break;
            }
        }
    }
}

 

참고 문서

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 - https://ko.wikipedia.org/wiki/큐_(자료_구조)

Circular Queue Data Structure - https://www.programiz.com/dsa/circular-queue