큐(Queue)

큐 ?

- 스택과 같이 데이터를 일시적으로 쌓아 놓는 자료구조

- FIFO(First In First Out) 방식으로 데이터를 입`출력
👉 먼저 들어온 데이터 순으로 먼저 나오게 된다. / 데이터 순서가 보장된다.

-Java에서 Queue는 인터페이스이며, 이를 구현한 구현체들이 있는데 이를 활용하여 사용할 수 있다. 그 중 하나가 LinkedList이다. 👉 큐의 경우 데이터의 순서가 있기에 List형 컬렉션을 사용해야하는데 FIFO구조이기에 ArrayList를 사용할 경우 삭제 시 배열의 요소들 간에 이동이 발생한다. 그렇기에 LinkedList로 구현하는 것이 유리하다.

용어 ?

인큐(en-queue) : 큐에 데이터를 저장하는 작업
디큐(de-queue) : 큐에서 데이터를 꺼내는 작업
프런트(front) : 큐에 맨 앞 부분으로 데이터가 나오는 쪽
리어(rear) : 큐에 맨 마지막 부분으로 데이터가 들어오는 쪽

Queue 기능?

배열로 큐 만들기

배열을 통해서 Queue를 구현한 모습을 그림으로 나타낸 것이다. 이때 데이터를 넣고 빼는 것을 정리해보면,

En-queue(넣기) : 내부적으로 저장해야하는 위치 + 데이터 수를 저장한 변수 하나를 통해서
해당 위치에 데이터를 저장하고 위치를 하나 증가시키면 된다. 이때 시간 복잡도는 O(1)이 된다.
que[num++] = 값;

De-queue(빼기) : 스택에서는 포인터 역할을 할 변수 하나를 통해서 위치에 넣고 빼고 할 수 있었다.
즉, 마지막에 들어온 데이터가 가장 먼저 나가며, 포인터 변수는 데이터들 가장 뒤쪽에 위치하기 때문이다.
그러나 Queue의 경우는 먼저 온 데이터부터 먼저 나가기에 데이터를 뺄 경우 0번 인덱스 값을 빼야한다.
이것은 단순히 que[0] 값을 반환만 해주면 된다. 그러나 제거가 이루어졌기에 그 뒤에 데이터들은 0번
인덱스를 채우기 위해 자신의 위치에서 앞으로 한 칸씩 이동하며 위치를 채워나가야한다.
남은 데이터가 N개라 할 경우 각 데이터를 현재 인덱스에서 한 칸씩 앞으로 이동해야하기에
시간복잡도 O(n)이 된다. 즉, 비용이 소모된다.

public class IntArrayQueue {
    private int[] que; // 큐 본체
    private int capacity; // 용량
    private int num; // 포인터 역할 변수

    public IntArrayQueue(int capacity){
        this.capacity = capacity;
        que = new int[capacity];
    }

    public static class EmptyIntArrayQueueException extends RuntimeException{
        public EmptyIntArrayQueueException(){};
    }

    public static class OverflowIntArrayQueueException extends RuntimeException{
        public OverflowIntArrayQueueException(){};
    }
	
    // 인큐
    public int inque(int x) throws OverflowIntArrayQueueException{
        if(x >= capacity)
            throw new OverflowIntArrayQueueException();
        return que[num++] = x;
    }
    
	//디큐
    public int deque() throws EmptyIntArrayQueueException{
        if(num <= 0)
            throw new EmptyIntArrayQueueException();
        int val = que[0];
        for(int i = 0 ; i < num - 1 ; i++)
            que[i] = que[i+1];
        num--;
        return val;
    }

	// 가장 앞 요소
    public int peek() throws EmptyIntArrayQueueException{
        if(num <= 0)
            throw new EmptyIntArrayQueueException();
        return que[num-1];
    }

	// 데이터 모든 clear
    public void clear(){num = 0;}

	// 원하는 값이 어느 위치에 있는지 확인
    public int indexOf(int x){
        for(int i = 0; i < num ; i++)
            if(que[i] == x)
                return i;
        return -1;
    }

	// 용량
    public int getCapacity(){
        return capacity;
    }

	// 데이터 저장된 수
    public int size(){
        return num;
    }

	//큐가 비어있는지 확인
    public boolean isEmpty(){
        return num <= 0;
    }

	// 큐에 저장된 데이터들 보기
    public void dump(){ // 왼쪽에서 오른쪽으로 데이터가 들어오는 형태로 출력
        if(num <= 0)
            System.out.println("큐가 비어있습니다.");
        else{
            for(int i = num - 1; i >= 0 ; i--){
                System.out.print(que[i] + " ");
            }
        }
        System.out.println("->");
    }
}

링 버퍼로 큐 만들기

De-queue 시 데이터를 옮겨야하는 비용 소모를 줄이기 위한 자료구조로 링 버퍼 활용
배열의 맨 앞,뒤가 연결되었다고 보는 자료구조(링 버퍼)
실제 배열이 물리적으로 연결된 것이 아닌 논리적으로 연결되었다고 보는 것

설명?

위 그림은 간단하게 자료구조가 어떻게 생겼는지 보기 위함이다.

용량 12짜리 배열이며 {35,56,24,68,95,73,19} 형태로 저장이 되어있다.
이때, 물리적 배열의 위치로는 {73,19,x,x,x,x,x,35,56,24,68,95} 형태이며 실제 마지막 인덱스 다음으로 첫 번째 인덱스가 오지 않는다.
즉, 논리적으로 연결되었다고 본 것이다. 이를 위해서는 배열 인덱스를 이용할 것이며, 현재 상태에서 맨 앞쪽과 맨 마지막 위치를 알 수 있는 변수를 각각 활용한다.(front , rear)
그리고 현재 쌓여 있는 데이터 수를 위하여 num이라는 변수하나를 만든다.
여기서 num은 단순 데이터 수만을 위함이 아닌 추후 데이터가 현재 없는지, 가득찼는지를 구분하기 위함이다.
예를 들어 데이터가 없을 경우도 front == rear는 같은 위치 일 것이며, 가득 찼을 경우도 한 바퀴 순환했기에 같은 위치이다.
처음 큐가 만들어지면 num = front = rear = 0 위치에서 시작한다.
Front : 데이터가 나오는 위치 / Rear : 데이터가 들어오는 위치 / num: 데이터 수<< 이걸 기억해두고 보자
데이터가 En-queue 되면 0번 인덱스에 값이 들어온다. 이때 num, Rear은 1개 증가한다.
En-queue를 할 시 num과 Rear가 증가한다는 것을 기억하고 Rear는 Queue에서 데이터가 들어오는 곳으로 항상 꼬리쪽이다.
다음으로 De-queue가 될 시 가장 현재 쌓인 데이터에서 가장 먼저 쌓은 데이터가 나간다. Queue에 가장 앞쪽은 Front이며 이는 front 변수에 위치가 저장되어 있다. 그리고 저장되어 있는 인덱스에서 값이 나간다. 그러면 front는 다음 위치를 가르켜야 하기에 1증가하며 num 1개가 줄어든다.
이런 식으로 데이터가 Queue에 En-queue, De-queue 작업을 수행한다.
이때 한가지 생각해 볼 것은 결국은 front , rear 변수는 배열의 인덱스가 저장되어 있는 것이다. 그렇기에 작업이 이루어질때 값이 증가하는데 그러다보면 배열의 크기(capacity)를 벗어나게 된다. 그럼 예외가 발생할 것이다.
그렇기에 En-queue , De-queue가 수행될 때 이 부분을 체크해서 capacity와 같아지면 0으로 셋팅해줘야한다.
배열은 인덱스가 0부터 시작해서 크기 - 1까지 인덱스를 갖는다. 예를들어 크기 10 배열은 0 ~ 9 까지 인덱스를 갖는다. capacity == front,rear가 되었다는 것은 현재 가르키는 인덱스가 10이며 순환하는 자료구조이기에 가장 맨 인덱스인 0이 되어야한다.
이처럼 En-queue , De-queue에 따라서 front 또는 rear가 값이 증가하고 0으로 초기화 되기를 반복한다. 이 부분을 생각해보면 데이터가 없을때시 front == rear은 같다. 즉 아무것도 없기에 들어오는 곳이 곧 나가는 쪽이된다. 한가지로는 모든 데이터가 가득 찼을경우 순환하는 구조이기에 한 바퀴를 돌기에 또 두 인덱스 위치는 같아진다. 이때 이처럼 비어있는지 , 가득 찼는지를 체크하기 위해 num이 사용된다. 즉 데이터 수인 num이 0이라는 것은 비어있는 것이며 num이 capacity와 같다는 것은 가득 찼다는 것이다.
마지막으로 이와같이 링 버퍼형태로 큐를 구현했을경우를 생각해보면 결국 En-Queue는 배열로 구현했을때와 동일하게 포인터 위치에 저장이된다. 그러나 De-queue를 생각해보면 배열의 경우는 항상 0번 인덱스에서 값이 나가고 그 자리를 뒤에서부터 채워야하기에 시간복잡도 O(n)이며, 비용이 발생한다. 그러나 링 버퍼로 했을 경우는 데이터를 이동 시킬 필요 없이 단순히 front변수의 값만 변경하여 Queue에 가장 앞쪽을 가르키게 하면된다. 즉 값을 하나증가만 하면되기에 시간 복잡도 O(1)이 된다. 그리고 마지막으로 가르키는 인덱스가 한 바퀴 순환했는지만 체크해주면 된다.

public class IntQueue {
    private int[] que; // 큐 본체
    private int capacity; // 용량
    private int front; // 인큐 시키는 데이터 중 맨 앞 요소 인덱스
    private int rear; // 인큐 시키는 데이터 중 맨 마지막 요소 인덱스
    // 현재 데이터 개수
    // front == rear 일 경우 비어있는지 가득찬 것이지 구별
    private int num;

    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){};
    }

    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){}
    }

    public IntQueue(int capacity){
        this.capacity = capacity;
        try {
            que = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }

    public int enque(int x) throws OverflowIntQueueException{
        if(num >= capacity)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if(rear == capacity)
            rear = 0; //링 버퍼이기에 용량과 같음은 한 바퀴를 돌았다는 의미
        return x;
    }

    public int deque() throws EmptyIntQueueException{
        if(num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if(front == capacity)
            front = 0;
        return x;
    }

    public int peek() throws EmptyIntQueueException{
        if(num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }

    public void clear(){
        num = front = rear = 0;
    }

    public int indexOf(int x){
        for(int i = 0 ; i < num ; i++){
            int idx = (i + front) % capacity;
            if (que[idx] == x)
                return idx;
        }
        return -1;
    }

    public int getCapacity(){
        return capacity;
    }

    public int size(){
        return num;
    }

    public boolean isEmpty(){
        return num <= 0;
    }

    public boolean isFull(){
        return num >= capacity;
    }

    public void dump(){
        if(num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else{
            for(int i = 0 ; i < num ; i++)
                System.out.println(que[(i + front) % capacity] + " ");
            System.out.println();
        }
    }
}

'알고리즘&자료구조 > 자료구조' 카테고리의 다른 글

Deque / PriorityQueue (0)	2023.02.06
[List] LikedList (0)	2023.02.06
[List] ArrayList (2)	2023.02.02
스택(Stack) (0)	2022.09.15

큐 ?

용어 ?

Queue 기능?

배열로 큐 만들기

링 버퍼로 큐 만들기

설명?

'알고리즘&자료구조 > 자료구조' 카테고리의 다른 글

티스토리툴바