[Data Structure] Java 큐(Queue) 사용

• 이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다.

Queue란?

• 큐는 출구와 입구가 명백히 존재하여 데이터를 담는 방식의 자료구조입니다.
• 큐의 주요 특징은 First In, First Out (FIFO) 구조를 갖습니다.

배열로 큐 구현

public class Queue {

public class Queue {

    final int MAX_SIZE = 100;
    int[] arr;
    int size;

    public Queue() {
        arr = new int[MAX_SIZE];
        size = 0;
    }

    void push(int data){
        arr[size++] = data;
    }

    int front(){
        return arr[0];
    }

    int pop(){
        if(size == 0){
            return 0;
        }
        else{
            for(int i=1;i<size;i++){
                arr[i-1] = arr[i];
            }
            size--;
            return 1;
        }
    }

    public int getSize() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {

        Queue queue = new Queue();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.getSize());        // 3

        System.out.println(queue.front());          // 1
        queue.pop();
        System.out.println(queue.front());          // 2
        queue.pop();
        System.out.println(queue.front());          // 3
        queue.pop();
    }
}

노드로 큐 구현

public class ListNode {
    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        next = null;
    }
}

다음 클래스는 노드를 구현하는 코드입니다.

public class ListNodeQueue {

    ListNode head;
    int size;

    public ListNodeQueue() {
        head = null;
        size = 0;
    }

    void push(int data){
        ListNode node = head;

        if(size == 0){
            node = new ListNode(data);
            head = node;
        }else{

            while (node.next!=null){
                node = node.next;
            }
            node.next = new ListNode(data);
        }
        size++;
    }

    int pop(){
        if(size == 0){
            return 0;
        }
        else {
            head = head.next;
            size--;
            return 1;
        }
    }

    int front(){
        return head.data;
    }

    public int getSize() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {

        ListNodeQueue queue = new ListNodeQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.front());      // 1
        queue.pop();
        System.out.println(queue.front());      // 2
        queue.pop();
        System.out.println(queue.front());      // 3
        queue.pop();
    }
}