JAVA - Queue이란? 그리고 구현

Queue 란

• Stack과 다르게 데이터가 들어간 순서대로 나오는 즉 FIFO(First In First Out) 자료구조입니다.

 

• offer()
  • 순차 보관
• poll()
  • 가장 먼저 보관되어 있는 값 추출
• peek()
  • 가장 먼저 보관되어 있는 값 확인

 

Queue 구현 코드

public class Queue {
    private int size = 2;
    private int head;
    private int tail;
    private int[] elements;

    public Queue() {
        this.head = 0;
        this.tail = 0;
        this.elements = new int [size];
    }

    public boolean isEmpty(){
        return head == tail;
    }

    public boolean isFull(){
        if(tail == elements.length){
            return true;
        }
        return false;
    }

    public void offer(int data){
        if(isFull()){
            size = tail + 5;
            int [] extendElements = new int[size];

            for (int i = 0; i < tail; i++) {
                extendElements[i] = elements[i];
            }
            elements = extendElements;
        }
        this.elements[tail++] = data;
    }

    public int poll(){
        if (isEmpty()) {
            System.out.println("데이터가 존재하지 않습니다.");
            return -1;
        }

        int result = elements[head++];
        return result;
    }

    public int peek(){
        if(isEmpty()){
            System.out.println("데이터가 존재하지 않습니다.");
            return -1;
        }else{
            int result = this.elements[head];
            return result;
        }
    }

    public void print(){
        while (tail - head > 0) {
            System.out.println(elements[head]);
            head++;
        }
    }
}

 

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.offer(1);
        System.out.println("poll() --> " + queue.poll()); // 1
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println("peek() --> " + queue.peek()); // 2
        queue.offer(5);

        queue.print();
        // 2
        // 3
        // 4
        // 5
    }
}

 

과제 4. 앞서 만든 ListNode를 사용해서 Queue를 구현하세요.

• LinkedList로 ListNode 구현방법 >> 이동
• 위의 글을 이해해야지 해당 글을 이해할 수 있으니 꼭 읽어보셔야 합니다.

구현 코드

public class ListNodeQueue {
    private ListNode head;
    private LinkedList linkedList;
    private int position;

    public ListNodeQueue() {
        this.linkedList = new LinkedList();
    }

    public void offer(int data){
        if(head == null){
            head = new ListNode(data);
        }else{
            linkedList.add(head, new ListNode(data), ++position);
        }
    }

    public void poll(){
        --position;
        head = linkedList.remove(head, 0);
    }

    public void print(){
        ListNode node = head;

        while (node != null) {
            System.out.println(node.data);
            node = node.next;
        }
    }
}

public class ListNodeQueueExample {
    public static void main(String[] args) {
        ListNodeQueue listNodeQueue = new ListNodeQueue();
        listNodeQueue.offer(1);
        listNodeQueue.offer(2);
        listNodeQueue.offer(3);
        listNodeQueue.poll(); // 가장 첫번째 요소 삭제 ==> 1 삭제
        listNodeQueue.offer(4);
        listNodeQueue.offer(5);

        listNodeQueue.print();
        // 2
        // 3
        // 4
        // 5
    }
}