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

---

(1) 큐(Queue)

• 선입 선출(First In First Out, FIFO) 자료구조: 먼저 들어온 입력이 먼저 나감
• 입력 순서대로 데이터 처리가 필요할 때 사용
• ex) 프린트 출력 대기열, BFS(Breath-First Search: 너비 우선 탐색(트리))

큐 구조

---

(2) 큐 기본 구조

• 선입선출 구조
• 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐
  • 데이터 추가(Enqueue): 큐에 데이터 추가
  • 데이터 꺼내기(Dequeue): 큐에서 데이터 꺼내기

데이터 추가(Enqueue)

데이터 꺼내기

---

(3) JAVA 코드로 학습하기

---

(1) JAVA에서 제공하는 java.util.Queue로 구현하기

//선형 자료구조-큐
public class Main {
    public static void main(String[] args){
        Queue queue = new LinkedList();  //queue가 인터페이스로 구현되어 있음

        queue.add(1);  // (1) 큐에 데이터 추가
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        System.out.println(queue);
        line();

        System.out.println(queue.poll());  // (2) 큐에서 가장 첫 번째 데이터 꺼내기
        System.out.println(queue);
        line();

        System.out.println(queue.poll());
        System.out.println(queue);
        line();

        System.out.println(queue.peek());  // (3) 큐에서 가장 첫 번째 데이터를 꺼내고 삭제는 하지 않음
        System.out.println(queue);
        line();

        System.out.println(queue.contains(1));  // (4) 큐에 1이라는 요소를 포함하고 있는지 확인
        System.out.println(queue.size());  // (5) 큐의 사이즈 확인
        System.out.println(queue.isEmpty());  // (6) 큐가 비어져 있는지 확인
        line();

        queue.clear();  // (7) 큐 전체 지우기
        System.out.println(queue);
        System.out.println(queue.poll());  // (8) 큐가 비어져 있을때 꺼내면 null 출력
    }
}

---

(2) ArrayList를 이용한 Queue 구현하기

//ArrayList를 이용한 queue 구현
class MyQueue1{
    ArrayList list;  //요소를 저장할 리스트 선언

    MyQueue1(){
        this.list = new ArrayList();  //리스트 생성
    }

    // 리스트(Queue)가 비어져 있는지 확인하는 함수
    public boolean isEmpty(){
        if(this.list.size() == 0){  //MyQueue1의 list 변수의 사이즈가 0인 경우 비어져있음
            return true;
        }
        return false;
    }

    // Queue애 data 추가
    public void push(int data){
        this.list.add(data);
    }

    // Queue의 첫 번째(rear)에서 데이터 꺼내기
    public Integer pop(){
        if(this.isEmpty()){  //비어져있으면
            System.out.println("list is empty");
            return null;
        }

        int data = (int) this.list.get(0);  //generic되어 있지 않으므로 (int) 붙여줘야 함
        this.list.remove(0);  //첫 번째 요소 삭제
        return data;
    }

    // 요소 꺼내는데 삭제는 하지 않는 함수
    public Integer peek(){
        if(this.isEmpty()){  //queue가 비어져 있는 경우
            System.out.println("list is empty");
            return null;
        }

        return (int) this.list.get(0);  //꺼내기만하고 삭제하지 않음
    }

    // 전체 Queue의 요소를 출력하는 함수
    public void printQueue(){
        System.out.println(this.list);
    }
}

---

(3) Array를 이용한 큐 구현(원형 큐)

//Array를 이용한 큐 구현(원형 큐)
class MyQueue2{
    int[] arr;  //저장할 배열 선언
    int front = 0;  //Queue의 앞부분의 위치
    int rear = 0;  //Queue의 뒷부분의 위치

    MyQueue2(int size){
       arr = new int[size+1];  //원하는 사이즈+1: 공간 하나는 비워두고 원형으로 관리하기 위함임
    }

    // 배열이 비어져 있는 경우를 확인하는 함수
    public boolean isEmpty(){
        return this.rear == this.front;  //앞부분 인덱스와 뒷부분 인덱스가 같으면 비어져있는 경우
    }

    // 배열이 꽉차있는지 확인하는 함수
    public boolean isFull(){
        // 배열의 길이만큼 나눠 나머지를 구해서 원형으로 관리
        return (this.rear +1)%this.arr.length == this.front;  //뒤를 가리키는 인덱스의 다음이 앞부분을 가리키는 경우에 가득 차있음
    }

    // 배열에 data 추가하는 함수
    public void enqueue(int data){
        if(this.isFull()){  //배열이 가득 차있다면
            System.out.println("Queue is full");
            return;
        }

        this.rear = (this.rear + 1) % this.arr.length;  //원형으로 관리하기 위해 배열의 길이만큼 나눔
        this.arr[this.rear] = data;  //data 넣음
    }

    // front의 위치에서 데이터를 꺼냄 
    public Integer dequeue(){
        if(this.isEmpty()){  //데이터가 비어져있다면
            System.out.println("Queue is empty");
            return null;
        }

        front = (front + 1) % this.arr.length;  //원형으로 관리하기 위해 배열의 길이만큼 나눔
        return this.arr[front];
    }

    // Queue의 모든 요소를 출력하는 함수
    public void printQueue(){
        int start = (this.front + 1) % this.arr.length;  //시작 부분
        int end = (this.rear + 1) % this.arr.length;  //끝나는 부분

        for (int i = start; i != end; i=(i + 1) % this.arr.length) {  //원형으로 관리, 끝나는 부분이 아닐 때까지 반복
            System.out.print(this.arr[i]+ " ");
        }
        System.out.println();
    }
}

• 원형으로 관리한다는 의미는 배열의 길이는 한정되어 있으므로 공간을 효율적으로 관리하기 위함임
• 예를들어, 배열의 길이가 5인 상황에서, 앞 부분을 가리키는 front부분이 5를 가리키면 rear의 위치는 6이 되어야하는데
• 6은 배열의 범위를 벗어나고 배열의 1,2,3,4부분이 비어져 있기때문에
• 6 % (배열의 길이 (==5)) = 1로 계산하여
• 배열의 빈 부분부터 다시 채워 관리하는 방법임