[자료구조] 자바 Queue 정리

 

Queue(큐)

 

선입선출(FIFO : First in First Out) 구조

 

삽입된 순서대로 데이터들이 나열되고 가장 먼저 삽입된 데이터가 가장 먼저 나오게 되는 구조이다.

가장 먼저 저장된 데이터를 front, 가장 나중에 저장된 데이터를 rear라고 구분하고, 데이터의 삽입은 front, 데이터의 삭제는 rear에서 이루어지게 된다.

---

 

주요 메서드

메서드	내용
boolean add(Object o)	지정된 데이터를 큐에 추가
boolean offer(Object o)	큐에 데이터를 저장
Object remove()	큐에서 데이터를 꺼내 반환 (비어있을 시 NoSuchElementException)
Object poll()	큐에서 데이터를 꺼내 반환 (비어있을 시 null 반환)
Object element()	데이터를 읽어온다. 삭제x (비어있을 시 NoSuchElementException)
Object element()	데이터를 읽어온다. 삭제x (비어있을 시 null 반환)

 

---

 

 

• Queue 구현

public class Queue<T> {

      class Node<T> {
          private T data;
          private Node<T> next;

          public Node(T data) {
              this.data = data;
          }
      }

      private Node<T> front;
      private Node<T> rear;

      public void enqueue(T item) {
          Node<T> t = new Node<T>(item);

          if (rear != null) {
              rear.next = t;
          }
          rear = t;
          if (front == null) {
              front = rear;
          }
      }

      public T dequeue() {
          if (front == null) {
              throw new NoSuchElementException();
          }
          T data = front.data;
          front = front.next;
          return data;
      }

      public T peek() {
          if (front == null) {
              System.out.println("empty");
          }
          return front.data;
      }

      public boolean isEmpty() {
          return front == null;
      }

      public static void main(String[] args) {

          Queue<Integer> q = new Queue<Integer>();
          q.enqueue(1);
          q.enqueue(2);
          q.enqueue(3);
          q.enqueue(4);

          System.out.println(q.dequeue());
          System.out.println(q.dequeue());
          System.out.println(q.peek());
          System.out.println(q.isEmpty());
          System.out.println(q.dequeue());
          System.out.println(q.dequeue());
          System.out.println(q.isEmpty());
          // System.out.println(q.dequeue());
      }
   }

 

• enqueue : rear가 null 값이 아니면 생성된 노드를 rear에 삽입한다. front가 null이면 rear가 front값이 되도록 한다.
• dequeue : front 데이터가 먼저 꺼내지도록 하고 다음 값으로 front를 채운다.
• peek : front의 데이터값이 보여지도록 한다.
• isEmpty : front값이 null이면 큐는 비어있게 된다.