자료구조 - 큐(Queue)

1. 큐의 구조

큐는 FIFO, LILO 구조 혹은 선입선출의 개념을 가지고 있다.

예를 들어 줄서는 개념과 같은데 먼저 줄을 선 사람이 먼저 나가고 늦게 들어온 사람은 늦게 나가는 것과 같은 개념이다.

 

 

 

 

2. 본론

 

 

 

 

 

 

 1) 큐의 용어

1) enqueue

큐에 데이터를 넣는 기능

2) dequeue

큐에서 데이터를 빼내는 기능

 

출처 https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

 2) 특수한 형태의 큐

 - 원형 큐(링버퍼)

큐를 통해서 데이터를 저장할때 dequeue를 해주게 되면 데이터를 한칸씩 앞으로 이동시켜야 하는 단점이 있다. 그렇지 않다면 큐의 정해진 사이즈 때문에 out of index 에러가 생길것이다.

이를 방지하기 위한 원형 큐가 존재한다. 

 

<파이썬 알고리즘 인터뷰> p.260, 책만, 2020

 

논리적으로 따지자면 큐의 맨 끝과 맨 앞으로 연결해 놓은것이다.

front와 rear라는 포인터를 두고 데이터가 enqueue되면 fron+1, dequeue 되면 rear+1

rear와 front가 같다면 empty, rear+1이 front의 포인터와 같다면 full 상태가 되어지는 것이다.

 

 

 - 우선순위 큐

우선순위 큐는 fifo가 아닌 우선순위에 따라서 출력이 달라지는 것이다. 대표적인게 heap 

 

 - lifo 큐

이것은 나중에 들어온것이 먼저 나가는 경우이다. 이것은 stack 자료구조이다.

 

 - Deque(데크; Double Ended Queue)

일반적인 큐는 한방향으로 입력과 출력이 이루어지는데 반해 데크는 양쪽에서 입출력이 가능한 특징이 있다. 

데크는 이중연결 리스트로 구현하는것이 가장 적합하다고 한다. head와 tail 포인터를 가지고 있고 enqueue dequeue에 따라서 포인터가 이동한다.

 

 

 

 

 

 

 

 

 

 

 

 3) queue의 용도

어떠한 작업이나 데이터를 순서대로 실행시키기 위해서 혹은 사용하기 위해서 대기 시킬때 사용한다.

또는 서로 다른 쓰레드나 프로세스 사이에서, 네트워크에서 자료를 주고받을떄 일시적으로 저장하는 용도로 사용한다.

 

 

3. 구현

public class Main {

    public static void main(String[] args) {
        Queue q = new Queue(10);
        q.enqueue(10);
        q.enqueue(9);
        q.enqueue(8);
        q.enqueue(7);
        q.enqueue(6);
        q.enqueue(5);
        q.enqueue(4);
        q.enqueue(3);
        q.enqueue(2);
        q.enqueue(1);
//        q.enqueue(0); // overflow error
        System.out.printf("--------------------\n");
        q.print();
        q.dequeue();q.dequeue();q.dequeue();q.dequeue();
        q.dequeue();q.dequeue();q.dequeue();q.dequeue();
        System.out.printf("--------------------\n");
        q.print();
    }
}
class Queue{
    private Object[] q;
    private int front=-1;
    private int rear=-1;

    public Queue(int n){
        this.q = new Object[n];
    }
    public boolean isFull(){
        if (rear == this.q.length-1)return true;
        else return false;
    }
    public boolean isEmpty(){
        if (front==rear)return true;
        else return false;
    }
    public void enqueue(Object obj){
        if (isFull()) throw new Overflow();

        q[++rear] = obj;
    }
    public Object dequeue(){
        if(isEmpty()) throw new Underflow();

        Object temp = q[++front];

        for(int i =++front; i<=rear; i++){
            q[i-1] = q[i];
            if(i==rear){
                q[i] = null;
            }
        }
        front=-1;
        rear--;
        return temp;
    }
    public void print(){
        for(int i = 0; i<=rear;i++){
            System.out.println(q[i]);

        }
    }
    class Overflow extends RuntimeException{}
    class Underflow extends RuntimeException{}
}


//  result
//--------------------
//10
//9
//8
//7
//6
//5
//4
//3
//2
//1
//--------------------
//2
//1