학습목표

• Queue 개념과 ADT
• Queue 구현
• Queue 클래스

Queue 개념과 ADT

간단한 큐의 개념은 먼저 들어간 데이터가 먼저 나온다는 것.
하지만 큐를 통해 스레드/네트워크 스케줄링, 메세지 관리, 정렬 등을 구현할 수 있다.

• Queue - 데이터는 한 방향으로만 삽입되고, 한 방향으로만 나온다.
• Deque - 데이터는 양방향으로 삽입과 삭제가 가능하다.

ADT

• enQueue : 삽입
• deQueue : 삭제
• peek : 확인
• isEmpty : 확인
• push_front/back : deque front/rear 삽입
• pop_front/back : deque front/rear 제거

Linked List Queue 구현

public class implementQueue {
    static class Queue<T> {
        static class Node<T> {
            private T data;
            private Node<T> next;

            public Node(T data) {
                this.data = data;
            }
        }
        private Node<T> first;
        private Node<T> last;

        public void add(T item) {
            Node<T> t = new Node<>(item);
            if (last != null) {
                last.next = t;
            }
            last = t;
            if (first == null)
                first = last;
        }

        public T remove() {
            if (first == null) {
                throw new NoSuchElementException();
            }

            T data = first.data;
            first = first.next;

            if (first == null) {
                last = null;
            }
            return data;
        }

        public T peek() {
            if (first == null) {
                throw new NoSuchElementException();
            }
            return first.data;
        }

        public boolean isEmpty() {
            return first == null;
        }
    }
    public static void main(String[] args) {
        Queue<Integer> q = new Queue<>();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q.remove()); // 1
        System.out.println(q.remove()); // 2
        System.out.println(q.peek()); // 3
        System.out.println(q.remove()); // 3
        System.out.println(q.isEmpty()); // true
    }
}

Linked list Dequeue 구현

Queue 라이브러리 사용

public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 10; i++) {
            queue.add(i); // 요소 추가, 예외 없음
        }
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println(queue.peek()); // 헤드 반환
        queue.poll(); // 헤드 제거 후 반환
        queue.offer(12); // 요소 추가, 예외 발생, 고정 크기의 경우 사용
        queue.remove(12); // 헤드 제거 후 반환, 없을 시 예외 발생
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
    }

출력

• 1 2 3 4 5 6 7 8 9 10
• 1
• 2 3 4 5 6 7 8 9 10