큐(Queue)

Queue

선입선출(First In First Out; FIFO)의 자료구조로 대기열이라고도 한다

가장 먼저 들어온 데이터가 가장 먼저 나가는 구조

삽입은 맨 뒤에서만 이루어지고, 삭제는 맨 앞에서만 이루어지는 구조, 중간에 끼워넣기 X

 

Queue 용어

• enqueue(data) : 큐의 맨뒤에 데이터 삽입
• dequeue: 큐의 맨앞 데이터 삭제 및 반환
• front : 큐의 맨앞 데이터
• rear(back): 큐 맨뒤 데이터
• size: 큐 크기
• 가득찬 큐에 데이터를 삽입하려고 시도하면 overflow, 빈 큐에서 데이터를 삭제하려고 시도하면 underflow 발생

 

Queue 구현

Java에서 큐는 array나 LinkedList로 구현할 수 있음, 각자 장단점이 다름

 

1) Array로 구현

배열로 구현 시 구현은 쉽지만, 크기가 동적이지 못하다. 

배열을 선언할 때 크기를 지정해줘야하기 때문에 크기를 런타임에 바꿀 수 없다. front와 rear를 관리해줘야한다. 

public class ArrayQueue{
    int[] queue;
    int front;
    int rear;
    int size;

    public ArrayQueue(int size){
        queue = new int[size];
        this.size = size;
        this.front = 0;
        this.rear = -1;
    }
    public void enqueue(int data){
        if(isFull()){
           //overflow...
        }else{
            queue[++rear] = data;
            size++;
        }
    }
    
    public int dequeue(){
        if(isEmpty()){
            //underflow...
            return -1;
        }else{
            size--;
            return queue[front++];
        }
    }
    public boolean isFull(){
        return rear == size;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
}

 

2) Linked List로 구현

 

Queue<Integer> queue = new LinkedList<>();

위처럼 선언하여 사용할 수 있다. 연결 리스트를 사용하면 큐 사이즈를 동적으로 관리할 수 있고, 삽입 및 삭제 연산 등은 LinkedList에 내장 함수를 사용하면 된다. 

 

enqueue 연산은 add나 offer 함수를 사용하면 된다.

//enqueue
queue.add(1); 
queue.offer(2); 

 

dequeue 연산은 poll이나 remove 함수를 사용하면 된다.

//dequeue
queue.poll();
queue.remove();

 

그 외의 isEmpty나 검사 함수는 아래와 같다. 

queue.isEmpty(); //queue가 비어있는지 확인
queue.element(); //queue의 front 원소 반환, queue가 비어있으면 excetion 반한
queue.peek(); //queue의 front 원소 반환, queue가 비어있으면 null 반환