for Programming study

큐(Queue)

22 Jun 2020 | DataStructure soongsil SSU

이 포스팅은 숭실대학교 컴퓨터학부 신용태 교수님의 자료구조 수업을 기반으로 작성되었습니다.

큐(Queue)란

LIFO 구조를 가지는 Stack과 다르게 Queue는 FIFO(First In, First Out)구조입니다.
즉 먼저 들어간 데이터가 먼저 나오는 식으로 동작합니다.
일반적으로 실생활속 대기줄을 생각하시면 됩니다.
Stack에서는 데이터 삽입, 삭제를 push, pop이라고 하는데
Queue는 Rear에 데이터 삽입하는것을 Enqueue, Front에서 데이터 삭제를 하는것을 Dequeue라고 합니다.
간단한 그림으로 표현하면 다음과 같습니다. queue

큐(Queue)의 종류

큐의 종류는 크게 아래의 3가지 종류입니다.

  • 선형 큐(Linear Queue) : 선형큐는 가장 일반적인 형태의 큐로 일반적인 배열 형태로 막대 모양을 하고 있다.
    크기가 제한되어 있고 빈 공간을 사용하려면 데이터의 위치를 재배치해야 하는 단점이 있다.
  • 원형 큐(Circular Queue) : 원형큐는 선형큐의 단점을 보완하고자 만들어졌는데, 만약 Rear의 위치가 배열의
    마지막에 위치하면 Rear를 배열의 가장 앞으로 옮겨줘서 원형으로 연결하여 배열 공간을 더 효율적으로 사용 할 수 있다.
  • 우선 순위 큐(Priority Queue) : 우선 순위 큐는 삽입된 각 데이터 별로 우선순위를 부여해서 우선순위가
    높은 데이터부터 큐에서 꺼내진다. 일반적으로 데이터를 삽입할 때 우선 순위에 따라 정렬하여 구현한다.

JAVA CODE로 구현

선형큐

public class Queue {
    private Object[] data;
    private int manyItems;
    private int front;
    private int rear;
    Queue(int size){
        data = new Object[size];
        this.manyItems=0;
        this.front=0;
        this.rear=-1;
    }

    public Object Dequeue() {
        Object toDequeue;
        if (isEmpty())
            return "empty";
        toDequeue = data[front];
        front++; //front를 하나 증가시켜서 dequeue한 데이터는 접근 불가
        manyItems--; //아이템 개수 감소
        return toDequeue;
    }
    public void Enqueue(Object item){
        if(manyItems == data.length) //큐 배열이 꽉찼을 때
            System.out.println("Queue is Full");
        else{
            this.rear++; //rear를 하나 증가시켜서 데이터 저장
            data[rear] = item;
            manyItems++;
        }
    }
    public Object peek(){ //배열에서 아이템을 삭제하지 않고 확인
        if(isEmpty()){ //비어있는 스택인지 확인
            return "empty";
        }
        return data[front];
    }
    public boolean isEmpty(){
        return manyItems==0;
    }

    public static void main(String[] args){
        Queue q = new Queue(3);

        System.out.println("Enqueueing elements in Queue");
        for(int i = 1; i<=5; i++) { //반복문을 통해 push
            System.out.println("Enqueue :"+ i);
            q.Enqueue(i);
        }
        System.out.println("Is Queue empty? : "+q.isEmpty());
        System.out.println("Peek : "+ q.peek());

        System.out.println("Dequeue all element from Queue");
        for(int i=0; i<4; i++) //반복문을 통해 pop
            System.out.println("Dequeue : " + q.Dequeue());

        for(int i = 1; i<=5; i++) { //반복문을 통해 push
            System.out.println("Enqueue :"+ i);
            q.Enqueue(i);
        }
        System.out.println("Is Queue empty? : "+q.isEmpty());
    }
}

실행 결과

queue 선형 큐 코드의 실행 결과를 보면 다음과 같은데 큐가 꽉 찰때까지 Enqueue를 하고 다시 큐가 텅 비게 될때까지 Dequeue를 수행합니다. 하지만 다시 Enqueue를 하려고 하면 ArrayIndexOutOfBoundsException이 발생하는데, 이는 배열의 범위를 벗어났다는 뜻입니다. Enqueue, Dequeue를 반복적으로 수행하는 과정에서 front와 rear가 이미 배열의 끝에 도달해 있기 때문입니다.
물론 선형큐에서도 이보다 더 효율적으로 코드를 작성할 수 있지만, 선형 큐의 단점을 강조하기 위해 위와 같이 코드를 작성하였습니다.
이러한 선형 큐의 단점을 보완하기 위해 사용하는 원형 큐는 어떻게 동작하게 되는지 코드를 통해 보여 드리겠습니다.

원형 큐