큐(Queue) - 배열

사회적 거리두기 줄서기

요즘 위 이미지와 같이 거리두면서 줄 잘 서고 계신가요? ㅎㅎ

줄 잘서는 자료구조 큐(Queue)를 해보겠습니다! ㅋㅋ

 

큐(Queue) 는 선입선출(FIFO : First In First Out)구조로 선형자료구조에 해당합니다. 

스택과 같이 가장 기본이 되는 자료구조입니다. 

스택은 넣고 꺼내는 입구가 하나였다면, 큐는 넣는 곳 빼는곳이 각각 따로 있습니다. 

큐(Queue)

큐에 넣는것을 enqueue 큐에서 꺼내는 것을 dequeue 라고 합니다. 

 

큐를 한번 그림으로 설명 해볼께요

 

우선, front와 rear 변수를 선언합니다. 이는 현재 queue의 상태를 확인 할때 사용합니다.

front는 맨 앞, rear는 맨뒤라고 생각하시면 됩니다.

 

맨 처음 큐가 비었기 때문에 front와 rear 가 idx -1 을 가르킵니다. 

front와 rear 값이 같습니다. 이것으로 비었다고 판단을 합니다. 

 

값을 추가했을때 (enqueue) 했을때 rear 값이 하나 증가하여 맨뒤인 idx 0 값을 가리킵니다. 

Queue is Full!!

같은 방식으로 값을 두번 추가 하면 큐가 꽉 차게 됩니다. 

이때 front와 rear 값을 확인 해보니, front는 맨 앞 rear는 맨뒤이고 max_size -1 값과  같게 됩니다. 

Dequeue

값을 하나 빼봅니다. queue는 먼저 들어간 아이 부터 나오도록 구현 하기 위해 front+1 위치의 값을 뺍니다.

다 빼개 되면 처음과 같이 front == rear 상태가 됩니다.

 

큐는 배열, 노드 두가지로 구현 할 수 있습니다. 우선 배열로 구현해보겠습니다.

0. 선언

public class Queue {
    int [] QUEUE = null;
    int FRONT;
    int REAR;
    int MAX_SIZE;

    public Queue(int size){
        QUEUE = new int[size];
        FRONT = -1;
        REAR = -1;
        MAX_SIZE = size;

    }
}

 

1. enqueue

    /**
     * enqueue
     *
     * @param value
     * @return
     */
    int enqueue(int value){
        if(REAR == MAX_SIZE-1){
            return -1;
        }


        QUEUE[++REAR] = value;
        return 0;
    }

 

2. dequeue

    /**
     * deqeueue
     *
     * @return
     */
    int dequeue(){
        if(FRONT == REAR){
            return -1;
        }

        return QUEUE[++FRONT];
    }

 

3. 전체

public class Queue {
    int [] QUEUE = null;
    int FRONT;
    int REAR;
    int MAX_SIZE;

    public Queue(int size){
        QUEUE = new int[size];
        FRONT = -1;
        REAR = -1;
        MAX_SIZE = size;

    }

    /**
     * enqueue
     *
     * @param value
     * @return
     */
    int enqueue(int value){
        if(isFull()){
            return -1;
        }


        QUEUE[++REAR] = value;
        return 0;
    }

    /**
     * deqeueue
     *
     * @return
     */
    int dequeue(){
        if(isEmpty()){
            return -1;
        }

        return QUEUE[++FRONT];
    }

    /**
     * isEmpty
     *
     * @return
     */
    boolean isEmpty(){
        if(FRONT == REAR){
            return true;
        }
        return false;
    }

    /**
     * isFull
     * @return
     */
    boolean isFull(){
        if(REAR == MAX_SIZE-1){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        Queue queue = new Queue(10);

        for(int i = 12 ; i >0 ; i--){
            if(!queue.isFull())
                queue.enqueue(i);
            else
                System.out.println("Queue is Full !!");
        }



        System.out.println("-- Queue Confirm --");

        for(int i = 0 ; i < queue.MAX_SIZE ; i++){
            System.out.println(queue.QUEUE[i]);
        }

        System.out.println("-- Queue Confirm End  --");


        for(int i = 12 ; i >0 ; i--){
            if(!queue.isEmpty())
                System.out.println(queue.dequeue());
            else
                System.out.println("Queue is Empty !!");
        }
    }

}