[자료구조] 큐(Queue)

큐(Queue)란

한쪽으로 넣고 다른 한 쪽으로 나오는 FIFO(First In First Out), 즉 선입선출 구조의 자료구조

Ex)터널, 선착순 예매

큐의 정의, 연산

Enqueue(item): item을 큐의 마지막에 저장한다.

Dequeue(): 큐의 가장 앞선 데이터를 삭제한다.

배열로 큐 구현

package Queue;

public class ArrayQueue {
    private char[] array;
    private int front;
    private int rear;
    private int size;

    public ArrayQueue(int size){    //큐 배열 생성
        this.front = 0;
        this.rear = -1;
        this.size = size;
        this.array = new char[size];
    }

    public boolean isEmpty(){   //큐가 비어있는지 확인
        return (front == rear+1);
    }

    public boolean isFull(){    //큐가 가득 차있는지 확인
        return (front == size-1);
    }

    public void enqueue(char item){   //데이터 삽입
        if(isFull())
            throw new ArrayIndexOutOfBoundsException();
        array[++rear] =item;
    }

    public char peek(){   //front 데이터 조회
        if(isEmpty())
            throw new ArrayIndexOutOfBoundsException();
        return array[front];
    }

    public char dequeue(){    //front 데이터 제거
        char item = peek();
        front++;
        return item;
    }
}

연결리스트로 큐 구현

//마저 하기

데크(Deque)란

양방향 큐, 삽입과 삭제가 양쪽 방향에서 이루어진다.

활용예시

• 우선순위가 같은 작업 예약(인쇄 대기열)
• 선입선출이 필요한 대기열(티켓 카운터)
• 콜센터 고객 대기시간