Queue의 다양한 구현

1. 원형 큐(링 버퍼) - 배열 기반

-  front(머리), rear(꼬리)라는 변수를 인덱스로 활용해 삽입,조회,삭제를 구현하였다.

-  front와 rear의 변수가 같다면 큐가 비어있는것이다.

-  front와 rear+1 이 같다면 큐가 꽉차있는것이다.

-  배열의 끝에 도달하면 첫번째 인덱스로 순환하여 원형큐라 한다.

-  삭제의 경우 배열에서 실제로 하지 않고 front(머리-출구), rear(꼬리-입구)의 값을 조정한다.

package queue;
public class ArrayQueueMain {
    public static void main(String[] args) {//배열 기반 큐
        ArrayQueue queue = new ArrayQueue();
        
        System.out.println("=offer=");
        
        queue.offer("0");
        queue.offer("1");
        queue.offer("2");
        
        System.out.println("=peek=");
        
        System.out.println(queue.peek());
        
        System.out.println("=poll=");
        
        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

package queue;
public class ArrayQueue {//배열 기반 큐
 
        int front=0;//출구 0으로 초기화
        int rear=0;//입구 0으로 초기화
        int QUE_LEN=4;//배열 크기
        
        Object[] queArr = new Object[QUE_LEN];
        
    public boolean offer(Object data) {//추가
        if(NextIdx(rear) == front)//입구와 출구의 인덱스가 하나 차이라면
        {
            System.out.println("큐가 꽉찾습니다.");
            return false;
        }
        rear = NextIdx(rear);
        queArr[rear] = data;
        return true;
    }
    
    public Object poll() {//삭제+반환
        if(isEmpty())
        {
            System.out.println("큐가 비어있습니다.");
            return null;
        }
        front = NextIdx(front);
        return queArr[front];
    }
    
    public Object peek() {//반환
        if(isEmpty())
        {
            System.out.println("큐가 비어있습니다.");
            return null;
            //System.exit(0);//시스템종료
        }
        return queArr[NextIdx(front)];    
    }
    
    public int NextIdx(int Idx)
    {
        if(Idx == QUE_LEN-1)//배열크기-1
            return 0;//배열의 첫번째 인덱스
        else
            return Idx+1;
    }
    public boolean isEmpty() {
        return front == rear;//인덱스의 위치가 같다면 큐가 비어있는것이다.
    }
}

2. LinkedList 기반 큐의 직접 구현 ( Node 객체 ) 

LinkedList 를 안다면 쉽게 구현할 수 있다. head가 출구이고 tail이 입구이다.

package queue;
 
public class LinkedListQueue {
    private Node head;
    private Node tail;
    private int size = 0;
    
    public class Node{
        private Object data;
        private Node next;
        
        public Node(Object input) {
            this.data = input;
            this.next = null;
        }
    }
    public boolean offer(Object input){
        
        Node newNode = new Node(input);
        
        if(isEmpty()){
            head=newNode;
            tail=newNode;
        }else {
             tail.next = newNode;
             tail = newNode;
        }
        size++;
        return true;
    }
    
    public Object peek() {
        if(isEmpty()){
            return null;
        }else
            return head.data;
        }
    
    public Object poll(){
        if(!isEmpty()){
               Node temp = head;
               head = temp.next;
               
               Object returnData = temp.data;
               
               temp = null;
               
               size--;
               
               return returnData;
        }else{
            return null;
        }
       }
    
    public boolean isEmpty() {
        return size() == 0;
        }
    
    public int size(){
        return size;
    }
  }    

3. 자바 라이브러리

-Queue 인터페이스를 구현한 LinkedList 클래스 활용

package queue;
import java.util.LinkedList;
public class LinkedListStackApi {
    public static void main(String[] args) {
        LinkedList<String> queue = new LinkedList();
        //큐 인터페이스를 구현한 LinkedList
        queue.offer("0");
        queue.offer("1");
        queue.offer("2");
        
        System.out.println("= java queue api peek=");
        
        System.out.println(queue.peek());//마지막 값 리턴
        
        System.out.println("= java queue api poll=");
        
        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
        
    }
}