자료구조 - 선형 구조 : 데크 (혹은 디큐, 데큐)

Algoritm에 대해 학습하며, Java를 통해 구현해봅니다.

이 포스팅은 BOJ(Beakjoon Online Judge)의 @jh05013 님 께서 관리하고 계신
단계별로 풀어보기를 기준으로 작성됩니다.

이 포스팅이 올라가는 저장소 : https://github.com/hwk0911

hwk0911 - Overview

혹시 이 포스팅을 보고 알고리즘 공부를 시작하시거나, 복습하시는 분들은
노트와 펜을 준비하시고 직접 그려보면서 하시면 좋습니다.

deque(Double Ended Queue)에 대해 알아보자!
부르는 사람에 따라 덱, 데크, 디큐 등 다양하게 불린다.

key)

1. 덱의 정의에 대해 알아본다.
2. 덱의 구조에 대해 알아본다.
3. 덱의 작동에 대해 알아본다.

1. deque (Double Ended Queue)

더블 엔디드 큐 이번 포스팅은 자료구조의 세번째 덱 포스팅이다.

Double Ended : 양 끝이 닮은, 양 끝이 앞이 되는, 앞뒤가 없는(배, 전차)
의 뜻으로 직역이 가능하다.

Double Ended Queue를 직역하면, '양 끝이 앞이 되는 큐'로 직역이 가능하다.
하지만, 덱은 큐의 성질만 갖는것이 아닌, 스택과 큐의 성질을 모두 갖는다.

전 포스팅에서 큐는 양쪽이 뚫린 FIFO의 구조를 갖는 자료구조라 했다.
덱도 마찬가지로 양쪽이 뚫린 자료구조다.
하지만, 양쪽에서 들어올 수 있고, 양쪽으로 나갈 수 있다.

요약해 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조다.

 

 

터널은 데크와 비슷한 구조를 갖는다. 걸어서 터널로 들어가도, 다시 되돌아 나올 수 있고,
그대로 통과할 수 있으니 비슷하다 할 수 있다.

+ 파생으로 스크롤, 셸프가 존재한다.

스크롤 - 입력이 한쪽 끝으로만 가능하도록 설정한 덱 (입력 제한 덱)
셸프 - 출력이 한 쪽 끝으로만 가능하도록 설정한 덱 (출력 제한 덱)

2. 덱(deque)의 구조

deque는 앞부분을 가리키는 front와, 마지막을 가리키는 last로 표현된다.

push의 경우 push_front(), push_back()
pop의 경우 pop_front(), pop_back() 이다.

deque의 가장 기본적인 구조를 살펴보자.

mid는 Array.length / 2의 위치를 표현한다.

첫 시작시 Front, Last는 mid의 위치에서 시작한다.

사진에서는 확실한 표현을 위해 짝수로 선언하여 2번과 3번 사이의 경계에 mid를 뒀으나,
실질적으로 길이 / 2는 3이므로, mid는 3번 배열을 가리킨다.

개인적인 생각으로 이상적인 덱은 홀수의 칸을 갖는것이 이상적이라 생각한다.

push와 pop연산에 대한 작동 방식을 표료 설명해보면 다음과 같다.

push_Front()	첫 입력이 아닌경우 1. --Front; 2. Array[Front] = data;	pop_Front()	1. Array[Front] = null; 2. ++Front;
push_Last()	첫 입력이 아닌경우 1. ++Last; 2. Array[Last] = data;	pop_Last()	1. Array[Last] = null; 2. --Last;

이처럼 단순하게 표현이 가능하다.

하지만 예외는 항상 존재한다.

1. 첫 입력이 Front로 들어오는 경우
   1. Array[Front] = data;
   2. ++Last;
2. 첫 입력이 Last로 들어오는 경우
   1. Array[Last] = data;
   2. --Front;

당연히 Overflow, Underflow의 예외처리는 기본중의 기본이다.

3. 덱(deque)의 작동

덱은 기본적으로 위와같이 작동한다. 

Front == Last인 경우, Front = mid, Last = mid를 통해 위치를 초기화 시켜준다.

Gif에 누락된 내용이 있는데, Front나 Last 둘 중 하나에 가득 찬 상태로,
가득 찬 곳으로 데이터가 들어온다면, 정렬을 실행하게 된다.
모든 원소를 가득차지 않은곳으로 한칸씩 밀어 앞부분에 공간을 만들어준다.
후에 생긴 공간에 데이터를 추가한다.

4. 추천 문제

문제 : https://www.acmicpc.net/problem/10866

10866번: 덱