cdat

一本全面剖析C++数据结构算法的书籍

.nr H1 4
.oh "The Abstract Data Type" 
.eh "Stacks"
.CS
STACKS
.CE
.NH 2
THE ABSTRACT DATA TYPE
.LP
.sp
A \fIstack\fR is an ordered list
of elements.  One end of this list is designated the \fIbottom\fR
and the other is called the \fItop\fR.  A stack with four elements
is shown in ?F{stack}(a). New elements are always added at the top of the
stack.  Suppose we wish to add the element \*(LQE\*(ZQ to the stack
of ?F{stack}(a).  This element will have to be placed on top
of the element \*(LQD\*(ZQ giving us the configuration of
?F{stack}(b).  Deletions from a stack also take place from
the top only.  Hence if we are to delete an element from the stack
of ?F{stack}(b), it will be the element \*(LQE\*(ZQ.  Following
the deletion, the configuration of ?F{stack}(a)
results.  If three successive deletions are performed
on the stack of ?F{stack}(b), the stack of ?F{stack}(c)
results.
.KF
.hl
.TS
expand;
l l l.
 	E\(<-@top@	 
D\(<-@top@	D	 
C	C	 
B	B	B\(<-@top@
A\(<-@bottom@	A\(<-@bottom@	A\(<-@bottom@
.sp
.T&
c c c.
(a)	(b)	(c)
.TE
.sp
.hl
\fB?F{stack}:\fR Stack configurations
.KE
.pp
From the preceding discussion, we see that a stack
is a LIFO (last in first out) list.  Lists of this type appear
frequently in computing.
The ADT stack is specified in ADT \n(H1.1.
.KF
.hl
\fBADT\fR \fIStack\fR
.br
{
\fBinstances\fR
.br
.AR
ordered list of elements; one end is called the \fIbottom\fR;
the other is the \fItop\fR;
.AL
\fBoperations\fR
.AR
@Create():@ Create an empty stack;
.br
@IsEmpty():@ Return 0 if stack is empty, return 1 otherwise;
.br
@IsFull():@ Return 1 if stack is full, return 0 otherwise;
.br
@Top(x):@ \kQReturn top element of stack in @x@;
.br
\h'|\nQu'return 0 if the operation fails, return 1 otherwise
.br
@Add(x):@ \kQAdd element \fIx\fR to the stack;
.br
\h'|\nQu'return 0 if the operation fails, return 1 otherwise
.br
@Delete(x):@ \kQDelete top element from stack and return it in \fIx\fR;
.br
\h'|\nQu'return 0 if the operation fails, return 1 otherwise
.AL
.AL
}
.br
.hl
\fBADT \n(H1.1:\fR The abstract data type stack
.KE
.oh "Formula-Based Representation"
.NH 2
FORMULA-BASED REPRESENTATION
.LP
.sp
Since a stack is a linear list with the restriction that additions
and deletions take place at the same end, we may use the linear list
representation of Section 2.3.  The top element of the stack
is stored in @element[length^-^1]@ and the bottom element
in @element[0]@.
The class \fIStack\fR defined in ?P{stackclass} is a derived
class of @LinearList@ (Program 2.1).
The functions \fIAdd\fR and \fIDelete\fR have been implemented by overloading
the binary operators `+' and `-', respectively. The expression @s~+~x@
will add element @x@ to the top of stack @s@ while the expression
@s~-~x@ will delete the top element from the stack @s@ and return the
deleted element in variable @x@.  Both functions return `0' if they are
unable to perform the operation and `1' if the operation is actually performed.
.KF
.hl
.nf
.ft  CW
template<class type>
class Stack : protected LinearList <type> {
// LIFO objects
public:
   Stack(int MaxStackSize = 10)
     : LinearList<type> (MaxStackSize) {}
   int IsEmpty() {return LinearList<type>::IsEmpty();}
   int IsFull()
      {return (Length() == MaxSize);}
   int Top(type& x)
      {return Find(Length(), x);}
   int operator +(type& x) // add x to stack
      {return Insert(Length(), x);}
   int operator -(type& x) // delete x from stack
      {return Delete(Length(), x);}
};
.ft R
.fi
.hl
\fB?P{stackclass}:\fR Formula-based class \fIStack\fR
.KE
.uh "Efficiency Of @Stack@"
.br
The complexity of each of the stack operations is seen to be
\(*H(1).  Notice that
by deriving @Stack@ from @LinearList@, we have reduced the effort needed
to code the class @Stack@.  Also, we have significantly improved our chances
of obtaining a correct implementation as the methods for @LinearList@
have already been tested and are known to be correct.  Unfortunately, this
simplification has come at the cost of increased run time.  For example,
to add an element to a stack, we first determine its @Length()@ and
then invoke @Insert@ which checks if the insert is in range.  Following
this, a \fBfor\fR loop overhead is paid to perform zero element moves.
We can eliminate these overheads by tailoring the code to the
class @Stack@.  This can be done by either starting afresh or by
accessing the protected members of @LinearList@ to customize our
codes.
.pp
Another potential difficulty is that the derived class @Stack@ is subject
to all of the limitations of the class @LinearList@.  For instance,
the operations \fBcout\fR and `==' need to be defined
on members of the data type @type@ as these are used by the @LinearList@
class members @Print@ and @Search@.
.uh "A Customized Definition of @Stack@"
.br
?P{custom} gives the class definition for @Stack@ when we customize
the @LinearList@ codes.  In a run time test which involved a \fBfor\fR
with 100,000 stack add and delete operations, the code of
?P{stackclass} took 42% more time than did the customized code
of ?P{custom}.  This improvement in performance has however also
come at some cost.
.KF
.nf
.hl
.ft CW
template<class type>
class Stack : protected LinearList <type> {
public:
   Stack(int MaxStackSize = 10)
        : LinearList<type> (MaxStackSize) {}
   int IsEmpty() {return LinearList<type>::IsEmpty();}
   int IsFull() {return (length == MaxSize);}
   int Top(type& x);
   int operator +(type& x); // add x to stack
   int operator -(type& x); // delete x from stack
};
template<class type>
int Stack<type>::Top(type& x)
{
if (IsEmpty()) return 0; //Top fails
x = element[length - 1];
return 1; //Top succeeds
}
template<class type>
int Stack<type>::operator+(type x)
{//add x to stack
if (IsFull()) return 0; //add fails
element[length++] = x;
return 1; //add succeeds
}
template<class type>
int Stack<type>::operator-(type& x)
{//delete top element and return in x
if (IsEmpty()) return 0; //delete fails
x = element[--length];
return 1; //delete succeeds
}
.hl
\fB?P{custom}:\fR Customized version of @Stack@
.ft R
.fi
.KE
Since the code of ?P{custom} accesses the non-public
members of the class @LinearList@ it is prone to failure when changes are
made to @LinearList@ as these changes are required only to
preserve the integrity of the public members.  This problem can be
overcome by extending the class @LinearList@ (Program 2.1)
to include public members to add and delete at/from the
right end of the list.
Another problem is that the code of
?P{custom} is somewhat more involved than that of ?P{stackclass}.
So,
it is expected to take longer to debug.
.pp
This illustrates some of the
tradeoffs involved between software reuse and program efficiency.
Interestingly, if we develop the code for the class @Stack@ afresh
(i.e., @Stack@ is not derived from @LinearList@ as in ?P{custom}),
and perform the run time experiment described above, the new code runs
13% faster than the customized code of ?P{custom}! 
With improvement in compiler technology, one may expect this difference in
performance to diminish.
.EX
.EH
.MB
.RS
.ip (a)
Obtain the code for the C++ class @Stack@ without making use of the
class @LinearList@.  I.e., start afresh and use an array @stack@
to store the elements, an integer variable @top@ that points to the
top element in the stack (initialized to @- 1@), and an integer
variable @MaxSize@ that gives the largest number of elements the
stack can hold.
.ip (b)
Write a program to measure the run time of an alternating sequence of
@n@ stack add and delete operations.  Measure the times needed
by Programs ?p{stackclass}, ?p{custom}, and your code of part (a).
.ip (c)
What can you say about the merits/demerits of the different software
development styles used?
.RE
.EH
Extend the stack ADT by adding functions to:
.RS
.ip (a)
Determine the size (i.e., number of elements) of the stack.
.ip (b)
Input a stack.
.ip (c)
Print a stack.
.RE
Now extend the class definition of a formula-based stack to include
code for these functions.
.EH
Extend the stack ADT by adding functions to:
.RS
.ip (a)
Split a stack into two.  The first contains the bottom half elements and the second the remaining elements.
.ip (b)
Combine two stacks into one by placing all elements of the second stack
on top of those in the first.  The relative order of elements from the
second stack is unchanged.
.RE
Now extend the class definition of a formula-based stack to include
code for these functions.
.LP
.oh "Linked Representation"
.NH 2
LINKED REPRESENTATION
.LP
.sp
While the array representation of a stack considered in the previous
section is both elegant and efficient, it is wasteful
of space when multiple stacks are to co-exist.  The reasons are the same as
those cited in Chapter 2 for the inefficiency of the separate arrays
for separate lists
representation.  An exception is
when only two stacks are to co-exist.  Now, space and time efficiency can be
maintained
by pegging the bottom of one stack at position 0
and the bottom of the other at position @MaxSize - 1@.  The two stacks
grow towards the middle of the array (see ?F{twostacks}).  When more than
two stacks are to be represented,
the multiple lists in a single array representation may be adapted
to the case of multiple stacks.  While this results in a
space efficient implementation,
the worst case add time becomes
\*(OH(@ArraySize@) rather than \(*H(1).  The delete time remains \(*H(1).
.KF
.hl
.PS
h = .5i; w = .3i;
X:[boxht = h; boxwid = w
A: box shade 5
B: box shade 5
C: box shade 5
D: box shade 5
]
boxwid = 5*w; box "@...@"; boxwid = w
Y:[E: box shade 30;
F: box shade 30
G: box shade 30
H: box shade 30
]
y = .1
arrow from X.D.t+(0,.4) to X.D.t
arrow from Y.E.t+(0,.4) to Y.E.t
"\fItop\fR1" at X.D.t+(0,.4+y)
"\fItop\fR2" at Y.E.t+(0,.4+y)
"[0]" at X.A.t+(0,.2)
"@ArraySize - 1@" at Y.H.t+(0,.2)
"STACK 1" at X.b-(0,.2)
"STACK 2" at Y.b-(0,.2)
arrow right .5i from X.D.e
arrow left .5i from Y.E.w
.PE
.hl
\fB?F{twostacks}:\fR  Two stacks in an array
.KE
.pp
Multiple stacks can be represented efficiently using a chain for each
stack.
This representation incurs a space penalty of one pointer field for each
stack element.  However, each stack operation can be performed in
\(*H(1) time.
When using a chain to represent a stack, we must decide which end
of the chain corresponds to the stack top.  If we associate the right
end of the chain with the stack top, then stack additions
and deletions are implemented using the
chain operations @Insert(n, x)@
and @Delete(n,x)@ where @n@ is the number of nodes in
the chain.  Each of these chain operations takes \(*H(@n@) time.
On the other hand, if we associate the left end of the chain with
the stack top, then the chain operations to use are
@Insert(0, x)@ and @Delete(1,x)@.  Each of these takes \(*H(1)
time.  As a result of this, the left end of the chain represents the
stack top.  The resulting class definition of a linked stack