[자료구조][JAVA]큐(Queue)

개념

💡큐(Queue)란??
한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다. 새로운 원소가 삽입되는 끝은 리어(rear)라 하고 원소가 삭제되는 끝을 프런트(front)라 한다.

특징

• FIFO(First-In-First-Out) 선입선출 구조의 자료구조다
• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
• tail(=rear)과 head(=front)가 존재한다.
• tail(=rear)과 head(=front)는 배열로 표현했을 때 가장 처음 0번지에 존재한다.
• 배열로 표현하면 head ~ tail-1번지가 원소들이 들어있는 위치다.

구조

class Queue{

    int[] save;
    int head = 0;
    int tail = 0;
    public Queue()
    {
      save = new int[100000];
    }
    public void push(int x){
        save[tail] = x;
        tail++;
    }
    public int pop(){
        if(empty() == 1)
        {
            return -1;
        }
        return save[head++];
    }
    public int front(){
        if(empty() == 1)
        {
            return -1;
        }
        return save[head];
    }
    public int back(){
        if(empty() == 1)
        {
            return -1;
        }
        return save[tail-1];
    }
    public int size(){
        return tail - head;
    }
    public int empty(){
        if(tail == head){
            return 1;
        }
        else
        {
            return 0;
        }
    }

}

• push : 뒷부분에 원소를 넣어준다.
• pop : 앞부분에 있는 원소를 반환해준다. 그리고 삭제한다.
• front : 앞부분의 원소를 반환해준다.
• back : 뒷부분의 원소를 반환해준다.
• size : 큐의 크기를 반환해준다.
• empty : 큐가 비어있는지 차있는지 판단해준다.