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) 연결 리스트 - 크기에 제한 없음
'Basic > 자료구조,알고리즘' 카테고리의 다른 글
Deque의 개념과 구현 (0) | 2019.01.09 |
---|---|
Queue의 다양한 구현 (0) | 2018.12.08 |
Stack의 다양한 구현 (0) | 2018.12.07 |
Stack 스택의 개념과 특성들 (0) | 2018.12.06 |
원형 연결리스트(CircularLinkedList)직접 구현 (0) | 2018.12.06 |