8. 데크(Deque, Double-ended queue)는 큐(Que)의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서 스텍의 성질과 큐의 성질을 모두 가지고 있는 지료구조이다.

<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" /><?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> 

데크의 연산을 추상 자료형으로 공백 데크를 생성하는 연산, 데크가 공백인지 아닌지 확인하는 연산, 데크의 rear 뒤에 원소(item)를 삽입하는 연산, 데크의 front에 있는 원소(item)를 데크에서 삭제하고 반환하는 연산, 데크의 rear에 있는 원소(item)를 데크에서 삭제하고 반환하는 연산, 데크의 front에 있는 원소(item)를 삭제하는 연산, 데크의 rear에 있는 원소(item)를 삭제하는 연산, 데크의 front에 있는 원소(item)를 삭제하는 연산, 데크의 rear에 있는 원소(item)를 반환하는 연산 등으로 정의 할 수가 있다.

[1] 위에서 제공한 연산 함수의 가상 수행하면서 데크의 상태를 그림으로 그리고 설명 하시오

[2] 데크는 양쪽 끝에서 삽입/삭제가 가능해야하기 때문에 이중 연결 리스트(Linked List)를 이용하여 구현한다. 데크의 이중 연결 리스트 구조를 설명하시오,

[3] [2]의 이중 연결 리스트를 이용하여 [1]의 연산을 수행하는 데크의 과정을 C 프로그램으 로 구현하시오.