4주차 과제: Queue

 

Queue를 구현

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out) 자료구조이다.

​

출처: https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

 

구현하는 방법은 배열과 LinkedList 두가지 가 있다.​

1. 배열

public class Queue {
    private int[] values;

    public Queue() {

    }

    public Queue(int[] values) {
        this.values = values;
    }

    //인큐 : 데이터 삽입
    public void enQueue(int data) {
        //맨 처음 들어오는 데이터에 대한 처리
        if (values == null) {
            values = new int[1];
            values[0] = data;
            return;
        }

        //정수 배열의 크기를 늘려준 뒤 마지막에 데이터를 넣어준다.(스택과 동일)
        values = Arrays.copyOf(values, values.length + 1);
        values[values.length - 1] = data;
    }

    //디큐 : 데이터 삭제
    public int deQueue() {
        //데이터가 없을 경우 처리
        if (values.length - 1 == -1) {
            throw new ArrayIndexOutOfBoundsException();
        }

        //배열의 처음 데이터를 반환한 뒤, 정수 배열을 줄여준다.
        int popData = values[0];

        //배열 Index를 앞으로 당겨서 빈 공간을 채워준다.
        int[] tempArr = new int[values.length - 1];
        System.arraycopy(values, 1, tempArr, 0, tempArr.length);

        values = tempArr;
        return popData;
    }

    //테스트 출력용 함수
    public String toString() {
        StringBuilder str = new StringBuilder();

        for (int value : values) {
            str.append(value).append(" ");
        }

        return str.toString();
    }


}

 

데모

public class QueueDemo {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enQueue(1);
        System.out.println("enQueue 1 -> " + queue);
        queue.enQueue(2);
        System.out.println("enQueue 2 -> " + queue);
        queue.enQueue(3);
        System.out.println("enQueue 3 -> " + queue);
        queue.enQueue(4);
        System.out.println("enQueue 4 -> " + queue);
        queue.enQueue(5);
        System.out.println("enQueue 5 -> " + queue);
        queue.enQueue(6);
        System.out.println("enQueue 6 -> " + queue);


        queue.deQueue();
        System.out.println("deQueue  -> " + queue);
        queue.deQueue();
        System.out.println("deQueue  -> " + queue);
        queue.deQueue();
        System.out.println("deQueue  -> " + queue);
        queue.deQueue();
        System.out.println("deQueue  -> " + queue);

    }
}

 

// 출력 결과
enQueue 1 -> 1 
enQueue 2 -> 1 2 
enQueue 3 -> 1 2 3 
enQueue 4 -> 1 2 3 4 
enQueue 5 -> 1 2 3 4 5 
enQueue 6 -> 1 2 3 4 5 6 
deQueue  -> 2 3 4 5 6 
deQueue  -> 3 4 5 6 
deQueue  -> 4 5 6 
deQueue  -> 5 6 

 

2. ListNode

public class LinkedListQueue {

    ListNode head;

    public LinkedListQueue() {
    }

    public LinkedListQueue(ListNode head) {
        this.head = head;
    }


    public void enQueue(int data) {
        ListNode pushNode = new ListNode(data);
        this.enQueueNode(pushNode);
    }

    public int deQueue() {
        ListNode popNode = this.deQueueNode();

        if (popNode == null) {
            throw new ArrayIndexOutOfBoundsException();
        }

        return popNode.getData();
    }


    private void enQueueNode(ListNode pushNode) {
        ListNode tempNode = head;

        if (head == null) {
            head = pushNode;
        } else {

            while (tempNode.getPoint() != null) {
                tempNode = tempNode.getPoint();
            }

            //A(tempNode) - > B(addNode) -> null 형태
            tempNode.updateNextPoint(pushNode);
            pushNode.updateNextPoint(null);
        }
    }

    private ListNode deQueueNode() {
        ListNode tempNode = head;

        if (head == null) {
            return null;
        }

        head = null;
        head = tempNode.getPoint();

        return tempNode;
    }

    //결과값 출력함수.
    public String toString() {
        StringBuilder str = new StringBuilder();
        ListNode tempNode = head;

        //헤더가 없을 경우 그냥 리턴
        if (tempNode == null) {
            return null;
        }

        while (true) {
            str.append(tempNode.getData()).append(" ");

            if (tempNode.getPoint() == null) {
                break;
            }

            tempNode = tempNode.getPoint();
        }
        return str.toString();
    }

}

 

데모

public class LinkedListQueueDemo {
    public static void main(String[] args) {
        LinkedListQueue linkedListQueue = new LinkedListQueue();

        linkedListQueue.enQueue(1);
        System.out.println("enQueue 1 -> " + linkedListQueue);
        linkedListQueue.enQueue(2);
        System.out.println("enQueue 2 -> " + linkedListQueue);
        linkedListQueue.enQueue(3);
        System.out.println("enQueue 3 -> " + linkedListQueue);
        linkedListQueue.enQueue(4);
        System.out.println("enQueue 4 -> " + linkedListQueue);
        linkedListQueue.enQueue(5);
        System.out.println("enQueue 5 -> " + linkedListQueue);

        linkedListQueue.deQueue();
        System.out.println("deQueue -> " + linkedListQueue);
        linkedListQueue.deQueue();
        System.out.println("deQueue -> " + linkedListQueue);
        linkedListQueue.deQueue();
        System.out.println("deQueue -> " + linkedListQueue);
        linkedListQueue.deQueue();
        System.out.println("deQueue -> " + linkedListQueue);

    }
}

 

// 출력결과
enQueue 1 -> 1 
enQueue 2 -> 1 2 
enQueue 3 -> 1 2 3 
enQueue 4 -> 1 2 3 4 
enQueue 5 -> 1 2 3 4 5 
deQueue -> 2 3 4 5 
deQueue -> 3 4 5 
deQueue -> 4 5 
deQueue -> 5 

 

 

차이점

​배열은 인덱스가 있는 탐색하기 편하다.

LinkedList 는 생성 삭제에서 링크 수정만으로 해결 할 수 있다.

​

​

참고:

• https://blog.naver.com/swoh1227/222162389788