[자료구조] 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는 여러 스레드가 동시에 큐에 접근할 때나 큐의 크기가 동적으로 변할 때 적합함.

---