Chapter 2 INTRODUCTION TO STACKS
1,Stack Specifications
2,Implementation of Stacks
3,Application,A Desk
Calculator4,Application,Bracket
Matching5,Abstract Data Types and
Their Implementations
6,Pointers and Pitfalls
A stack is a data
structure in which all
insertions and deletions of
entries are made at one
end,called the top of the
stack,The last entry which
is inserted is the first one
that will be removed.
2.1 Introduction Specifications
2
3
4
1
4
3
Top
4
3
3
Characteristic:
Last In First Out
Standard Template Library (STL)
? The standard template library
(abbreviated STL) in C++ contains much
useful information,many functions,and
many classes.
? The STL provides convenient
implementations for many common data
structures,including almost all the data
structures we shall study in this book.
? We can include the STL stack
implementation into our programs with the
directive
#include <stack>
and then we can dene initially empty stack
objects and apply methods called push,pop,
top,and empty.
? In C++,a template construction allows us to
create data structures whose entries have
different types,Example:
stack<double> numbers and stack<int>
? The STL provides several
implementations of
various data structures such as stacks.
? The code in a client program should not
depend on a particular choice of
implementation,but the performance of
the
final program may very much depend on
the
choice of implementation.
? A second,optional template
First Example,Reversing a List
#include<iostream.h>
#include <stack>
using namespace std;
void main( )
/* Pre,The user supplies an integer n and n decimal
numbers.
Post,The numbers are printed in reverse order.
Uses,The STL class stack and its methods
*/
{ int n; double item;
stack <double> numbers;
cout<<" Type in an integer n followed by n
decimal numbers," << endl ;
cout<<" The numbers will be printed in reverse
order," << endl ;
cin >> n;
for(int i=0; i<n; i++)
{ cin>>item; numbers.push(item); }
cout<<endl<<endl;
while(!numbers.empty( ))
{ cout<<numbers.top( )<<" "; numbers.pop( ); }
cout<<endl;
} declares and initializes
a stack of numbersinput an integer ofpush stackinput an element
push stack
output an element
in top of stack
an ele ent in
top of stack is pop off
Constructor
The constructor is a function with the same
name as the corresponding class and no return
type,It is invoked automatically whenever an
object of the class is declared.
2.2 Implementation of Stacks
Stack,,Stack( );
Pre,None.
Post,The Stack exists and is initialized to be
empty.
Entry Types,Generics
For generality,we use Stack entry for the
type of entries in a Stack.
A client can specify this type with a
definition such as
typedef int Stack entry ;
or typedef char Stack entry ;
The ability to use the same underlying data
structure and operations for different entry
types is called generics,typedef provides
simple generics,Starting in Chapter 6,we
shall use C++ templates for greater
generality.
Error Processing
We shall use a single enumerated type called
Error code to report errors from all of our
programs
and functions,
The enumerated type Error code is part of the
utility package in Appendix C,Stacks use three
values of an Error_code:
success,overflow,underflow
Later,we shall use several further values of an
Error code.
Programming Precept
After a client uses a class method,it should
decide whether to check the resulting error status,
Classes should be designed to allow clients to
decide how to respond to errors.
C++ also provides more sophisticated error
processing called exception handling,The
standard library implementations of classes use
exception handling,but we shall opt for the
simplicity of returning error codes in all our
implementations.
Error_code Stack,,pop( );
Pre,None.
Post,If the Stack is not empty,the top of the
Stack is removed,If the Stack is empty,
an
Error code of underflow is returned and
the Stack is left unchanged.
1,Specification of Method for
Stack
Error_code Stack,,top(Stack entry &item) const;
Pre,None.
Post,The top of a nonempty Stack is copied to item,
A code of fail is returned if the Stack is empty.
Error_code Stack,,push(const Stack entry &item);
Pre,None.
Post,If the Stack is not full,item is added to the top
of the Stack,If the Stack is full,an Error code
of overflow is returned and the Stack is left
unchanged.
Error_code Stack,,top(Stack entry &item) const;
Pre,None.
Post,The top of a nonempty Stack is copied to item,
A code of fail is returned if the Stack is empty.
Error_code Stack,,empty( ) const;
Pre,None.
Post,A result of true is returned if the Stack is
empty,otherwise false is returned.
const int maxstack = 10;
class Stack
{ public:
Stack( );
bool empty( ) const;
Error_code pop( );
Error_code top(Stack entry &item) const;
Error_code push(const Stack entry &item);
private:
int count;
Stack_entry entry[maxstack];
};
2 The Class Specifications
The declaration of private visibility for the data
makes it is impossible for a client to access the
data stored in a Stack except by using the methods
push( ),pop( ),and top( ).
Important result,A Stack can never contain illegal
or corrupted data,In general,data is said to be
encapsulated if it can only be accessed by a
controlled set of functions.
Programming Precept
The public methods for a data structure
should be implemented without
preconditions.
The data members should be kept private.
Representation of Data in a Contiguous
Stack
(a) Stack is empty.
Stack is empty
(b) Push the first entry.
(c) n items on the stack.
Push the first entry
n items on the stack
Error_code Stack::push(const Stack_entry &item)
/* Pre,None.
Post,If the Stack is not full,item is added to the
top
of the Stack.If the Stack is full,an Error_code
of overflow is returned and the Stack is left
unchanged,*/
{
Error_code outcome=success;
if(count >= maxstack) outcome= overflow;
else entry[count++] = item;
return outcome;
}
Error_code Stack::pop( )
/* Pre,None.
Post,If the Stack is not empty,the top of the Stack
is removed,If the Stack is empty,an
Error_code of underflow is returned and the
Stack is left unchanged,*/
{
Error_code outcome=success;
if(count = = 0) outcome= underflow;
else --count;
return outcome;
}
Error_code Stack::top(Stack entry &item) const
/* Pre,None.
Post,If the Stack is not empty,the top of the Stack
is returned in item.If the Stack is empty,an
Error_code of underflow is returned and the
Stack is left unchanged,*/
{
Error_code outcome = success;
if(count = = 0) outcome = underflow;
else item = entry[count - 1];
return outcome;
}
bool Stack::empty( ) const
/* Pre,None.
Post,If the Stack is empty,true is returned,
Otherwise false is returned,*/
{ bool outcome = true;
if(count > 0) outcome = false;
return outcome;
}
Stack::Stack( )
/* Pre,None.
Post,The stack is initialized to be empty,*/
{ count = 0 ; }
1,Reverse Polish
CalculatorIn a Reverse Polish ( postfix ) calculator,
the operands (numbers,usually) are entered
before an operation (like addition,
subtraction,multiplication,or division) is
specified,The operands are pushed onto a
stack,
When an operation is performed,it pops
its operands from the stack and pushes its
result back onto the stack.
2.3 Application,A Desk Calculator P66
RPN (an acronym for Reverse Polish
Notation) is method of entering input in to a
calculator without the use of parenthesis.
( Reverse Polish Notation also called Postfix
Notation )example,infix(中缀 ) → postfix(后缀 )
A*(B+C) → ABC+*
A/B*C+D*(E-A)+C/(D*B)→ AB/C*DEA-*+CDB*/+
typedef double Stack_entry;
# include "stack.h"
void main( )
/* Post,The program has executed simple arithmetic
commands entered by the user,
Uses,The class Stack and functions introduction,
instructions,do_command,And
get_command, */
{ Stack stored_numbers;
introduction( );
instructions( );
while (do_command(get-command(),
stored_numbers));
}
Obtaining a Command
The auxiliary function get command obtains
a command from the user,checking that it is
valid and converting it to lowercase by using
the string function tolower( ) that is declared
in the tandard
header file cctype.char get_command()
{
char command;
bool waiting = true;
cout<<"Select command and press< Enter >:";
while(waiting)
{ cin>>command;
command = tolower(command);
if (command = = '?‘ || command = = '=‘ ||
command = = '+' || command = = '.‘ ||
command = = '*‘ || command = = '/' ||
command = = 'q‘ ) waiting=false;
else cout<<"Please enter a valid command:"
<<"\n[?]push to stack [=]print top\n"
<<"[+][-][*][/] are arithmetic "
<< " operations \n [Q]uit.\n"
}
return command;
}
bool do_command(char command,Stack &numbers)
/* Pre,The first parameter specifies a valid calculator
command.
Post,The command specified by the first parameter
has been applied to the Stack of numbers
given by the second parameter,A result of
true is returned unless command == 'q',
Uses,The class Stack,*/
{ double p,q;
switch(command)
{ case '?',
cout<<"Enter a real number,"<<flush;
cin>>p;
Input operand
if(numbers.push(p)==overflow)
cout<<"Warning,Stack full,lost number\n“;
break;
case '=':
if (numbers.top(p)==underflow)
cout<<"Stack empty\n";
else cout << p << endl ;
break;
case '+':
if (numbers.top(p) = = underflow)
cout << "Stack empty" << endl;
else
{ numbers.pop( );
printGet top of stack to p
Get top of stack to pFirst operand(top stack)in p,pop it
if ( numbers.top(q) = = underflow )
{ cout << "Stack has just one entry\n";
numbers.push(p); }
else
{ numbers.pop( );
if(numbers.push(q+p)==overflow)
cout<<"Warning,Stack full,lost
result\n";
}
}
break;
case 'q',cout << "Calculation finished.\n";
return false;
} // end switch
return true;
}
Get top of stack to q
second operand(top stack)
in q,pop it
add,result push stackadd options for furtheruser c mmands
怎样设计算法把运算符放在两个运算对象中
间的中缀表达式转换为后缀形式呢？
请参看, 数据结构与算法, (科学出版社 )
void main( )
/* Post,The program has notified the user of any bracket
mismatch in the standard input file.
Uses,The class Stack, */
{ Stack openings;
char symbol;
bool is_matched = true;
while(is_matched && (symbol=cin.get( )) != '\n')
{ if (symbol=='{' || symbol=='(' || symbol=='[')
openings.push(symbol);
if(symbol=='}' || symbol==')' || symbol==']') // if(1)
{ if(openings.empty( )) // if(2)
{ is_matched = false;
cout<<"Unmatched closing bracket"<<symbol
<<" detected.\n";
} //end if(2)
2.4 Application,Bracket Matching P69
else { char match;
openings.top(match);
openings.pop( );
is_matched=(symbol=='}' && match=='{')
|| (symbol==')' && match=='(') ||
(symbol==']'
&& match =='[');
if(!is_matched)
cout<<"Bad match "<<match<<
symbol<<endl;
}
} //end if(1)
} //end_while
if (!openings.empty( ))
cout<<"Unmatched opening bracket(s) detected.\n";
}
2.5 Abstract Data Types P71
Definition A type is a set,and the elements of
the set
are called the values of the type.Types such as int,float,and char are called
atomic types because we think of their values as
single entities only,not something we wish to
subdivide.
Computer languages like C++ provide tools
such as arrays,classes,and pointers with which
we can build new types,called structured types,
A single value of a structured type (that is,a
single element of its set) is a structured object
such as a contiguous stack,A value of a
structured type has two ingredients,It is made up
of component elements,and there is a structure,
Definition A sequence of length 0 is empty,A
sequence of length n≥ 1 of elements from a set T
is an ordered pair (Sn-1,t) where Sn-1 is a sequence
of length n-1 of elements from T,and t is an
element of T,Abstract Stacks
The definition of a finite sequence allows us to define a
list of items of a type T as a finite sequence of
elements of the set T,
Next we wish to define a stack,But there is nothing
regarding the sequence of items to distinguish a stack
from a list,
The primary characteristic of a stack is the set of
operations or methods by which changes or accesses
can be made,Including a statement of these operations
with the structural rules defining a finite sequence,we
Definition A stack of elements of type T is a finite
sequence of elements of T,
together with the following operations:
1,Create the stack,leaving it empty.
2,Test whether the stack is Empty.
3,Push a new entry onto the top of the stack,
provided
the stack is not full.
4,Pop the entry off the top of the stack,provided
the
stack is not empty.
5,Retrieve the Top entry from the stack,
provided the
stack is not empty.
Refinement of Data Specification
1,On the abstract level we decide how the data are
related
to each other and what operations are needed,but
we
decide nothing concerning how the data will
actually be
stored or how the operations will actually be
done.
2,On the data structures level we specify enough
detail
so that we can analyze the behavior of the
methods and
make appropriate choices as dictated by our
problem.
3,On the implementation level we decide the details
The first two levels are often called conceptual
because at these levels we are more concerned
with problem solving than with programming,The
middle two levels can be called algorithmic
because they concern precise methods for
representing data and operating with it,The last
two levels are specifically concerned with
programming.Programming Precept
Let your data structure your program.
Refine your algorithms and data structures
at the same time.
Once your data are fully structured,
your algorithms should almost write
themselves.
◆ Avoid tricky ways of storing your data; tricks usually
will not generalize to new situations.
◆ Be sure to initialize your data structures.
◆ In designing algorithms,always be careful about
the extreme cases and handle them gracefully,
Trace through your algorithm to determine what
happens in extreme cases,particularly when a
data structure is empty or full.
◆ Before choosing implementations,be sure that all
the data structures and their associated
operations are fully specified on the abstract
level.
Pointers and Pitfalls
◆ Use data structures to clarify the logic of your
programs.
◆ Practice information hiding and encapsulation in
implementing data structures,Use functions to
access your data structures,and keep these in
classes separate from your application program.
◆ Postpone decisions on the details of
implementing your data structures as long as
you can.
◆ Stacks are among the simplest kind of data
structures; use stacks when possible.
◆ In any problem that requires a reversal of data,
consider using a stack to store the data.
1,Stack Specifications
2,Implementation of Stacks
3,Application,A Desk
Calculator4,Application,Bracket
Matching5,Abstract Data Types and
Their Implementations
6,Pointers and Pitfalls
A stack is a data
structure in which all
insertions and deletions of
entries are made at one
end,called the top of the
stack,The last entry which
is inserted is the first one
that will be removed.
2.1 Introduction Specifications
2
3
4
1
4
3
Top
4
3
3
Characteristic:
Last In First Out
Standard Template Library (STL)
? The standard template library
(abbreviated STL) in C++ contains much
useful information,many functions,and
many classes.
? The STL provides convenient
implementations for many common data
structures,including almost all the data
structures we shall study in this book.
? We can include the STL stack
implementation into our programs with the
directive
#include <stack>
and then we can dene initially empty stack
objects and apply methods called push,pop,
top,and empty.
? In C++,a template construction allows us to
create data structures whose entries have
different types,Example:
stack<double> numbers and stack<int>
? The STL provides several
implementations of
various data structures such as stacks.
? The code in a client program should not
depend on a particular choice of
implementation,but the performance of
the
final program may very much depend on
the
choice of implementation.
? A second,optional template
First Example,Reversing a List
#include<iostream.h>
#include <stack>
using namespace std;
void main( )
/* Pre,The user supplies an integer n and n decimal
numbers.
Post,The numbers are printed in reverse order.
Uses,The STL class stack and its methods
*/
{ int n; double item;
stack <double> numbers;
cout<<" Type in an integer n followed by n
decimal numbers," << endl ;
cout<<" The numbers will be printed in reverse
order," << endl ;
cin >> n;
for(int i=0; i<n; i++)
{ cin>>item; numbers.push(item); }
cout<<endl<<endl;
while(!numbers.empty( ))
{ cout<<numbers.top( )<<" "; numbers.pop( ); }
cout<<endl;
} declares and initializes
a stack of numbersinput an integer ofpush stackinput an element
push stack
output an element
in top of stack
an ele ent in
top of stack is pop off
Constructor
The constructor is a function with the same
name as the corresponding class and no return
type,It is invoked automatically whenever an
object of the class is declared.
2.2 Implementation of Stacks
Stack,,Stack( );
Pre,None.
Post,The Stack exists and is initialized to be
empty.
Entry Types,Generics
For generality,we use Stack entry for the
type of entries in a Stack.
A client can specify this type with a
definition such as
typedef int Stack entry ;
or typedef char Stack entry ;
The ability to use the same underlying data
structure and operations for different entry
types is called generics,typedef provides
simple generics,Starting in Chapter 6,we
shall use C++ templates for greater
generality.
Error Processing
We shall use a single enumerated type called
Error code to report errors from all of our
programs
and functions,
The enumerated type Error code is part of the
utility package in Appendix C,Stacks use three
values of an Error_code:
success,overflow,underflow
Later,we shall use several further values of an
Error code.
Programming Precept
After a client uses a class method,it should
decide whether to check the resulting error status,
Classes should be designed to allow clients to
decide how to respond to errors.
C++ also provides more sophisticated error
processing called exception handling,The
standard library implementations of classes use
exception handling,but we shall opt for the
simplicity of returning error codes in all our
implementations.
Error_code Stack,,pop( );
Pre,None.
Post,If the Stack is not empty,the top of the
Stack is removed,If the Stack is empty,
an
Error code of underflow is returned and
the Stack is left unchanged.
1,Specification of Method for
Stack
Error_code Stack,,top(Stack entry &item) const;
Pre,None.
Post,The top of a nonempty Stack is copied to item,
A code of fail is returned if the Stack is empty.
Error_code Stack,,push(const Stack entry &item);
Pre,None.
Post,If the Stack is not full,item is added to the top
of the Stack,If the Stack is full,an Error code
of overflow is returned and the Stack is left
unchanged.
Error_code Stack,,top(Stack entry &item) const;
Pre,None.
Post,The top of a nonempty Stack is copied to item,
A code of fail is returned if the Stack is empty.
Error_code Stack,,empty( ) const;
Pre,None.
Post,A result of true is returned if the Stack is
empty,otherwise false is returned.
const int maxstack = 10;
class Stack
{ public:
Stack( );
bool empty( ) const;
Error_code pop( );
Error_code top(Stack entry &item) const;
Error_code push(const Stack entry &item);
private:
int count;
Stack_entry entry[maxstack];
};
2 The Class Specifications
The declaration of private visibility for the data
makes it is impossible for a client to access the
data stored in a Stack except by using the methods
push( ),pop( ),and top( ).
Important result,A Stack can never contain illegal
or corrupted data,In general,data is said to be
encapsulated if it can only be accessed by a
controlled set of functions.
Programming Precept
The public methods for a data structure
should be implemented without
preconditions.
The data members should be kept private.
Representation of Data in a Contiguous
Stack
(a) Stack is empty.
Stack is empty
(b) Push the first entry.
(c) n items on the stack.
Push the first entry
n items on the stack
Error_code Stack::push(const Stack_entry &item)
/* Pre,None.
Post,If the Stack is not full,item is added to the
top
of the Stack.If the Stack is full,an Error_code
of overflow is returned and the Stack is left
unchanged,*/
{
Error_code outcome=success;
if(count >= maxstack) outcome= overflow;
else entry[count++] = item;
return outcome;
}
Error_code Stack::pop( )
/* Pre,None.
Post,If the Stack is not empty,the top of the Stack
is removed,If the Stack is empty,an
Error_code of underflow is returned and the
Stack is left unchanged,*/
{
Error_code outcome=success;
if(count = = 0) outcome= underflow;
else --count;
return outcome;
}
Error_code Stack::top(Stack entry &item) const
/* Pre,None.
Post,If the Stack is not empty,the top of the Stack
is returned in item.If the Stack is empty,an
Error_code of underflow is returned and the
Stack is left unchanged,*/
{
Error_code outcome = success;
if(count = = 0) outcome = underflow;
else item = entry[count - 1];
return outcome;
}
bool Stack::empty( ) const
/* Pre,None.
Post,If the Stack is empty,true is returned,
Otherwise false is returned,*/
{ bool outcome = true;
if(count > 0) outcome = false;
return outcome;
}
Stack::Stack( )
/* Pre,None.
Post,The stack is initialized to be empty,*/
{ count = 0 ; }
1,Reverse Polish
CalculatorIn a Reverse Polish ( postfix ) calculator,
the operands (numbers,usually) are entered
before an operation (like addition,
subtraction,multiplication,or division) is
specified,The operands are pushed onto a
stack,
When an operation is performed,it pops
its operands from the stack and pushes its
result back onto the stack.
2.3 Application,A Desk Calculator P66
RPN (an acronym for Reverse Polish
Notation) is method of entering input in to a
calculator without the use of parenthesis.
( Reverse Polish Notation also called Postfix
Notation )example,infix(中缀 ) → postfix(后缀 )
A*(B+C) → ABC+*
A/B*C+D*(E-A)+C/(D*B)→ AB/C*DEA-*+CDB*/+
typedef double Stack_entry;
# include "stack.h"
void main( )
/* Post,The program has executed simple arithmetic
commands entered by the user,
Uses,The class Stack and functions introduction,
instructions,do_command,And
get_command, */
{ Stack stored_numbers;
introduction( );
instructions( );
while (do_command(get-command(),
stored_numbers));
}
Obtaining a Command
The auxiliary function get command obtains
a command from the user,checking that it is
valid and converting it to lowercase by using
the string function tolower( ) that is declared
in the tandard
header file cctype.char get_command()
{
char command;
bool waiting = true;
cout<<"Select command and press< Enter >:";
while(waiting)
{ cin>>command;
command = tolower(command);
if (command = = '?‘ || command = = '=‘ ||
command = = '+' || command = = '.‘ ||
command = = '*‘ || command = = '/' ||
command = = 'q‘ ) waiting=false;
else cout<<"Please enter a valid command:"
<<"\n[?]push to stack [=]print top\n"
<<"[+][-][*][/] are arithmetic "
<< " operations \n [Q]uit.\n"
}
return command;
}
bool do_command(char command,Stack &numbers)
/* Pre,The first parameter specifies a valid calculator
command.
Post,The command specified by the first parameter
has been applied to the Stack of numbers
given by the second parameter,A result of
true is returned unless command == 'q',
Uses,The class Stack,*/
{ double p,q;
switch(command)
{ case '?',
cout<<"Enter a real number,"<<flush;
cin>>p;
Input operand
if(numbers.push(p)==overflow)
cout<<"Warning,Stack full,lost number\n“;
break;
case '=':
if (numbers.top(p)==underflow)
cout<<"Stack empty\n";
else cout << p << endl ;
break;
case '+':
if (numbers.top(p) = = underflow)
cout << "Stack empty" << endl;
else
{ numbers.pop( );
printGet top of stack to p
Get top of stack to pFirst operand(top stack)in p,pop it
if ( numbers.top(q) = = underflow )
{ cout << "Stack has just one entry\n";
numbers.push(p); }
else
{ numbers.pop( );
if(numbers.push(q+p)==overflow)
cout<<"Warning,Stack full,lost
result\n";
}
}
break;
case 'q',cout << "Calculation finished.\n";
return false;
} // end switch
return true;
}
Get top of stack to q
second operand(top stack)
in q,pop it
add,result push stackadd options for furtheruser c mmands
怎样设计算法把运算符放在两个运算对象中
间的中缀表达式转换为后缀形式呢？
请参看, 数据结构与算法, (科学出版社 )
void main( )
/* Post,The program has notified the user of any bracket
mismatch in the standard input file.
Uses,The class Stack, */
{ Stack openings;
char symbol;
bool is_matched = true;
while(is_matched && (symbol=cin.get( )) != '\n')
{ if (symbol=='{' || symbol=='(' || symbol=='[')
openings.push(symbol);
if(symbol=='}' || symbol==')' || symbol==']') // if(1)
{ if(openings.empty( )) // if(2)
{ is_matched = false;
cout<<"Unmatched closing bracket"<<symbol
<<" detected.\n";
} //end if(2)
2.4 Application,Bracket Matching P69
else { char match;
openings.top(match);
openings.pop( );
is_matched=(symbol=='}' && match=='{')
|| (symbol==')' && match=='(') ||
(symbol==']'
&& match =='[');
if(!is_matched)
cout<<"Bad match "<<match<<
symbol<<endl;
}
} //end if(1)
} //end_while
if (!openings.empty( ))
cout<<"Unmatched opening bracket(s) detected.\n";
}
2.5 Abstract Data Types P71
Definition A type is a set,and the elements of
the set
are called the values of the type.Types such as int,float,and char are called
atomic types because we think of their values as
single entities only,not something we wish to
subdivide.
Computer languages like C++ provide tools
such as arrays,classes,and pointers with which
we can build new types,called structured types,
A single value of a structured type (that is,a
single element of its set) is a structured object
such as a contiguous stack,A value of a
structured type has two ingredients,It is made up
of component elements,and there is a structure,
Definition A sequence of length 0 is empty,A
sequence of length n≥ 1 of elements from a set T
is an ordered pair (Sn-1,t) where Sn-1 is a sequence
of length n-1 of elements from T,and t is an
element of T,Abstract Stacks
The definition of a finite sequence allows us to define a
list of items of a type T as a finite sequence of
elements of the set T,
Next we wish to define a stack,But there is nothing
regarding the sequence of items to distinguish a stack
from a list,
The primary characteristic of a stack is the set of
operations or methods by which changes or accesses
can be made,Including a statement of these operations
with the structural rules defining a finite sequence,we
Definition A stack of elements of type T is a finite
sequence of elements of T,
together with the following operations:
1,Create the stack,leaving it empty.
2,Test whether the stack is Empty.
3,Push a new entry onto the top of the stack,
provided
the stack is not full.
4,Pop the entry off the top of the stack,provided
the
stack is not empty.
5,Retrieve the Top entry from the stack,
provided the
stack is not empty.
Refinement of Data Specification
1,On the abstract level we decide how the data are
related
to each other and what operations are needed,but
we
decide nothing concerning how the data will
actually be
stored or how the operations will actually be
done.
2,On the data structures level we specify enough
detail
so that we can analyze the behavior of the
methods and
make appropriate choices as dictated by our
problem.
3,On the implementation level we decide the details
The first two levels are often called conceptual
because at these levels we are more concerned
with problem solving than with programming,The
middle two levels can be called algorithmic
because they concern precise methods for
representing data and operating with it,The last
two levels are specifically concerned with
programming.Programming Precept
Let your data structure your program.
Refine your algorithms and data structures
at the same time.
Once your data are fully structured,
your algorithms should almost write
themselves.
◆ Avoid tricky ways of storing your data; tricks usually
will not generalize to new situations.
◆ Be sure to initialize your data structures.
◆ In designing algorithms,always be careful about
the extreme cases and handle them gracefully,
Trace through your algorithm to determine what
happens in extreme cases,particularly when a
data structure is empty or full.
◆ Before choosing implementations,be sure that all
the data structures and their associated
operations are fully specified on the abstract
level.
Pointers and Pitfalls
◆ Use data structures to clarify the logic of your
programs.
◆ Practice information hiding and encapsulation in
implementing data structures,Use functions to
access your data structures,and keep these in
classes separate from your application program.
◆ Postpone decisions on the details of
implementing your data structures as long as
you can.
◆ Stacks are among the simplest kind of data
structures; use stacks when possible.
◆ In any problem that requires a reversal of data,
consider using a stack to store the data.
