ex42.tex

\chapter{Exercise 42: Stacks and Queues}

At this point in the book you know most of the data structures that are used to
build all the other data structures.  If you have some kind of \ident{List},
\ident{DArray}, \ident{Hashmap}, and \ident{Tree} then you can build most
anything else that's out there.  Everything else you run into either uses
these or is some variant on these.  If it's not then it's most likely an
exotic data structure that you probably will not need.

\ident{Stacks} and \ident{Queues} are very simple data structures that are
really variants of the \ident{List} data structure.  All they are is using
a \ident{List} with a "discipline" or convention that says you'll always 
place elements on one end of the \ident{List}.  For a \ident{Stack}, you
always push and pop.  For a \ident{Queue}, you always shift to the 
front, but pop from the end.

I can implement both data structures using nothing but the CPP and two
header files.  My header files are 21 lines long and do all the 
\ident{Stack} and \ident{Queue} operations without any fancy defines.

To see if you've been paying attention, I'm going to show you the 
unit tests, and then \emph{you} have to implement the header files
needed to make them work.  To pass this exercise you can't create any
\file{stack.c} or \file{queue.c} implementation files.  Use only the
\file{stack.h} and \file{queue.h} files to make the tests runs.

\begin{code}{tests/stack\_tests.c}
<< d['code/liblcthw/tests/stack_tests.c|pyg|l'] >>
\end{code}

Then the \file{queue\_tests.c} is almost the same just using \ident{Queue}:

\begin{code}{tests/queue\_tests.c}
<< d['code/liblcthw/tests/queue_tests.c|pyg|l'] >>
\end{code}

\section{What You Should See}

Your unit test should run without you changing the tests, and it
should pass \program{valgrind} with no memory errors.  Here's
what it looks like if I run \file{stack\_tests} directly:

\begin{code}{stack\_tests run}
<< d['code/ex42.1.sh-session|pyg|l'] >>
\end{code}

The \file{queue\_test} is basically the same kind of output so I 
shouldn't have to show it to you at this stage.

\section{How To Improve It}

The only real improvement you could make to this is to switch from
using a \ident{List} to using a \ident{DArray}.  The \ident{Queue}
data structure is more difficult to do with a \ident{DArray} because
it works at both ends of the list of nodes.

A disadvantage of doing this entirely in a header file is that you can't
easily performance tune it.  Mostly what you're doing with this technique
is establishing a "protocol" for how to use a \ident{List} in a certain
style.  When performance tuning, if you make \ident{List} fast then 
these two should improve as well.

\section{Extra Credit}

\begin{enumerate}
\item Implement \ident{Stack} using \ident{DArray} instead of \ident{List}
    without changing the unit test.  That means you'll have to create your
    own \ident{STACK\_FOREACH}.
\end{enumerate}