Author: Stan Eisenstat
Subject: Re: Deque Definition
Date: Friday, 13 Mar 2020, 19:10:35

    > I posted a question earlier today on the newsgroup regarding remD and
    > headD; it seems my understanding of how the deque struct should be
    > formatted was incorrect (I originally has it defined as a char * and a
    > pointer to another deque struct); I wasn't thinking of this in terms of
    > having a T and H stack). ...

As described 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).  (Why does this work?)
   
A singly-linked list consists of zero of more nodes,
each containing a value (in this case a char*) and a
pointer to the next node in the list (or NULL for the
last node in the list).  See Aspnes, Section 5.2, for
more details.

A headless list is one that is represented by a pointer
to a node, either the first node in the list or NULL if
the list is empty.  That is, there is no header node.
See Aspnes, Section 5.2, for more details.

The first sentence directs you to implement the Deque
ADT using two stacks, each implemented as a headless
singly-linked list.  That is, a Deque variable must be
a pointer to a struct(*) that contains TWO headless,
singly-linked lists (i.e., pointers to nodes), one
used as the H stack, the other as the T stack.

 (*) This struct is NOT the same as the struct used
     to implement the singly-linked list.

The rest of the description above explains how these
two stacks are used to implement the Deque ADT.
=====

    >                     ...  I see in the spec that you state, "Each value
    > stored in a Deque is a char *." I'm a bit confused as to how this is the
    > case; if we want the deque struct to point to the start of two
    > singly-linked lists (if I understand correctly!) then shouldn't we instead
    > have two pointers to some sort of stack struct (the stack struct defined
    > as a pointer to a stack struct and a char *)?

Yes, as is explained above.  You seem to be confusing
the two structs, one used for nodes in singly-linked
lists, the other for the two stack pointers.

If this does not clarify the situation, please ask
again.

--Stan-