ADT Queue..... 2

[keat]

Consider a variation of the ADT queue called a deque, or double-ended queue, in which items can be inserted or deleted from either end. How can I construct a C++ class that implements this ADT? How do I write an short program to test my ADT? Also, I have to create a stack and single-ended queue classes as descendants of my deque class. How do I go about doing that? Thank you very much for your time and help.

Keat.

 

[Zyrenthian]

It sounds like the deque would be a combination of a stack and a queue. That being the case, I would impliment it with a head and tail pointer, use the deque/enque for queue functionality and push and pop for the stack functionality.

Matt

 

[QwertGold]

Hey Keat.
Sounds like you need a linklist to implement you ADT. If you have a linklist with both a head and a tail pointer and some functions
insert_at_head
insert_at_tail
remove_at_head
remove_at_tail.

If you need to potimize you ADT use a double-link list, so you dont need to traverse the list from the beginning whenever you need to remove_at_tail.
You can find a example in Deitel & Deitel's "How to program C++" chapter 15.

Kind regards
Klaus