Queue - 큐의 개념과 특성들

1. Queue의 정의

- Queue는 먼저 들어간 데이터가 먼저 나오는 자료구조이다.

- 입구와 출구가 다르다.

- 파이프 구조이다.

2. Queue의 기본연산

offer   - 큐의 입구에 데이터 추가

poll    - 큐의 출구로부터 데이터의 반환과 + 삭제

peek  - 큐의 출구로부터 데이터의 반환

isEmpty - 데이터의 유무 확인

Method	Description
boolean isEmpty()	Queue가 비어있는지 알려준다.
boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환.
Object poll()	Queue에서 객체를 꺼내서 반환+삭제. 비어있으면 null을 반환.
Object peek()	삭제없이 요소를 읽어 온다. Queue가 비어있으며 null을 반환.
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환. 저장공간이 부족하면 lllegalStateException발생
Object remove()	Queue에서 객체를 꺼내 반환+삭제. 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어온다. Queue가 비었을때 NoSuchElementException 발생

3. Queue의 특성

1) 상수시간에 i번째 항목에 접근 불가

2) 하지만 Queue의 데이터 추가 삭제 연산은 상수시간 가능

4. Queue의 구현

1) 원형 큐(링 버퍼) - 배열 기반

     2) ArrayList 구현은 삭제시 삭제된 공간을 채우려하기 때문에 비효율적이라 구현에서 제외한다.

3) LinkedList로 직접 구현(Node 객체) 

4) 자바 라이브러리

     -Queue 인터페이스를 구현한 LinkedList 클래스 활용

5. Queue 구현의 비교

     

1) 공통점 - 추가, 삭제가 상수시간 연산 가능

2) 배열 기반  - 배열의 크기가 정해져 있기에 데이터가 증가하면 배열을 복사해줘야 하는점

3) 연결 리스트 - 크기에 제한 없음