[자료구조] Queue

Queue

• 선입 선출 구조의 자료구조 이다.
  • FIFO(First In First Out)
  • 가장 먼저 입력한 데이터를 가장 먼저 출력한다.
• 데이터의 입출력 방향이 다르다.
  • front : 출력
  • rear : 입력
• 데이터를 하나씩 입력하고 하나씩 빼야 한다. - 여러개의 데이터를 동시에 처리 할 수 없다.
• 큐에 데이터를 입력하는 것을 'enqueue', 데이터를 출력하는 것을 'dequeue'라고 한다.
• 현실에서 일반적인 대기줄을 생각하면 된다. 가장 먼저 대기줄에 선 사람이 우선 순위가 가장 높다.
• 컴퓨터의 장치들 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도, 시간의 차이를 극복하기 위해
  임시 기억 장치의 자료 구조로 Queue를 사용한다, 이것을 버퍼(buffer)라고 한다.
  • 프린터로 인쇄를 하려고할때 CPU는 처리속도가 빠르고, 프린터는 느리기 때문에 cpu는 인쇄에 필요한 데이터를 queue에 저장하고 다른 작업을하고 프린터는 queue에 쌓인 데이터를 받아 처리한다.

 

JAVA에서 Queue

• 자바에서 Queue를 인터페이스로 제공, Queue는 collection을 상속 받는다.
• LinkedList를 통해 Queue를 구현할수 있다.

Queue 상속

import java.util.LinkedList;
import java.util.Queue;

// queue 생성, LinkedList를 활용해야한다.
// Queue는 collection을 상속받고 있다.
Queue<String> queue = new LinkedList<>();

// 데이터 입력(enqueue), add()와 offer() 사용 가능
queue.add("first data");
queue.add("second data");
queue.offer("third data");
System.out.println("----------------");
System.out.println(queue);

// 데이터 출력(dequeue) 1
System.out.println("----------------");
System.out.println("제일 먼저 입력한 데이터를 출력");
System.out.println("데이터를 출력하고 queue에서 삭제한다. - "+queue.poll());
System.out.println(queue);

// 데이터 출력(dequeue) 2
System.out.println("----------------");
System.out.println("데이터를 출력하고 queue에서 삭제한다. - "+queue.remove());
System.out.println(queue);

// 데이터 사이즈 출력
queue.add("first data"); // 데이터 입력
queue.add("second data"); // 데이터 입력
System.out.println(queue);
System.out.println("----------------");
System.out.println("큐 크기 반환 : "+queue.size());

// 가장 먼저 입력한 데이터 검색 -> 제일 먼저 출력될 데이터
System.out.println("----------------");
System.out.println("Queue의 가장 앞에 있는 데이터 검색 -> 가장 먼저 출력될 데이터를 뜻한다.");
System.out.println(queue.peek()); // Queue에서 삭제하기 않고 데이터만 검색

// queue 비우기, 전체 삭제
queue.clear();
System.out.println("----------------");
System.out.println("데이터 전체 삭제");
System.out.println(queue);

// queue가 비었을때 출력을 하면 null이 반환 된다.
System.out.println("----------------");
System.out.println("queue가 비었을때 출력을 하면 "+queue.poll()+" 반환");

/*

[first data, second data, third data]
----------------
제일 먼저 입력한 데이터를 출력
데이터를 출력하고 queue에서 삭제한다. - first data
[second data, third data]
----------------
데이터를 출력하고 queue에서 삭제한다. - second data
[third data]
----------------
[third data, first data, second data]
큐 크기 반환 : 3
----------------
Queue의 가장 앞에 있는 데이터 검색 -> 가장 먼저 출력될 데이터를 뜻한다.
third data
----------------
데이터 전체 삭제
[]
----------------
queue가 비었을때 출력을 하면 null 반환

*/

JAVA로 Queue 구현

import java.util.*;

public class QueueEx { 
  
  // ArrayList로 구현
  private ArrayList<Integer> listQueue = new ArrayList<Integer>();

  // 데이터 입력 - enqueue
  public void add(Integer data) {
    listQueue.add(data);
  }

  // 데이터 출력 - dequeue
  public Integer poll() {
    if(listQueue.size() == 0) {
      return null;
    }else {
    return listQueue.remove(0);
    }
  }

  // queue 사이즈 반환
  public int size() {
    return listQueue.size();
  }

  // 가장 먼저 입력한 데이터 반환
  public Integer peek() {
    if(listQueue.size() == 0) {
      return null;
    }else {
      return listQueue.get(0);
    }
  }

  // queue를 String으로 반환
  public String show() {
    return listQueue.toString();
  }

  // queue를 비운다, 데이터 전체 삭제
  public void clear() { 
		listQueue.clear(); 
	}
}