[스터디 4주차] Queue

Queue란?

- FIFO(First In First Out)의 형태, 먼저 들어온 데이터가 가장 먼저 나가는 구조이다.

- 큐는 한 쪽 끝은 front로 지정하여 삭제 연산만 수행

- 다른 한쪽 끝은 rear로 지정하여 삽입 연산만 수행

- Enqueue: 큐 맨 뒤에 데이터 추가

- Dequeue: 큐 맨 앞쪽의 데이터 삭제 

 

https://coding-factory.tistory.com/602

Queue 구현

(1) Array

// Array 로 queue 구현 하기 

public class ArrayQueue {

    int[] elements;
    private int front = 0;
    private int rear = 0;
    private int size = 2;
    private int exSize =0;

    public ArrayQueue(){
        elements = new int[size];
    }
    /**
     * 데이터 삽입
     */
    public void offer(int data){
        if(rear == elements.length){
            System.out.println("[사이즈 확장] Size : " + size +" -> " + (rear+5));
            exSize = rear +5;
            int[] extendElements = new int[exSize];
            // migrate
            for(int i=0; i<rear; i++){
                extendElements[i] = elements[i];
            }
            elements = extendElements;
        }

        elements[rear++] = data;
        System.out.println( "데이터 추가 : "+data + " -> front : " + front +" , rear : "+ rear);

    }


    /**
     * 맨 앞의 데이터 출력
     */
    public int peek(){
        return elements[front];
    }

    /**
     * 데이터 출력후 삭제
     */
    public int poll(){
        if(front == rear) {
            System.out.println("데이터가 존재하지 않습니다");
            return -1;
        }
        int data = elements[front];
        elements[front++] = 0;
        return data;

    }

    /**
     * 맨앞의 데이터 삭제
     */
    public void remove(){
        if(front == rear) {
            System.out.println("데이터가 존재하지 않습니다");
        }
        System.out.println("데이터 삭제 : " + elements[front]);
        elements[front] = 0;
        front++;
    }

    /**
     * 모든 데이터 삭제
     */
    public void clear(){
        elements = new int[size];
        front=0;
        rear=0;
        System.out.println("모든 데이터 삭제 완료");
    }

}

 

(2) LinkedList

// Linked list로 queue 구현하기 
public class ListNodeQueue {

    private ListNode head;
    private int front=0;
    private int rear=0;

    public ListNodeQueue(){}

    /**
     * 데이터 삽입
     */
    public void offer(int data){
        if(head==null){
            head = new ListNode(data);
        }
        System.out.println( "데이터 추가 : "+data + " -> front : " + front +" , rear : "+ rear);
        head.add(head, new ListNode(data), rear++);
    }


    /**
     * 맨 앞의 데이터 출력
     */
    public int peek(){
        if(front == rear) {
            System.out.println("데이터가 존재하지 않습니다");
            return -1;
        }
        return head.data;
    }

    /**
     * 데이터 출력후 삭제
     */
    public int poll(){
        if(front == rear) {
            System.out.println("데이터가 존재하지 않습니다");
            return -1;
        }
        rear--;
        ListNode delNode = head;
        int data = delNode.data;
        head = delNode.remove(head,0);
        return data;
    }

    /**
     * 맨앞의 데이터 삭제
     */
    public void remove(){
        if(front == rear) {
            System.out.println("데이터가 존재하지 않습니다");
            return;
        }
        rear--;
        ListNode delNode = head;
        head = delNode.remove(head,0);
    }

    /**
     * 모든 데이터 삭제
     */
    public void clear(){

        while(front <= rear--){
            head= head.remove(head,rear);

            if(front == rear ) break;
        }
        System.out.println("모든 데이터 삭제 완료");
    }

}