Author: Stan Eisenstat
Subject: Re: [Cs223] Headless vs. Headed Deque?
Date: Thursday, 19 Mar 2020, 08:25:51

    > Message Posted By: Unknown
    >
    > What are the benefits of implementing the Deque as headless (which I think
    > means using "Deque d" as a pointer to struct deque - is that correct?) vs.
    > headed (which would mean the struct deque would have an array of type
    > Stack [where Stack is a pointer to struct stack] of size 2 as a field, is
    > that right?)?

In both cases a Deque variable is a pointer to a struct
deque.

In the "headed" case, storage for the struct deque is
allocated by createD() and freed by destroyD(), and thus
the value of the Deque variable (which is the address of
that storage) never changes when you call one of the
Deque functions.

In the "headless" case, the value of the Deque variable
is NULL when the Deque is empty.  Storage for the struct
deque is allocated by addD() or pushD() when the Deque
is empty (and its address is stored in the Deque
variable) and freed by remD() or popD() when the last
element is removed (and NULL is stored in the Deque
variable).  Thus the value of the Deque variable changes
when the Deque switches between the empty and nonempty
states.

A "headed" Deque is slightly easier to implement. but
the "headless" Deque illustrates why the Deque variable
can change (which is why I posted about it).

--Stan-