99클럽 코테 스터디 25일차 TIL + Deque(1)

학습 키워드

- Deque

 

공부한 내용

Deque

• Deque는 Double Ended Queue의 양방향 대기열이라고도 불리는 자료구조이다.
• 양방향으로 열려있는 구조로 Queue와 외형적으로 비슷한 구조이다. 그러나 Deque는 Stack과 Queue와 달리 LIFO, FIFO와 같은 순서에 구속되지 않는다.

Deque 특징

Stack 및 Queue를 모두 사용할 수 있다.

• Deque는 양쪽으로 데이터를 추가하고 삭제할 수 있어서 Stack과 Queue를 구현할 수 있다. 추가와 삭제를 양쪽에서 제어할 수 있어서 여러 형태로 사용할 수 있다.

추가를 제한하는 구조

• 한쪽에서만 데이터 추가가 가능하고 삭제는 양방향에서 가능하게 구현한다면 아래와 같은 구조가 된다.
• 데이터 추가의 방향이 정해진 상태가 된다. 왼쪽으로 삭제하는 형태는 Stack과 같고 오른쪽으로 삭제하는 형태는 Queue와 같다.

삭제를 제한하는 구조

• 데이터 추가는 양쪽에서 가능하지만, 삭제는 한 방향에서만 가능하게 구현한다면 아래와 같은 구조가 된다.

왼쪽에서 추가하는 형태는 Stack과 같고 오른쪽에서 추가하는 형태는 Queue와 같다.

Deque은 양쪽으로 입출력이 모두 가능하지만 이 중에 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(Scroll)이라고 하며, 한쪽으로만 출력할 수 있도록 설정한 덱을 셀프(Shelf)라고 한다.

양방향 끝에서 데이터 추가, 삭제가 용이하다.

• Stack과 Queue에서 추가할 데이터나 삭제할 데이터의 인덱스 정보를 가지고 있듯이 Deque도 양쪽의 추가 삭제할 데이터의 인덱스 정보를 가지고 있어서 양쪽 끝의 데이터에 접근과 추가, 삭제가 용이하다.

양방향 끝이 아닌 임의 데이터만 추가하거나 삭제하는 것은 불가능하다.

• Deque는 양방향 끝의 인덱스 정보를 가지고 있다. 따라서 양방향의 데이터가 아닌 중간에 있는 데이터에 접근하려고 하면 인덱스 정보가 없어서 접근할 수 없다.

Deque 선언

Deque<Integer> deque = new LinkedList<>();
Deque<Integer> deque1 = new ArrayDeque<>();

• Deque를 선언할 때 보통 LinkedList와 ArrayDeque를 사용한다.

 

회고

발생한 문제

- 코딩 문제를 풀다가 자료구조에 대한 공부가 부족하다는 사실을 알게 되었다. 

 

해결 방법

- 자료구조 공부를 진행하였다. 

 

알게된 내용

- Deque는 스택과 큐 모두 사용할 수 있다는 사실을 알게 되었다.