\documentstyle [12pt]{article}
\setlength{\parskip}{2 ex}

\begin{document}
\sloppy

{\large
\begin{center}
15.451 PROBLEM SET \# 10\\
DUE: Thursday 2 December 1993 \\
2 problems
\end{center}}

\section{Two stacks makes a queue}

We are trying to implement a queue, that is, a data structure that
supports {\sc enqueue}(x) and {\sc dequeue}.  {\sc Enqueue}(x) adds x
to the tail of the queue and {\sc Dequeue} returns the element at the
head of the queue and removes it.

For example:
\begin{tabbing}
Operation \hspace{1in} \= Result returned \hspace{.2in}\= Queue status \\
\\
Start \> \> EMPTY \\
{\sc Enqueue}(a) \> \> a \\
{\sc Enqueue}(b) \> \> a b \\
{\sc Enqueue}(c) \> \> a b c \\
{\sc Enqueue}(d) \> \> a b c d \\
{\sc Dequeue} \> a \> b c d \\
{\sc Dequeue} \> b \> c d \\
{\sc Enqueue}(e) \> \> c d e \\
{\sc Dequeue} \> c \> d e \\
{\sc Dequeue} \> d \> e \\
{\sc Dequeue} \> e \> EMPTY \\
\end{tabbing}

But we only have two stacks $\cal A$ and $\cal B$.  Using the
operations {\sc Push-A}(x), {\sc Push-B}(x), {\sc Pop-A}, and {\sc
Pop-B}, show how to implement a queue so that both {\sc Enqueue}(x)
and {\sc Dequeue} take amortized constant time.

\begin{itemize}
\item Use potential functions for your amortized analysis.
\item Use the accounting method for your amortized analysis.
\end{itemize}

\end{document}