Deques, Queues, and Stacks

Objective: The deque data structure effectively implements both the queue and stack data structures at the same time. Moreover, to understand how to implement a deque implies that you also understand how to implement both the queue and stack. In completing this task we will explore this by first implementing a deque, then encapsulating its functionality to generate the stack and queue structures trivially.

Note: although this task may appear particularly large, most of the code for the Deque class can be adapted from the OrderedLinkedList class we have already written. The Stack and Queue classes are then almost entirely just calling the methods you have defined in the Deque. Thus, the requirements of this task focus more on understanding the problem conceptually than coding.

For this task you are required to implement three classes: a reusable Deque collection, and then encapsulate that class to create reusable Stack and Queue collections. The Deque collection class is to be implemented using a doubly linked list (not an ordered linked list!) and has the following features:

• Namespace:
  • namespace SIT221_Library Your class should be defined in the namespace SIT221_Library;
• Interfaces:
  • ICollection< TYPE > Your class must implement the ICollection interface, including the associated enumerator support.

• Properties:
  • public int Count A read-only property which returns how many elements are currently stored in the doubly linked list;
  • public bool IsReadOnly { get; } Returns false (the deque is not read-only);
• Constructors:
  • public Deque() A parameter-less constructor which initialises the deque’s doubly linked list structure;
• Methods:
  • public void AddFront(TYPE data) A method which accepts a single element and inserts it at the head of the doubly linked list;
  • public void AddRear(TYPE data) A method which accepts a single element and appends it after the tail of the doubly linked list;
  • public void Add(TYPE data) A method which accepts a single element simply passes the information through to the AddRear() method, defined above;
  • public void Clear() A method which removes all elements stored in the deque;
  • public bool Contains(TYPE item) A method which searches the deque contents to determine whether a value is stored in the deque (returns true) or not (returns false);
  • public void CopyTo(TYPE[] array, int arrayIndex) A method which copies all of the elements in the deque to the array, starting at arrayIndex;
  • public TYPE PeekFront() A method which returns the value stored in the head of the linked list;
  • public TYPE PeekRear() A method which returns the value stored in the tail of the linked list;
  • public bool Remove(TYPE item) A method which deletes the first occurrence of the specified item from the deque and returns true, or returns false if the specified item did not appear in the list;
  • public TYPE RemoveFront() A method which removes the head element from the linked list and returns its value;
  • public TYPE RemoveRear() A method which removes the tail element from the linked list and returns its value;
• Enumerator support:
  • Given the use of the same doubly-linked list structure as we used in the ordered linked list example, you should be able to reuse your solution’s / the specimen solution’s implementation of the enumerator with minor changes.

The Queue collection is implemented by using a Deque in its implementation by exploiting delegation2. The Queue class will also implement the ICollection interface, and all the members specified by this interface are simply mapped/passed to the equivalent members of the Deque class, e.g., for the Add method you would simply write:

public void Add(TYPE item)
{
_MyDequeObject.Add(item);
}

The following changes and/or additional methods are also required: l

• It is not possible to remove an element from the middle of a queue (only from the front), so the Remove() method defined by the ICollection interface must throw a NotSupportedException instead.

• public void Enqueue(TYPE item) Add a method that provides the normal enqueue operation functionality, which is mapped/passed to the deque’s AddRear() method;
• public TYPE Dequeue() Add a method that provides the normal dequeue operation functionality, which is mapped/passed to the deque’s RemoveFront() method;
• public TYPE Front() Add a method that provides the normal front operation functionality, which is mapped/- passed to the deque’s PeekFront() method;
• public TYPE Rear() Add a method that provides the normal rear operation functionality, which is mapped/- passed to the deque’s PeekRear() method.

Similarly, the Stack collection is also implemented by using a Deque in its implementation by exploiting delegation and similarly implements the ICollection interface. The following changes and/or additional methods are also required:

• It is not possible to remove an element from the middle of a stack (only from the top), so the Remove() method defined by the ICollection interface must throw a NotSupportedException instead.

• public void Push(TYPE item) Add a method that provides the normal push operation functionality, which is mapped/- passed to the deque’s AddFront() method;
• public TYPE Pop() Add a method that provides the normal pop operation functionality, which is mapped/- passed to the deque’s RemoveFront() method;
• public TYPE Top() Add a method that provides the normal top operation functionality, which is mapped/- passed to the deque’s PeekFront() method;

Finally, test your three classes by writing a simple Main method