[Data Structure기초] Queue

 

Queue(큐)

- 줄을 지어 순서대로 처리되는 자료구조

- 먼저 들어온 데이터가 가장 먼저 나감 (First In First Out , 선입선출)

- 마트의 재고관리 부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) , 캐시 메모리, 버퍼 등에서 사용됨

Stack 시간복잡도

삽입( enqueue ) : O(1) 
삭제( dequeue ) : O(1) 

 

연산
enqueue(Object data)	데이터를 넣는 함수 ( add(data), offer(data) )
dequeue()	데이터를 꺼내는 함수( remove(), poll() )
peek()	요소를 읽어옴, 비어있으면 null
isEmpty()	큐가 비어있는지 확인
isFull()	큐가 꽉 차있는지 확인
element()	큐가 비었을 때 요소를 읽어옴

 

//큐 사용예제
    Queue queue = new LinkedList(); //Queue는 인터페이스, 다형성을 이용해서 LinkedList를 사용하는 것이 편리

    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    queue.add(5);
    System.out.println(queue);

    System.out.println(queue.poll());
    System.out.println(queue);

    System.out.println(queue.poll());
    System.out.println(queue);

    System.out.println(queue.peek());//가장 먼저 들어온 요소
    System.out.println(queue);

    System.out.println(queue.contains(3));
    System.out.println(queue.size());
    System.out.println(queue.isEmpty());

    queue.clear();
    System.out.println(queue);
    System.out.println(queue.poll()); //아무것도 없으면 null

 

장점

- 선입선출(FIFO) 원칙 : 특정 작업을 처리하는 순서를 보장하는 데 유용하다.
-  크기 조절 가능 : 큐는 일반적으로 동적으로 크기를 조절할 수 있어, 필요에 따라 크기를 늘리거나 줄일 수 있다.
-  대기열 관리 : 큐는 대기열을 관리하는 데에 매우 유용하다. 데이터를 삽입, 삭제하는데 모든 데이터를 순회할 필요가 없기 때문이다.

- 자바에서는 스택을 기본 자료 구조로 제공

 

단점

- 중간 항목 접근 어려움 : 큐는 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나기 때문에 중간에 위치한 특정 항목에 접근하기가 어렵다. 큐에서 특정 항목을 삭제하기 위해서는 그 앞에 위치한 모든 항목들을 먼저 삭제해야 한다.
- 크기 제한 : 큐는 일반적으로 동적으로 크기를 조절할 수 있지만, 특정 구현에서는 크기가 제한되어 있을 수 있습니다. 큐가 가득 찬 상태에서 더 많은 항목을 삽입하려고 하면 오버플로우(Overflow)가 발생할 수 있다.
- 선형 탐색 시간 : 특정 항목을 찾기 위해서는 큐를 선형적으로 탐색해야 한다. 따라서, 큐에서 특정 항목을 찾는데 걸리는 시간은 큐의 크기에 비례한다.

 

 

관련link

https://velog.io/@db_jam/%EC%9E%90%EB%B0%94-%ED%81%90Queue-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC

[Java] 큐(Queue) 자료구조 정리

https://hoehen-flug.tistory.com/31

[자료구조] 큐(Queue) 자료구조 알아보기 & Java 예제 코드

https://you88.tistory.com/30

[자료구조 Java] 큐(Queue) 개념 정리 + 자바로 구현하기