[자료구조] Queue, Stack, Deque
1. Stack
- 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조이다.
- 나중에 들어온게 먼저 나가는 후입선출(LIFO, Last In First Out) 방식이다.
2. Queue
- "줄을 서서 기다린다." 라는 사전적 의미를 가지고 있다.
- 먼저 들어온게 먼저 나가는 선입선출(FIFO, First In First Out) 방식이다.
3. Deque
- Double-ended Queue(양단 큐)라는 뜻으로, Stack와 Queue의 장점을 합쳐놓은 자료구조이다.
- 양쪽 끝에서 삽입과 삭제가 모두 가능하다는 특징이 있다.
- Deque Interface는 다음과 같이 크게 3가지 기능(추가, 삭제, 조회)을 제공한다.
1. 추가
| Type | Method | Description |
| boolean | add(E e) | 이 deque의 뒤에 지정된 요소를 삽입 (성공시 true, 사용 가능한 공간이 없으면 IllegalStateException 발생) |
| void | addFirst(E e) | 이 deque의 앞에 지정된 요소를 삽입 (사용 가능한 공간이 없으면 IllegalStateException 발생) |
| void | addLast(E e) | 이 deque의 뒤에 지정된 요소를 삽입 (사용 가능한 공간이 없으면 IllegalStateException 발생) |
| boolean | offer(E e) | 이 deque의 뒤에 지정된 요소를 삽입 (성공 시 true, 사용 가능한 공간이 없으면 false) |
| boolean | offerFirst(E e) | 이 deque의 앞에 지정된 요소를 삽입 (성공 시 true, 사용 가능한 공간이 없으면 false) |
| boolean | offerLast(E e) | 이 deque의 뒤에 지정된 요소를 삽입 (성공 시 true, 사용 가능한 공간이 없으면 false) |
| void | push(E e) | 이 deque의 앞에 지정된 요소를 삽입 (사용 가능한 공간이 없으면 IllegalStateException 발생) |
| int | size() | 이 deque에 존재하는 요소의 수를 반환 |
2. 삭제
| Type | Method | Description |
| E | poll() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | pollFirst() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | pollLast() | 이 deque의 마지막 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | pop() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | remove() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | removeFirst() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| E | removeLast() | 이 deque의 첫번째 요소를 검색 및 제거 (요소가 없으면 null 반환) |
| boolean | remove(Object o) | 이 deque에서 지정된 요소의 첫번째 항목을 제거 (요소가 존재하면 true, 없으면 false 반환) |
| boolean | removeFirstOcurrence (Object o) |
이 deque에서 지정된 요소의 첫번째 항목을 제거 (요소가 존재하면 true, 없으면 false 반환) |
| boolean | removeLastOcurrence (Object o) |
이 deque에서 지정된 요소의 마지막 항목을 제거 (요소가 존재하면 true, 없으면 false 반환) |
3. 조회
| Type | Method | Description |
| boolean | contains(Object o) | 이 deque에서 지정된 요소가 존재하는지 검색 (요소가 존재하면 true, 없으면 false 반환) |
| E | element() | 이 deque의 첫번째 요소를 검색 (요소가 없으면 NoSuchElementException 발생) |
| E | getFirst() | 이 deque의 첫번째 요소를 검색 (요소가 없으면 NoSuchElementException 발생) |
| E | getLast() | 이 deque의 마지막 요소를 검색 (요소가 없으면 NoSuchElementException 발생) |
| E | peek() | 이 deque의 첫번째 요소를 검색 (요소가 없으면 null 반환) |
| E | peekFirst() | 이 deque의 첫번째 요소를 검색 (요소가 없으면 null 반환) |
| E | peekLast() | 이 deque의 마지막 요소를 검색 (요소가 없으면 null 반환) |
| Iterator | iterator() | 이 deque의 요소에 대한 반복자를 순서대로 반환 |
| Iterator | descendingIterator() | 이 deque의 요소에 대한 반복자를 역순으로 반환 |
💻 면접 질문 대비하기
Q. 단방향 데이터 처리를 할 때 Deque를 사용하는 것은 바람직한 방법일까?
데이터를 추가, 삭제, 조회하는 것에 대한 속도는 동일하다.
다만 하지만 효율성의 문제가 존재한다고 언급하고 있다.
단방향 데이터 처리 작업에서 Deque를 사용할 때 불필요한 추가 작업에 대해 자세히 물어보았다.
deque는 양방향 데이터 처리 작업을 위해 전처리 과정이 들어가게 된다.
(즉, 사용되지 않을 방향에 대한 전처리 작업을 진행한다는 것이다.)
이 부분 때문에 적절하게 사용된 Stack이나 Queue가 더욱 효율적이라고 할 수 있다.
어떠한 전처리 작업을 수행하는지 구체적으로 물어보았다.
아래 내용을 참고하여, 코드를 작성할 때 어떤 자료구조가 더 적절한지 고민하는.태도가 필요하다고 생각된다.
Q. Deque의 구현체로서 ArrayDeque와 LinkedList 중 어떤 클래스를 사용하는 것이 좋을까?
배열을 사용하는 ArrayDeque가 대부분의 작업에서 유리하다.
하지만 양단이 아닌 중간에 요소를 추가하고 삭제하는 작업에 한해서는 LinkedList를 사용하는 것이 효율적이다.
참고로 ArrayDeque 생성 시 초기 배열의 크기는 16이다.
크기를 넘을 때마다 64까지는 2배씩, 그 이후부터는 1.5배씩 증가시켜 대체한다.
Q. 멀티스레드 환경에서 사용하는 LinkedBlockingDeque와 ConcurrentLinkedDeque의 차이는?
LinkedBlockingDeque는 스레드 간의 작업을 순차적으로 수행해야 할 때나, 큐의 크기가 고정되어 있을 때 적합함.
ConcurrentLinkedDeque는 여러 스레드가 동시에 큐에 접근할 때나 큐의 크기가 동적으로 변할 때 적합함.
