[자료구조] 큐(Queue) 정리

1. Queue 컬렉션

---

Queue(큐)는 Stack(스택)과 반대로 먼저 추가된 데이터가 먼저 나오는 FIFO (First In First Out) 동작을 갖는다. 이것은 선입선출 방식이라고도 한다. FIFO 방식은 운영체제의 프로세스 관리, 프린트 출력 대기열, 너비 우선 탐색(BFS, Breath-First Search) 알고리즘 등에서 사용된다. 

큐는 한쪽에서만 입력이 이루어지고, 다른 쪽 끝에서는 출력만 이루어지는 구조이다.

큐에 자료를 넣는 것을 인큐(Enqueue) 라고 하고 반대로 자료를 꺼내는 것을 디큐(Dequeue) 라고 한다. 이때 자료는 가장 먼저 입력된 자료부터 나오게 된다.

---

(1) 자바의 Queue

 

클래스	분류	설명
Queue	인터페이스	데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 선입선출(FIFO, First In First Out)의 특성을 가짐
Deque	인터페이스	양쪽 끝에서 삽입과 삭제가 가능한 자료구조 중 하나로 선입선출(FIFO), 후입선출(LIFO) 개념이 모두 적용되는 구조
PriorityQueue	Queue 인터페이스의 구현체	우선순위 큐를 구현하는데 사용되며 우선순위가 높은 요소가 먼저 나오는 구조
ArrayDeque	Deque 인터페이스의 구현체	스택으로 사용할 수 있는 덱(Double Ended Queue) 구조이다. 배열을 이용하여 구현되며, 크기가 제한되어 있지 않다.

---

2. Queue 사용법

---

자바는 java.util.Queue 클래스를 통해 Queue(큐)를 제공하고 있다. 큐는 리스트로 구현되어 있기 때문에 java.util.LinkedList 클래스도 임포트 해줘야한다.

Queue 는 인터페이스 이므로 Queue queue = new Queue(); 로 생성이 불가능하다.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();  // 큐 생성

 

 

 

(1) Queue에 데이터 추가하는 방법 (add와 offer의 차이점)

queue.offer(i);  // 방법1
queue.add(i);   // 방법2

 

만약 값 추가에 실패했을 경우

add() → IllegalStateException

offer() → false

를 리턴하게 된다.

 

 

 

 

(2) Queue 값 출력

queue.peek();   //  현재 queue에 가장 먼저 들어간 값이 출력

 

만약 Queue 가 현재 비어있을 경우 null 을 return 한다.

읽기만 하고 Deque 하지 않는다. 단지, 데이터만 읽는다.

 

 

 

(2) Queue 값 삭제 (출력)

queue.poll();     // queue의 첫번째 값 삭제 , 주로 사용하는 방법
queue.clear();    // queue를 비움
queue.remove();   // queue의 첫번째 값 삭제

 

poll() 과 remove()는 값이 있을 경우 첫번째 값을 출력하면서 삭제처리를 한다.

하지만 데이터가 없을 경우 값 출력 및 삭제 시, 

poll() → NoSuchElementException

remove() → null

을 리턴한다.

 

 

 

 

(3) 비었는지 확인

• queue.isEmpty()  -> boolean 값을 반환한다.

 

 

 

(4) 큐 사이즈 확인

Queue queue = new LinkedList(); 

queue.add(1);
queue.add(2);
queue.add(3);

System.out.println(queue.size());    // 3

 

 

 

 

(5) 큐 안에 있는 데이터 포함 여부 확인

Queue queue = new LinkedList(); 

queue.add(1);
queue.add(2);
queue.add(3);

System.out.println(queue.contains(3));    // 3이 포함되어 있므로 true 출력

 

 

 

---

 

 

 

3. Queue 구현하기

• ArrayList를 이용하여 Queue 구현하기

class MyQueue {
	ArrayList list;
    MyQueue () { list = new ArrayList(); }
    
    public boolean isEmpty() {
    	if (this.list.size() == 0) {
        	return true;
        } else {
        	return false;
        }
    }
    
    public void push(int data) {
    	this.add(data);
    }
    public Integer pop() {
    	if (this.isEmpty) {
        	System.out.println("Queue is empty");
            return null;
        } else {
        	int data = (int)this.list.get(0);   // 리스트가 제네릭하지 않으므로 int로 형 변환 필수
            this.list.remove(0);
            return data;
        }
    }
    
    public Integer peek() {
    	if (this.isEmpty) {
        	System.out.println("Queue is empty");
            return null;
        }
        return (int)this.list.get(0);
    }
    
    public void printQueue() {
    	System.out.println(this.list);
    }
}

 

 

 

---

 

 

• 배열을 이용하여 Queue 구현하기 (원형 큐)

class MyQueue {
	int[] arr;
    int front = 0;
    int rear = 0;
    
    MyQueue(int size) { arr = new int[size+1]; }   // front 값은 null로 두기 위해
    
    public boolean isEmpty() { return this.front == this.rear; }
    
    public boolean isFull() {
    	return (this.rear + 1) % this.arr.length == this.front;
    }
    
    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;
    }
    
    public Integer dequeue() {
    	if (this.isEmpty()) {
        	System.out.println("Queue is Empty");
            return;
        }
        front = (front+1) % this.arr.length;
        return this.arr[front];
    }
    
    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();
    }
    
}