📌 큐(Queue)란?

큐(Queue)는 사전적으로 ‘줄서서 기다리다’, ‘대기행결’ 이라는 의미를 가지고 있습니다. 줄에 기다리는 순서대로 먼저 줄을 선 사람이 먼저 입장하는 구조와 동일하게 이루어져 있습니다.

특징

• 큐는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 자료구조이지만 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어집니다.
• FIFO(First In First Out, 선입선출) : 데이터가 삽입된 순서대로 삭제되는 순서로 한쪽 끝을 front로 정하여 삭제 연산만 수행하도록 하고 다른 쪽 끝은 rear로 정하여 삽입 연산만 수행하도록 제한하여 만든 자료구조입니다.
• 데이터의 삽입과 삭제가 큐의 양 끝에서 각각 일어나므로 큐의 앞과 뒤를 명확하게 구분 지을 필요가 있습니다.
• 이러한 선입선출의 특징 때문에 임시로 자료를 저장하거나 버퍼와 같이 경우에 주로 사용하는 자료구조 형태입니다.

Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제

관련 용어

• front: 큐의 맨 앞, 데이터가 나가는 곳
• rear: 큐의 맨 뒤, 데이터가 들어오는 곳
• enqueue: 큐의 뒤에 데이터 추가
• dequeue: 큐의 앞에 데이터 삭제
• empty/full: 큐가 비었는지 가득 찼는지 검사
• getfront: 큐의 맨 앞을 알려주는 것(스택의 peek)
• size(level): 큐의 크기를 리턴

시간복잡도

• 삽입: Insertion O(1)
• 삭제: Deletion O(1)(dequeue) / O(N)(remove)
• 검색: Search O(N)

큐의 삽입은 front에서만 일어나고 삭제는 항상 rear에서만 일어나므로 삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정

📌 큐(Queue) 구현

public class ArrayQueue {
    int MAX = 1000;
    int front;    //머리 쪽에 위치할 index값, pop할때 참조하는 index
    int rear;    //꼬리 쪽에 위치할 index값, push할때 참조하는 index
    int [] queue;
    public ArrayQueue() {
        front = rear = 0;    //초기값 0
        queue = new int[MAX]; //배열 생성
    }

    public boolean queueisEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
        return front == rear;
    }
    public boolean queueisFull() {    //queue가 가득 차 공간이 없는지 판단하는 함수
        if(rear == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
        return front-rear;
    }
    public void push(int value) {
        if(queueisFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
    }
    public int pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front++];
        return popValue;
    }
    public int peek() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front];
        return popValue;
    }
}

📌 큐(Queue) 사용

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가
queue.peek();       // queue의 첫번째 값 참조
queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

참고

• https://gyoogle.dev/blog/computer-science/data-structure/Stack%20&%20Queue.html
• https://coding-factory.tistory.com/602
• https://go-coding.tistory.com/6

피드백 및 개선점은 댓글을 통해 알려주세요😊