목차
- 덱 이란?
- 덱의 특징
- 큐의 연산
3-1. front
3-2. back
3-3. pop_front
3-4. pop_back
3-5. push_front
3-6. push_back
3-7. empty - 덱 사용 예시
1. 덱 이란?
덱(deque: Double Ended Queue)
직역하자면 끝이 두개인 큐입니다.
더 자세한 내용은 설명하면서 살펴보도록 하겠습니다.
2. 덱의 특징
기존의 큐는 각 각의 끝에서 입력과 삭제가 이루어 졌다면,
덱은 양 끝쪽에서 입력과 삭제가 이루어지는 자료구조입니다.
입력이나 삭제가 양방향에서 자유롭기 때문에 stack과 queue를 합쳐놓았다고 생각할 수 있습니다.
지난 시간(queue)에서 미처 못한 부분이기도 한데,
앞은 front로 거의 통일되어 있으나 설명하는 곳이나 사용하는 언어에 따라 끝부분을
rear나 back등으로 설명이 되어 있습니다.
이번 설명에서는 back으로 명칭을 통일하도록 하겠습니다.
3. 큐의 연산
3-1.front
front는 가장 앞의 자료를 출력하는 역할을 합니다.
위 예시에 front를 실행할 경우 'A'가 출력됩니다.
3-2. back
back은 가장 뒤의 자료를 출력하는 역할을 합니다.
위 예시에서 back을 실행할 경우 'E'가 출력됩니다.
3-3. pop_front
pop_front는 front에 해당하는 자료를 삭제합니다.
아래는 위 예시에서 pop_front를 실행한 모습입니다.
예시에서 알 수 있듯이 pop_front가 실행되고 나면
front가 가리키는 포인터의 위치가 한칸 뒤로 옮겨지는 것을 알 수 있습니다.
3-4. pop_back
pop_back은 back에 해당하는 자료를 삭제합니다.
바로 위의 예시에서 pop_back을 실행하면 다음의 모습으로 나타납니다.
'E'가 삭제되고서 back이 가리키는 위치가 한칸 앞으로 옮겨진 것을 확인할 수 있습니다.
3-5. push_front
push_front는 front의 위치에 자료를 추가합니다.
push_front("F")를 실행하면 다음의 모습이 됩니다.
위 자료처럼 front위치에 자료가 추가된다면 새로운 자료가 추가되고서 front는 그 위치를 가리킵니다.
3-6. push_back
push_back은 back의 위치에 자료를 추가합니다.
push_back("A")를 실행하면 다음의 모습이 됩니다.
위 자료처럼 back위치에 자료가 추가된다면 새로운 자료가 추가되고서 back은 그 위치를 가리킵니다.
3-7. empty
stack, queue와 마찬가지로
출력(front, back)이나 삭제(pop)을 실행할 시에 덱에 자료가 없다면 오류를 유발할 수 있기 때문에,
덱안에 자료가 있는지 없는지 확인하는 역할을 합니다.
4. 덱 사용 예시
실제 활용 예시는 찾시 못했습니다.
발견하는 데로 추가하겠습니다.
알고리즘에서는 주로 stack과 queue를 동시에 사용해야 하는 상황에 사용하기 좋습니다.
