Author: Stan Eisenstat
Subject: Re: [Cs223] Head and Tail Pointers
Date: Wednesday, 18 Mar 2020, 17:36:10

    > Message Posted By: Unknown
    >
    > When we are defining our deque are we allowed to have head and tail
    > pointers like the queue in Aspens' notes? Or are we only allowed to have a
    > head pointer?

As stated in the specification:

  2. The Deque data type should be implemented using a pair of stacks (the H
     stack and the T stack), each implemented using a headless, singly-linked
     list.  To add an item to the tail (head) of the Deque, push it onto the top
     of the T (H) stack.  To remove an item from the head of the Deque, pop it
     off the top of the H stack (but if the H stack is empty, first move items
     one at a time from the top of the T stack to the top of the H stack until
     the T stack is empty).
   
As you can see, this is completely different from the
doubly-linked list and ring buffer implementations
described in Aspnes' notes, so the notion of head and
tail pointers does not apply.
=====

    > When it is said the deque is implemented as two headless singly-linked
    > stacks do we have to define two separate stacks for a deque or can we just
    > imagine it is as a queue with the stack functionality of being able to
    > push to the head?

Your Deque implementation must be based on two headless,
singly-linked lists.

--Stan-