[자바의정석] Chap 11. 컬렉션 프레임워크(스택, 큐)

1. 4 Stack / Queue

- Stack : 후입 선출인 자료구조. stack, arraylist 등으로 구현 가능하다.

   -. stack에서는 search로 전달된 객체의 위치를 반환함. 이때 위치는 배열의 0이 아닌 1부터 시작함.

 

- Queue : 선입 선출인 자료구조. queue는 인터페이스라, 해당 인터페이스를 구현한 클래스 사용(LinkedList 등)

                -> 먼저 들어간 놈을 지울때 빈 공간 채우기 위해 데이터 복사 발생(arraylist 배열기반 사용하면)

                -> 따라서 linkedlist로 구현됨

 

- PriorityQueue : 저장된 순서에 상관없이 우선순위가 높은 것부터 꺼낸다. 그리고 null은 저장 불가이다.

                 -> 얘는 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조 형태로 저장한다.

 

- Deque(Double-ended Queue) : queue의 변형으로, 양쪽 끝으로 추가 / 삭제가 가능하다. 

deque의 조상은 queue이며, 구현체로는 ArrayDeque, LinkedList가 있다.