큐(queue)
- 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.
- first in first out(선입선출) : 처음 들어온 것이 먼저 나간다.
- 데이터가 삽입되는 곳 rear(큐의 요소 중 제일 마지막 부분), 데이터가 제거(추출)되는 곳 front(큐 내의 요소 중 가장 첫번쨰 부분)
- 데이터 접근, 삽입, 삭제가 빠르다.
- 중간에 위치한 데이터에 대한 접근이 불가능하다.
- java에서 큐는 인터페이스의 역할을 수행하며 ArrayDeque, LinkedList, PriorityQueue등을 통해서 구현체를 구현
- enqueue : 큐의 맨 뒤(rear)에서 데이터를 '추가'하는 연산을 의미
- 메서드 : java = add(e), offer(e)/ js = push(e)
- rear : 큐의 '맨뒤'에 위치한 데이터를 가르키는 포인터
- 메서드 : java = remove(), poll() / js = splice(0,1) or shift()
- front : 쿠의 '맨 앞'에 위치한 데이터를 가리키는 포인터
- 메서드 : java = element(), peek() / js = 없는듯...?
- Dequeue : 큐의 맨 앞에 위치한 데이터를 가르키는 포인터
java queue의 메서드
- offer(e) : 큐의 맨 뒤에 지정된 요소 추가. 큐가 가득차서 요소를 추가할 수 없는 경우 false 반환
- add() : 큐의 맨뒤에 지정된 요소를 추가. 큐가 가득차서 요소를 추가할 수 없을 경우 예외 발생
- poll() ->
원본 배열을 바꾸는가..? 궁굼: 큐의 맨 앞에서 요소를 제거하고 반환. 큐가 비어있으면 null 반환- peek() : 큐의 맨앞에서 요소를 반환합니다. 큐가 비어 있으면 null 반환
- clear() : 큐의 모든 요소를 제거
선형 큐(Linear Queue)
- 선형 배열을 사용하여 구현된 큐
- 삽입을 위해서는 계속해서 요소들을 이동시켜야 한다.
원형 큐(circular queue)
front: 맨 첫번쨰 요소 바로 앞을 가리킴rear: 마지막 요소를 가리킴- 큐 empty 상태 : front ===rear
- 큐 full 상태 : front === (rear+1) % max_queue_size
- front :0 , rear : 7 => (7+1) %8 = 0
- 공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워둠
시간 복잡도 : O(1)
- 큐는 front와 rear의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 원소 삽입, 삭제의 시작 복잡도는 O(1)이다.
활용
- 데이터를 입력된 순서대로 처리해야 할때
- BFS 알고리즘
- 프로세스 관리-> 운영체제에서 프로세스를 관리할떄, 프로세스가 CPU를 할당받기 위해 대기사는 큐를 사용
- 대기 순서 관리 -> 은행에서 손님이 대기열에 줄을 서서 업무 처리하는 것..
- 캐시(cache) -> 캐시 메모리에서 데이터를 저장하고 꺼낼 때, 가장 오래된 데이터를 먼저 삭제하는 정책을 구현할 때 큐 사용
장단점
- 장점 : 데이터의 순서가 중요한 작업에 적합
- 단점 : 큐의 크기가 고정되어 있으면 데이터가 가득차면 더이상 삽입이 불가능
덱(Deque - Ended Queue)
- 양쪽 front, rear에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조
- 선입선출, 후입선출 개념이 모두 적용
연속적인 메모리를 기반으로 하는 시퀀스 컨테이너- 선언 이후 크기를 줄이거나 늘릴 수 있는
가변적 크기를 가짐 - 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다. But, 성능이 좋지 않다.
- 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
- 중간에서의 삽입 삭제는 어렵다.
- 스택, 큐에 비해 비교적 구현이 어렵다.
- Java에서 덱은 java.util.Deque 인터페이스를 이용해 구현할 수 있습니다.
java deque의 메서드
- addFirst(e) : 덱의 맨
앞에 지정된 요소를추가- addLast(e) : 덱의 맨
뒤에 지정된 요소추가- removeFirst() : 덱의 맨
앞에서 요소를제거하고 반환. 덱이 비어 있으면 예외 발생- removeLast() : 덱의 맨
뒤에서 요소를제거하고 반환. 덱이 비어있으면 예외발생- getFirst() : 덱의 맨
앞에서 요소를반환. 덱이 비어 있으면 예외 발생- getLast() : 덱의 맨
뒤에서 요소를반환. 덱이 비어 있으면 예외 발생
시간복잡도 : O(1)
- 삽입 삭제 연산은 index를 통해 요소들에 탐색이 가능하기에 O(1)의 시간 복잡도를 가짐
활용
- 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
- 데이터의 크기가 가변적일 때
- 양방향 큐
- 회문판별 : 덱은 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 검사할때 사용
- 최댓값/최소값 검색 : 덱은 슬라이딩 윈도우(sliding window)알고리즘을 이용해 최대값/최소값을 검색할 때 사용
장단점
- 장점 : 양쪽 끝에서의 삽입과 삭제가 가능
- 단점 : 메모리 사용량이 큼
참고문헌
https://adjh54.tistory.com/135
https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque
