[JAVA] Queue 란 ? Queue 구현해보기

Queue

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다

 

Queue 의 구조

 

queue 의 기본적인 구조는 위와 같지만 종류는 크게 2가지로 나뉜다.

 

1. 선형 Queue

 

일반 line 처럼 처음과 끝이 이어져 있지 않기 때문에 데이터를 꺼낼때마다 정렬을 하거나 , 배열의 크기를 증가시켜야 하기 때문에 효율적이지 않다.

 

구현class

public class Queue {
    private int[] queueList;
    private int pollPointer;
    private int addPointer;
    private int size;

    public Queue(int size) {
        this.queueList = new int[size];
        this.size = size;
        this.pollPointer=0;
        this.addPointer = -1;
    }

    public void add(int value){
        if(addPointer == size-1){
            System.out.println("더 이상 추가 할 수 없음");
        }else {
            queueList[++addPointer] = value;
        }
    }

    public int poll(){
        if(addPointer==-1){
            System.out.println("요소가 존재하지 않습니다.");
            return 0;
        }
        addPointer--;
        int result = queueList[pollPointer];

        // 요소를 꺼내고 앞으로 정렬하는 작업
        // 요소가 많아지면 효율이 떨어짐
        for (int i = 0; i < queueList.length-1; i++) {
            queueList[i] = queueList[i+1];
        }
        return result;
    }
}

참고: www.geeksforgeeks.org/array-implementation-of-queue-simple/

 

 

---

2. 원형 Queue

-  선형 Queue 의 단점을 보완 하기위해 생김

- 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둔다.

원형 Queue

구현class

public class Queue {
    private int[] queueList;
    private int pollPointer;
    private int addPointer;
    private int size;

    public Queue(int size) {
    	//배열의 공간하나를 못쓰기 때문에 인자로 받은 size에서 +1 을 진행함
        this.queueList = new int[size+1];
        this.size = size+1;
        this.pollPointer = 0;
        this.addPointer = 0;
    }
    public boolean isFull(){
        if(((addPointer+1)%size==pollPointer)){
            return true;
        }else {
            return false;
        }
    }
    public void add(int value){
        if(isFull()){
            System.out.println("더 이상 추가 할 수 없음");
        }else {
            addPointer = (++addPointer)%size;
            queueList[addPointer] = value;
        }
    }

    public int poll(){
        if(addPointer==pollPointer){
            System.out.println("요소가 존재하지 않습니다.");
            return 0;
        }
         pollPointer = (++pollPointer) % size;

        return queueList[pollPointer];
    }
}

 

참고: www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html