Java 자료구조 Queue (1) 간략히 보기

Queue 이란?

• 선입선출 (First-In-First-Out-FIFO)
• 순서가 보장된 처리
  • 사용자가 몰린 서버
• 언어마다 구현된 API가 약간씩 다름
  • push(), offer(), add()
  • pop(), poll()
  • peek()
• 순서를 보장하는 자료구조

• Queue 는 배열구조로 하기에는 비효율적이다.
  • 왜냐하면 앞에 데이터를 뽑으면 앞쪽 데이터가 비어있으므로 한 칸씩 앞으로 땡겨줘야 한다.
  • 그렇지 않으면 앞에 공간이 비어있는데도 불구하고 뒤에 데이터가 계속 차오르기 때문이다.
  • 따라서 시간복잡도도 O(N) 으로 늘어난다.
  • 그래서 배열보다는 링크드 리스트로 구현한다.

Queue 를 구현 하는 방법

1. LinkedList 를 이용한 구현
2. 배열을 이용한 원형 큐 구현
   • 배열을 이용한 선형 큐 구현은 매우 비효율적
   • 
   • 
   • front 와 index 인덱스를 갖고 데이터를 갖고옴
   • 
   • 더미공간을 만들어서 큐가 비어있는 상태인지 꽉 차있는지 구별함
   • 고정된 크기의 배열로 구현
   • 인덱스가 원형이라 모듈로 접근해야함
     • 예) 인덱스가 5가 끝이라면 인덱스 6은 1을 가르키게 모듈화함
     • 

LinkedList 코드 구현

package queue;  
  
public interface IQueue<T> {  
    void offer(T data);  
    T poll();  
    T peek();  
    int size();  
    void clear();  
    boolean isEmpty();  
}

package queue;  
  
public class MyLinkedQueue<T> implements IQueue<T> {  
    private Node head;  
    private Node tail;  
    private int size;  
  
    public MyLinkedQueue() {  
        this.size = 0;  
        this.head = new Node(null);  
        this.tail = this.head;  
    }  
  
    @Override  
    public void offer(T data) {  
        Node node = new Node(data);  
        this.tail.next = node;  
        this.tail = this.tail.next;  
        this.size++;  
    }  
  
    @Override  
    public T poll() {  
        if (isEmpty()) {  
            throw new IllegalStateException();  
        }  
        Node node = this.head.next;  
        this.head.next = node.next;  
        node.next = null;  
        this.size--;  
        if (this.head.next == null) {  
            this.tail = this.head;  
        }  
        return node.data;  
    }  
  
    @Override  
    public T peek() { // 가장 앞에 있는 데이터 확인만  
        if (isEmpty()) {  
            throw new IllegalStateException();  
        }  
        return this.head.next.data;  
    }  
  
    @Override  
    public int size() {  
        return this.size;  
    }  
  
    @Override  
    public void clear() {  
        this.head.next = null;  
        this.tail = head;  
        this.size = 0;  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return this.head.next == null;  
    }  
  
    private class Node {  
        T data;  
        Node next;  
  
        Node(T data) {  
            this.data = data;  
        }  
  
        Node(T data, Node next) {  
            this.data = data;  
            this.next = next;  
        }  
    }  
}

원형 큐 (Circular Queue) 구현

package queue;  
  
public class MyCircularQueue<T> implements IQueue<T> {  
  
    private T[] elements;  
    private int front;  
    private int rear;  
    private int maxSize;  
  
    public MyCircularQueue(int size) {  
        this.elements = (T[]) new Object[size + 1];  
        this.front = 0;  
        this.rear = 0;  
        this.maxSize = size + 1;  
    }  
  
    @Override  
    public void offer(T data) {  
        if (isFull()) {  
            throw new IllegalStateException();  
        }  
  
        this.rear = (this.rear + 1) % this.maxSize;  
        this.elements[this.rear] = data;  
    }  
  
    @Override  
    public T poll() {  
        if (isEmpty()) {  
            throw new IllegalStateException();  
        }  
        this.front = (this.front + 1) % this.maxSize;  
        return this.elements[this.front];  
    }  
  
    @Override  
    public T peek() {  
        if (isEmpty()) {  
            throw new IllegalStateException();  
        }  
        return this.elements[this.front + 1];  
    }  
  
    @Override  
    public int size() {  
        if (this.front <= this.rear) {  
            return this.rear - this.front;  
        }  
        return this.maxSize - this.front + this.rear;  
    }  
  
    @Override  
    public void clear() {  
        this.front = 0;  
        this.rear = 0;  
    }  
  
    @Override  
    public boolean isEmpty() {  
        return this.front == this.rear;  
    }  
  
    private boolean isFull() {  
        return (this.rear + 1) % this.maxSize == this.front;  
    }  
}