[알고리즘] JAVA 큐(Queue) 알고리즘

  

 

- FIFO(First-In-First-Out) 선입선출 구조 (먼저 들어간 것이 먼저 나간다)

- 대표적인 예 : 은행 창구(먼저 번호표 뽑은 사람이 먼저 서비스를 받음)

 

자바로 구현한 소스 코드

package com.company;

interface Queue {
    boolean isEmpty();
    boolean isFull();
    void enqueue(char item);
    char dequeue();
    char peek();
    void clear();
}

class Main implements Queue{

    private int front;
    private int rear;
    private int queueSize;
    private char queueArr[];

    public Main(int queueSize) {
        front = -1; // front 초기화
        rear = -1;
        this.queueSize = queueSize; // queue사이즈 설정
        queueArr = new char[this.queueSize]; // 큐 배열 설정
    }

    @Override
    public boolean isEmpty() {
        // front, rear가 같으면 데이터가 없는 상태이므로 모두 -1로 초기화
        if(front == rear) {
            front = -1;
            rear = -1;
        }
        // front, rear가 같은 경우 데이터가 없는 상태이므로 true, 아닌 경우 false;
        return (front == rear);
    }

    @Override
    public boolean isFull() {
        // rear 포인터가 큐의 마지막 원소와 동일한 경우 true 아닌 경우 false;
        return (rear == this.queueSize-1);
    }

    // 큐에 데이터 삽입
    @Override
    public void enqueue(char item) {
        if(isFull()) {
            System.out.println("큐가 꽉 찼습니다.");
        } else {
            queueArr[++rear] = item; // 다음 rear 포인터가 가리키는 위치에 데이터를 추가
            System.out.println("삽입된 데이터 : " + item);
        }
    }

    @Override
    public char dequeue() {
        if(isEmpty()) {
            System.out.println("큐가 비었습니다.");
            return 0;
        } else {
            System.out.println("삭제된 아이템 : " + queueArr[front+1]);
            front = (front+1) % this.queueSize;
            return queueArr[front];
        }
    }

    @Override
    public char peek() {
        if(isEmpty()) {
            System.out.println("큐가 비었습니다.");
            return 0;
        } else {
            System.out.println("peek에 있는 아이템 : " + queueArr[front+1]);
            return queueArr[front+1];
        }
    }

    @Override
    public void clear() {
        if(isEmpty()) {
            System.out.println("큐가 비었습니다.");
        } else {
            front = -1;
            rear = -1;
            queueArr = new char[this.queueSize]; //새로운 큐 배열 생성
            System.out.println("큐 초기화 완료");
        }
    }

    // 큐에 저장된 모든 데이터 출력
    public void printQueue() {
        if(isEmpty()) {
            System.out.println("큐가 비었습니다.");
        } else {
            for(int i=front+1; i<=rear; i++) {
                System.out.println(queueArr[i] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        int queueSize = 5;
        Main arrQueue = new Main(queueSize);

        arrQueue.enqueue('A');
        arrQueue.printQueue();

        arrQueue.enqueue('B');
        arrQueue.printQueue();

        arrQueue.enqueue('C');
        arrQueue.printQueue();

        arrQueue.enqueue('D');
        arrQueue.printQueue();

        arrQueue.enqueue('E');
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.dequeue();
        arrQueue.printQueue();

        arrQueue.peek();
        arrQueue.printQueue();

        arrQueue.clear();
        arrQueue.printQueue();
    }
}

 

출력 결과