자료구조 다시보기- queue

오늘의 TIL 힘차게 나와주세요 ~~~~~~!!!

참고 1 - [자료구조 알고리즘] Queue 구현하기 in Java

1. queue

스택과 다르게 queue 는 FIFO 구조 이다.
사람들이 줄 서 있는 것과 같다. 늦게 온 사람은 맨 뒤에 서고, 맨 앞에 미리 서있던 사람부터 빠진다.

2. queue 자료구조를 사용하는 예시

• 하나의 자원을 공유하는 경우: 프린터 대기 리스트나 CPU
• Mp3 같은 어플리케이션에서 버퍼로 쓰인다.

3. java 로 구현.

스택은 입구와 출구가 같은 꼴이었기에 top 만 기억하면 됐는데, 큐는 서로 다르기에 맨 앞 과 맨 뒤 자료를 기억하는 포인터가 필요하다.

package example;

import java.util.NoSuchElementException;

public class QueueTest<T> {
    class Node<T> {
        private T data;
        private Node<T> nextNode;
        public Node(T data){
            this.data =data;
        }
    }
    private Node<T> first;
    private Node<T> last; //앞부터빠지니까 first 노드를 바꾸기 위해모든 노드들이 다음 노드를 알아야함. -> 마지막에 들어오는 노드 위해 last 노드 갱신해갈 필요 있음.

    public void add(T data) {
        Node<T> newNode = new Node<T>(data);
        if (first ==null) {
            first = newNode;  //first 비워져있으면 거기 채움.
        }
        if(last !=null){
            last.nextNode = newNode;
        }
        last = newNode;
    }

    public T remove(){
        if(first==null){
            throw new NoSuchElementException();
        }
        T value =first.data;
        first =first.nextNode;  // 여기를 위해 lastnode 알아야함
        return value;
    }

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

    public boolean isEmpty(){
        return first ==null ? true: false;
    }

}

  @Test
    void queueTest(){
        QueueTest<Integer> queue = new QueueTest<Integer>();
        queue.add(3);
        queue.add(4);
        queue.add(5);
        queue.add(6);
        queue.remove();
        assertThat(queue.peek()).isEqualTo(4);
    }

    @Test
    void isEmptyTest(){
        QueueTest<Integer> queue = new QueueTest<Integer>();
        assertThat(queue.isEmpty()).isTrue();
        queue.add(3);
        queue.remove();
        queue.add(4);
        queue.add(5);
        assertThat(queue.isEmpty()).isFalse();
        queue.remove();
        queue.remove();
        assertThat(queue.isEmpty()).isTrue();
    }