[Java-자료구조] Queue 사용과 구현

 

Queue

• 선형 자료구조
• 한쪽 끝에서만 삽입이 이루어지고 다른 한쪽 끝에서는 삭제이 이루어지는 FIFO구조의 자료구조
• Queue에는 선형 큐,원형큐, 링크드리스트 큐, 우선순위큐 등의 종류가 존재한다.
• 컴퓨터의 버퍼에서 사용하는 형태

멤버변수: rear(새로운 element가 들어가는 위치) head(element가 나가는 위치)

 

Queue 사용법

import java.util.Queue;

자바는 java.util.Queue 인터페이스로 Queue를 제공하고 있다.

 

Queue 선언

Queue<Integer> queue = new LinkedList<>(); // linkedlist를 이용한 Queue 사용법

Queue 자체는 인터페이스이기 때문에 LinkedList를 이용하여 Queue를 선언해야 한다.

 

Queue  메서드

데이터 삽입(Push)

queue.add(E element); // element를 Queue에 넣되 공간이 부족하면 IllegalStateException 오류 발생 성공시 true
queue.offer(E element); // element를 Queue에 추가하고 성공하면 true, 실패하면 false

데이터 삭제(Pop)

queue.remove(); // 객체를 꺼내서 반환하되 Queue가 비어있다면 NoSuchElementException 예외 발생
queue.poll(); // 객체를 꺼내서 반환하고 Queue가 비어있다면 null 반환

데이터 검색

queue.element(); // front부분에 있는 element를 반환하고 Queue가 비어있다면 예외를 발생합니다.
queue.peek(); // front부분에 있는 element를 반환합니다. Queue가 비어있다면 null을 반환합니다.

 

Queue 시간복잡도

동작	시간복잡도 Big O
Insertion	O(1)
Deletion	O(1)
Search	O(N)

---

Queue 장단점

장점

• front쪽에서는 데이터를 빼기만 하고 rear쪽에서는 데이터를 삽입하기만 하기에 데이터의 삽입, 삭제 연산이 빠르다.
• 데이터의 입력 순서로 처리가 필요한 경우 사용한다.

단점

• 선형 큐로 구현하는 경우 삽입과 삭제 과정에서 공간의 효율성을 위해 element를 이동시키는 연산이 필요하거나 이동시키지 않고 쓰는 경우 공간낭비가 발생할 수 있다.
• 원형 큐로 구현하는 경우 메모리 공간의 효율성은 증가하지만 배열로 구현되기에 큐의 크기가 한정적이다.

 

---

구현

Queue 인터페이스

public interface Queue<E> {

    boolean add(E element); // element를 Queue에 추가 저장공간이 부족하면 IllegalStateException

    boolean offer(E element); // element를 Queue에 추가

    E element(); // 삭제없이 front의 요소를 가져온다. 비어있으면 NoSuchElementException

    E peek();  // 삭제없이 front의 요소를 가져온다.

    E remove(); // 객체를 꺼내서 반환  비어있으면 NoSuchElementException

    E poll(); // 객체를 꺼내서 반환
}

Linear Queue(with array)

import java.util.NoSuchElementException;

public class LinearQueue<E> implements Queue<E>{
    private int front;
    private int rear;
    private int capacity;
    private E[] array;
    private int size;
    private final int DEFAULT_SIZE = 100;

    LinearQueue(){
        array = (E[])new Object[DEFAULT_SIZE];
        front = 0;
        rear = 0;
        size = 0;
        capacity = DEFAULT_SIZE;
    }

    LinearQueue(int capacity){
        array = (E[])new Object[capacity];
        front = 0;
        rear = 0;
        size = 0;
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E element) {
        boolean isAdd = true;
        if(size == capacity){
            isAdd = false;
        }else {
            if (size != 0) {
                rear++;
            }
            array[rear] = element;
            size++;
        }
        return isAdd;
    }

    @Override
    public boolean add(E element) {
        boolean check = offer(element);
        if(!check){
            throw new IllegalStateException();
        }
        return check;
    }

    @Override
    public E peek() {
        if(size==0){
            return null;
        }
        return array[front];
    }

    @Override
    public E element() {
        E result = peek();
        if(result == null){
            throw new NoSuchElementException();
        }
        return result;
    }

    @Override
    public E poll() {
        if(size==0){
            return null;
        }
        E element = array[front];
        for(int i=1;i<=rear;i++){
            array[i-1] = array[i];
        }
        array[rear--] = null;
        size--;
        return element;
    }

    @Override
    public E remove() {
        E result = poll();
        if(result == null){
            throw new NoSuchElementException();
        }
        return result;
    }
}

Circular Queue(with array)

import java.util.NoSuchElementException;

public class ArrayQueue<E> implements Queue<E>{
    private int front;
    private int rear;
    private int capacity;
    private int size;
    private E[] array;
    private final int DEFAULT_SIZE = 100;

    ArrayQueue(){
        array = (E[])new Object[DEFAULT_SIZE];
        front = 0;
        rear = 0;
        capacity = DEFAULT_SIZE;
        size = 0;
    }

    ArrayQueue(int capacity){
        array = (E[])new Object[capacity];
        front = 0;
        rear = 0;
        this.capacity = capacity;
        size = 0;
    }

    @Override
    public boolean offer(E element) {
        boolean isAdd = true;
        if(size == capacity){
            isAdd = false;
        }else{
            if (size != 0) {
                rear++;
                rear %= capacity;
            }
            array[rear] = element;
            size++;
        }
        return isAdd;
    }

    @Override
    public boolean add(E element) {
        boolean check = offer(element);
        if(!check){
            throw new IllegalStateException();
        }
        return check;
    }

    @Override
    public E peek() {
        if(size==0){
            return null;
        }
        return array[front];
    }

    @Override
    public E element() {
        E result = peek();
        if(result == null){
            throw new NoSuchElementException();
        }
        return result;
    }

    @Override
    public E poll() {
        if(size==0){
            return null;
        }
        E element = array[front];
        array[front++] = null;
        size--;
        if(front == capacity){
            front %= capacity;
        }
        return element;
    }

    @Override
    public E remove() {
        E result = poll();
        if(result == null){
            throw new NoSuchElementException();
        }
        return result;
    }

}

// 일반적으로 원형 큐의 구현의 경우 배열의 한 칸정도는 Overflow를 막기 위해 남겨둔다. 

LinkedList Queue(with LinkedList)

import java.util.NoSuchElementException;

public class LinkedListQueue<E> extends DoublyLinkedList<E> implements Queue<E> {

    LinkedListQueue(){
        super();
    }

    @Override
    public boolean offer(E element) {
        addLast(element);
        return true;
    }

    @Override
    public E element() {
        E ele = getFirst();
        if(ele == null){
            throw new NoSuchElementException();
        }
        return ele;
    }

    @Override
    public E peek() {
        E element = getFirst();
        return element;
    }

    @Override
    public E poll() {
        if(size==0){
            throw new NoSuchElementException();
        }
        E element = removeFirst();
        return element;
    }
}

2022.01.16 - [JAVA/자료구조] - [Java-자료구조] LinkedList 사용과 구현 > Doubly LinkedList 구현

---

알고리즘 사용 사례 with Queue

• 프로세스 관리
• BFS 알고리즘
• 데이터 입력 순서에 따른 처리