개념 - 덱 deque

덱은 앞뒤로 넣고 삭제도 가능한 자료구조다. 

즉

push_front와 push_back이

pop_front와 pop_back 이 전부 가능하다.

추가적으로 back()과 front()를 지원한다.

책의 ADT

addFront(e)

deleteFront()

addRear(e)

isEmpty()

getFront()

getRear()

isFull();

display();

배열기반 원형 덱은 원형 큐가 가진 push_back(enqueue)과 pop_front(dequeue) 에다가 push_front와 pop_back을 더한 것이다. 따라서 (책에서는) 상속받아서 구현할 수도 있다. 

그런데 구현할 때 조금 더 생각해야 할 것이 있는데, 이전의 큐 게시글에서 언급했던 전위 후위 문제다. 만약 push_front를 하면서 전위로 입력을 했다면 push_back을 할 때는 후위로 입력을 해야한다. 단편적인 코드는 다음과 같다.

void push_back(T d)

{

if (isFull()) throw;

data[rear] = d;

rear = (rear + 1) % SIZE;

}

void push_front(T d)

{

if (isFull()) throw;

front = (front - 1 + SIZE) % SIZE;

data[front] = d;

}

간단하게 생각해봐도 rear 와 front가 둘다 [5]에서 시작한다고 할 때, 똑같이 후위로 입력한다면 [4]와 [6]에 입력하므로 [5]가 낭비될 것이다. 하나를 후위로 했다면 하나는 전위로 해야한다. 이건 

T Front()

{

if (isEmpty()) throw;

return data[front % SIZE];

}

T Back()

{

if (isEmpty()) throw;

return data[rear - 1 % SIZE];

}

등에도 일관성 있게 적용되어야 한다. 위에서 front를 전위로 했으므로 그냥 반환하고, rear를 후위로 했으므로 하나를 빼줘야 한다.

연결리스트처럼, 구현할 땐 꼭 그림을 그리자.. 아니 사실 어떤 자료구조던 그림을 그리자

코드 : 

배열기반 덱 : http://kid5.tistory.com/262

STL 덱 정보 : 

http://www.cplusplus.com/reference/deque/deque/?kw=deque

요약 : 벡터처럼 동적할당을 사용하지만 연속적인 메모리가 아닐수도 있다. 즉 포인터 연산이 UB일 수 있다. 벡터는 동적할당이 지속적으로 이루어지는 단일배열로 구성된 반면 덱은 여러 공간에 자료가 흩어져있기 때문에 맨 앞에 삽입하거나 삭제할 때의 시간도 효율적이면서 상수시간에 모든 원소를 접근할 수 있지만 내부구현이 복잡하다.

https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

벡터의 벡터.... 라고 한다. 언젠가 심도있게 공부해보자.