COS 333: Chapter 11, Part 1
Summary
TLDRThis lecture delves into abstract data types (ADTs) and encapsulation, fundamental concepts in programming languages. It explains abstraction as a simplified representation focusing on significant attributes, integral to high-level languages that hide lower-level details. ADTs are user-defined, grouped in syntactic units with hidden representations, ensuring data integrity and simplifying program organization. The lecture also discusses design issues for ADT support in languages, using C++ as an example to illustrate class-based encapsulation, constructors, destructors, and the importance of separating interface from implementation.
Takeaways
- 📚 The lecture introduces the concepts of Abstract Data Types (ADTs) and encapsulation within the context of programming languages.
- 🎯 Abstraction in programming is about providing a summarized view of an entity that includes only the most significant attributes, hiding the lower-level details.
- 🏛️ High-level programming languages have evolved to offer varying degrees of abstraction, simplifying the implementation of complex systems without exposing the intricacies of lower-level operations.
- 🔐 ADTs are user-defined constructs that encapsulate data and operations within a single syntactic unit, ensuring data integrity and preventing external code from directly accessing the data.
- 🔑 Two key conditions for ADTs are: 1) the representation and operations must be defined within a single unit, and 2) the representation must be hidden from the program units that use these objects.
- 🛠️ The advantages of grouping related ADT elements within a single syntactic unit include better organization, increased modifiability, and the ability to compile each ADT separately, improving efficiency.
- 🔍 Hiding the ADT representation from user code enhances reliability, as changes to the internal workings do not affect the code that uses the ADT, and reduces the likelihood of naming conflicts.
- 📝 A programming language must provide a syntactic unit for encapsulating ADTs, a method for making essential parts of an ADT visible to clients while hiding its representation, and support for access controls to regulate visibility.
- 🛑 Design issues for ADTs in programming languages include the form of the interface container, the parameterization of ADTs, access controls, and whether the ADT specification is separate from its implementation.
- 💻 The lecture provides examples of how C++ supports ADTs through classes, access control specifiers, constructors, destructors, and friend functions, demonstrating how these features address the design issues discussed.
- 📁 The implementation of ADTs in C++ can be separated into a header file for declarations and an implementation file for definitions, allowing for the hiding of object representation from the client and better organization of code.
Q & A
What are the main topics discussed in the lectures on Chapter 11?
-The main topics discussed are abstract data types (ADTs), encapsulation, and the implementation of ADTs in programming languages, along with design issues associated with ADTs.
What is the general concept of abstraction in programming languages?
-Abstraction in programming is a view or representation of an entity that includes only the most significant attributes, essentially providing a summarized view that contains only the most important details.
How do high-level programming languages provide abstraction?
-High-level programming languages provide abstraction by hiding details of lower-level implementations, allowing programmers to implement complex systems without needing to understand the underlying operations.
What are the two conditions that an abstract data type (ADT) must satisfy?
-An ADT must have its representation and operations defined in a single syntactic unit, and the representation of the objects must be hidden from the program units that use these objects.
Why is it advantageous to group everything related to an ADT within the same syntactic unit?
-Grouping everything related to an ADT within the same syntactic unit allows for better organization, increased modifiability, and the ability to compile each ADT separately, which can be more efficient.
What is the purpose of hiding the representation of an ADT from the user code?
-Hiding the representation of an ADT from the user code increases reliability, as it prevents the user code from depending on the specific representation and allows the internal workings of the ADT to be changed without affecting the user code.
What are the advantages of hiding the representation of an ADT in terms of programming?
-The advantages include increased reliability, as the user code cannot directly access the objects of the ADT; increased simplicity for the programmer, as they only need to know about the interface; and reduced likelihood of name conflicts.
What features must a programming language provide to support ADTs?
-A programming language must provide a syntactic unit to contain the ADT's representation and operations, and a method to make the essential parts of an ADT visible to clients while hiding the actual data representation.
What are some design issues to consider when a high-level programming language provides support for ADTs?
-Design issues include the form of the container for the interface, whether ADTs can be parameterized, the access controls provided, and whether the specification of the ADT is physically separate from its implementation.
How does C++ support ADTs?
-C++ supports ADTs through the use of classes, which encapsulate the data and operations within a single syntactic unit, and provides features like constructors, destructors, access control specifiers, and friend functions to support various aspects of ADT implementation.
What is the significance of constructors and destructors in C++ for ADTs?
-Constructors in C++ are special functions used to initialize the data members of an instance, while destructors are used to clean up after an instance is destroyed, typically by deallocating resources and performing other cleanup operations.
Outlines
📘 Introduction to Abstract Data Types and Encapsulation
The lecture begins with an introduction to Chapter 11, focusing on abstract data types (ADTs) and encapsulation. The speaker explains that abstraction in programming hides unnecessary details, allowing programmers to work at a higher level without needing to understand lower-level implementations. High-level languages provide varying degrees of abstraction, simplifying complex systems. The lecture will cover the definition of ADTs, their design issues, and examples of how programming languages implement them. The concept of process abstraction through sub-programs is also introduced, setting the stage for a deeper dive into data abstraction in the subsequent lecture.
🔐 Understanding Abstract Data Types and Their Benefits
This paragraph delves into the specifics of abstract data types (ADTs), outlining the two key conditions they must meet: encapsulation of representation and operations within a single syntactic unit, and the concealment of the representation from users. The benefits of these conditions include organized code, increased modifiability, and the ability to compile ADTs separately, which optimizes the development process by minimizing the need for recompilation. The speaker also discusses the advantages of hiding the ADT's representation, such as enhanced reliability and the prevention of name conflicts, and emphasizes the importance of a clear interface for interaction with the ADT.
🛠 Language Features for Supporting ADTs
The speaker outlines the essential language features required to support abstract data types, including a syntactic unit for encapsulation and mechanisms for visibility control. The need for a syntactic unit to contain the ADT's type definition and operations is highlighted. Additionally, the paragraph discusses the necessity of making certain parts of an ADT visible to clients while keeping the actual data representation hidden. The importance of sub-program headers for defining supported operations is also emphasized, providing a clear interface for users without exposing the underlying implementation.
🏗️ Design Considerations for ADT Support in Programming Languages
The paragraph explores various design issues that programming languages must address to effectively support ADTs. These include deciding the form of the container for the ADT's interface, the possibility of parameterizing ADTs, access control mechanisms, and whether the specification of an ADT should be physically separate from its implementation. The discussion provides insight into how different languages might approach these design challenges, affecting how ADTs are structured and utilized within those languages.
🤖 C++ Implementation of ADTs Through Classes and Constructors
This section examines how C++ supports ADTs using classes, which serve as the encapsulation device. Classes in C++ allow for the sharing of member functions across all instances while maintaining separate data for each object. The use of access control specifiers to achieve information hiding is explained, along with the role of constructors in initializing ADT instances. The paragraph also touches on the concept of destructors for cleaning up resources and the use of friend functions and classes to allow external access to private class members when necessary.
📚 Implementing a Stack ADT in C++
The speaker provides an example of implementing a stack ADT in C++, illustrating the use of a class to define the stack's representation and operations. The example includes a default constructor, a destructor, and a member function for the push operation. The implementation details are kept within the class, preventing client code from depending on them. The importance of separating the interface from the implementation to enhance encapsulation is emphasized, showcasing a simple yet effective way to utilize ADTs in C++.
📁 Separating Interface and Implementation in C++
The paragraph discusses a more advanced implementation of the stack ADT in C++, which enforces a separation between the header file and the implementation file. This approach hides the object representation from the client, ensuring that the client relies only on the public interface defined in the header file. The implementation file contains the actual code for the member functions, constructors, and destructors, which are compiled separately. This method promotes better organization and encapsulation, preventing the client from depending on the internal details of the ADT.
🔚 Conclusion and Preview of the Next Lecture
The final paragraph wraps up the current lecture on abstract data types and encapsulation, summarizing the key points discussed and the examples provided. It also gives a preview of the next lecture, which will continue the exploration of Chapter 11, presumably delving deeper into the implementation and application of ADTs in programming languages.
Mindmap
Keywords
💡Abstract Data Types (ADTs)
💡Encapsulation
💡Abstraction
💡Data Abstraction
💡Process Abstraction
💡Modifiability
💡Reliability
💡Name Conflicts
💡Constructor
💡Destructor
💡Friend Functions
Highlights
Introduction to abstract data types (ADTs) and encapsulation, emphasizing their importance in programming languages.
Definition of abstraction in programming, highlighting its role in summarizing entities with significant attributes.
The evolution of high-level programming languages, from FORTRAN to modern languages, focusing on their abstraction capabilities.
Explanation of process abstraction through sub-programs, simplifying complex operations for programmers.
The concept of data abstraction since 1980, illustrating how it is achieved via abstract data types.
Criteria for defining ADTs, including the grouping of related data and operations within a single syntactic unit.
The necessity of hiding the representation of ADT objects from program units to ensure data integrity.
Advantages of organizing related ADT elements within a single syntactic unit, such as better program organization and increased modifiability.
Benefits of hiding ADT representations, including increased reliability and reduced likelihood of name conflicts.
Features required by programming languages to support ADTs, such as syntactic units and methods for visibility control.
Design issues in ADT support, including the form of the container for the interface and parameterization of ADTs.
C++'s approach to ADT support using classes, encapsulating data and member functions, and the role of constructors and destructors.
Implementation of a stack ADT in C, demonstrating the grouping of representation and operations within a class.
Separation of header and implementation files in C++ for ADTs to enhance encapsulation and hide object representation.
Discussion on friend functions and classes in C++, their role in accessing private members across different classes.
Conclusion of the lecture with a preview of the next session, which will continue the discussion on chapter 11 of the textbook.
Transcripts
welcome to the first of two lectures on
chapter 11 where we will be discussing
abstract data types and encapsulation
concepts
these are the topics that we'll be
discussing in today's lecture we'll
begin by looking at what abstraction in
a general sense is in the context of
programming languages
we'll then move on to data abstraction
specifically we will talk about what
abstract data types or adts are
then we'll take a look at the various
design issues that are associated with
abstract data types and then finally
we'll begin with our discussion on a
couple of programming language examples
in terms of how these languages
implement abstract data types and how
these differ in terms of the design
issues that we will discuss
in the next lecture we'll also be
continuing with these language examples
and therefore this will
form the main
body of the work that we'll be
discussing in this lecture and the next
now before we can talk about what
abstract data types are we first need to
define what we are talking about when we
discuss abstraction in a general sense
so an abstraction is a view or a
representation of some sort of entity
that includes only the most significant
attributes so you can think of an
abstraction as a summarized view of
something where the summarized view
contains only the most important details
of the thing that we are trying to
represent
now abstraction is a very fundamental
concept right at the core of programming
and computer science in general
and if we look at high-level programming
languages we can in fact see that they
have aimed to provide at least some
level of abstraction all the way from
the very earliest high-level programming
languages like fortran
so we can see this in high-level
programming languages because they
attempt to hide details
of lower level
implementations which are not necessary
for a programmer to understand in order
for them to implement a fairly
complicated system so for example we can
see if we look at machine language
compared to a high level programming
languages code then the operations that
need to be performed on a register and
memory level do not need to be performed
in the high-level programming language
because those operations have been
abstracted away and the programmer
doesn't need to worry about them
now nearly all programming languages
support what is referred to as process
abstraction and this is provided by
means of sub programs so here we are
cutting our code up into smaller units
and then once we have a unit that
contains a series of related operations
then we can essentially forget about
those operations and simply use the
sub-program so for example if we have a
sub-program that prints something out to
the screen
then that essentially will be abstracted
away and we don't need to then consider
how the mechanics work in terms of
actually
displaying something to the screen
now nearly all programming languages
since 1980 support what is referred to
as data abstraction
and this is achieved by means of
abstract data types so process
abstraction was discussed in the
previous set of lectures for the last
chapter
and in this lecture and the next lecture
we will be focusing on data abstraction
so now that we know what an abstraction
is we can focus our attention on
abstract data types or adts
so adts are user-defined constructs and
they must satisfy two conditions
firstly for every abstract data type the
representation of and the operations on
objects of this type are defined in a
single syntactic unit
so what does this mean well it means
everything that is related to the adt
will be grouped together within a single
unit so in other words the data that the
adt stores as well as the operations
that the adt can perform such as for
example search operations or reordering
operations are all grouped together
within a single unit
and what this then implies is that other
program units such as functions or
methods are allowed to create variables
of this defined type so essentially they
are then creating a specific instance of
an adt
and then the data stored within the adt
will be as specified in the syntactic
unit and also the operations that can be
performed on the adt will also be
specified within the same syntactic unit
now the second condition that an adt
must satisfy
is that the
representation of objects of the type
will be hidden from the program units
that use these objects
so what this means is the only
operations that are possible for the adt
are those that are provided in the types
definition
in other words what we are saying is
that the data stored within the adt
cannot be directly accessed by external
entities such as functions or methods
it is necessary to manipulate this data
by means of the operations defined by
the adt and these operations form an
interface and they effectively then
filter whatever interactions are
performed
on the abstract data type and therefore
ensure that the data is then always in a
correct congruent state
and that data corruption does not occur
so let's look in more detail at what the
advantages are of the first condition
associated with abstract data types in
other words that everything related to
an abstract data type will be grouped
together within the same syntactic unit
so the first advantage is fairly
straightforward it allows for our
programs to be better organized and this
is of course because everything related
to an abstract data type will be grouped
together within the same syntactic unit
which will typically be contained within
its own file so this means there's only
one place that we need to look
for any code related to that abstract
data type
related to this we also have increased
modifiability and this is again because
everything associated with the abstract
data type will be grouped together so if
we need to make any changes then we know
that these changes will be localized to
one particular file that contains this
single syntactic unit
and then finally each adt can generally
be compiled separately in its own file
and what this means is that there is no
need to recompile the entire system and
you should be familiar with this from
the concept of make files in c plus and
java
so essentially if we look at a make file
this allows us to localize what needs to
be recompiled whenever a change is made
so if we modify for example a class that
is defined in one file then we only need
to recompile that file as well as other
files that then
depend on that file and the abstract
data type defined within it
so
we then only need to compile a subset of
the files related to our larger project
and not everything as a whole if we
didn't have these separate syntactic
units we wouldn't be able to separate
our adt's out into secret files and
therefore every time there's a minor
change we'd have to recompile the entire
system from scratch
so what is the advantage of the second
condition associated with all abstract
data types in other words that the
representation of an abstract data type
is hidden from the user code
so the first big advantage is an
increase in reliability and this is
because the user code cannot directly
access objects of the abstract data type
or depend on the representation of these
objects
and this allows the inner workings of
the abstract data types to be changed
without affecting user code
so let's imagine that we are defining an
abstract data type that represents a
list and we decide initially that our
abstract data type is going to be
represented using an array
however later on we decide that we will
replace the array representation and
instead use a linked list representation
now if the representation of this list
adt
were exposed to the user code then the
user code could depend on the fact that
an array is being used for the
representation so they may depend on it
in terms of making certain operations
more efficient for example
if the inner representation is hidden
from the user code it means that the
user code
should not be aware of whether an array
or a linked list or some other kind of
representation is being used so all that
they do is they use the abstract data
type through its interface in terms of
the operations that are supported for it
and they cannot grow to depend on the
inner representation of the actual data
within the adt
the second big advantage is that a
programmer will know about list code and
variables so this just simply means that
a programmer who uses an abstract data
type
needs to know about fewer things and
this relates back to our discussion on
why abstraction in general is a good
thing
the third big advantage is that name
conflicts are less likely to occur
so this relates to the fact that we of
course need to name the data variables
that are used to represent the abstract
data type somehow
and if these were exposed then we would
have to be sure that we don't use
variables with the same name because
then we would get naming conflicts that
would occur now if these representations
these variables that represent the data
within an adt are hidden in the adt it
means that that name is then limited to
the adt and therefore we could use the
same name somewhere else in our program
without worrying about it conflicting
with the variables defined within the
abstract data type
so what features must a programming
language provide in order to be able to
support adts
well first and foremost and what should
be obvious from our previous discussion
is that we need a syntactic unit and
this is of course because all adt's must
use a single syntactic unit to contain
their representation and their
operations
so the syntactic unit is then
responsible for encapsulating the adt's
type definition
we also require a method to make the
essential parts of an adt visible to a
client or a user
while still hiding the actual definition
of how the adt is represented in terms
of actual data
so the essential parts then of the adt
that should be visible will be of course
the type name for the adt because we
need to know what the type name is in
order to be able to create objects of
that particular adt
and then secondly we need sub-program
headers and these sub-program headers
will be representations of what
operations are supported by the abstract
data type so this will be then by means
of member functions or methods depending
on the programming language that we are
using which will be then defined for a
specific abstract data type the sub
program headers as we saw in our
discussion on the previous chapter only
need to include the details related to
the name return types and parameters
for these sub-programs and they don't
need to include the actual
implementation so generally the
implementation of these operations will
also be hidden within our adt
now there are of course several design
issues that need to be considered if a
high-level programming language is to
provide support for adts
the first design issue is what is the
form of the container for the interface
of the type
so when we're talking about the
interface to an adt we're talking about
the public interface that is exposed to
client or user code
so the public interface thing is the set
of operations that are publicly visible
to client or user code where that client
or user code can actually then invoke
those operations on the adt in question
so the
interface then needs to be contained
within some sort of unit
and this would be then our container
which also typically specifies the name
of the adt's type
and we need to consider what form this
container takes on so do we use for
instance a class to represent this
container or do we use some other kind
of construct
the second design issue is can abstract
data types be parameterized
so we spoke about parameterized
sub-programs in the previous chapter
where we used the examples of template
functions in c plus and generic methods
in java in a similar fashion we can also
create parameterized abstract data types
for instance in c plus we can create
template classes and in java we can
create generic classes
then the third design issue is what
access controls are provided access
controls
allow us to specify
the visibility of certain parts of our
abstract data type to client or user
code so here we're talking about things
like public private and protected access
controls
and then finally the last design issue
is is the specification of the adt
physically separate from its
implementation
so some high-level programming languages
such as c plus plus doing for say
separation where in c plus we have a
header file which contains the public
interface
as well as part of the representation
and then we have a secret implementation
file that contains the implementation
of our various operations within our
abstract data type some other
programming languages don't enforce this
kind of separation so for instance in
java there's no separation
between the specification of the type
and the implementation all of this falls
within the same class file
at this point we'll move on to some
examples of programming languages that
implement adts
and we will through this discussion then
look at different ways that the design
issues that we discussed on the previous
slide can be addressed in a high level
programming language
so the first language example we'll look
at is c plus and in c plus plus adt
support is based firstly on struct types
within the earlier c programming
language and we discussed structs
earlier on in this course
secondly adt support is also inspired by
classes within simulated 67
so the encapsulation device in c plus
for an adt is the class
and the class is then used to define an
abstract data type
now all class instances of a class then
share a single copy of the member
functions so the member functions are
the functions or operations that belong
to a particular adt
secondly we also then have data that is
represented within an adt
and this is represented by data members
which are essentially in the variables
within a class
and so each instance of a class then has
its own copy of the classes data members
so what this means is then each instance
of a class that is created has its own
separate data which doesn't interfere
with any other objects of the same class
now we saw earlier on in this course
that c plus plus allows for variables to
be static stack dynamic or heap dynamic
so instances of a class in other words
objects of a class behave in exactly the
same way and therefore instances of a
class can also be static or stack
dynamic or alternatively heap dynamic if
we use new to specifically allocate
space for the object on the heap
now in c plus information hiding is
achieved by means of access control
specifiers
and these are private public or
protected clauses
so private clauses specify entities
within a class that are hidden in other
words they are not accessible to client
or user code they are only accessible
within the class itself
public clauses on the other hand specify
the interface entities within our adt so
in other words the entities that are
directly accessible to client or user
code
and then finally we have protected
clauses and these come into play
when inheritance is implemented
for a particular class now we won't
discuss protected clauses in more detail
at this point
we will discuss them further in the next
chapter which deals with object oriented
programming
c plus plus has what are referred to as
constructors which are special functions
where their name is the same as the
class name for which they are defined
and constructors are responsible for
initializing the data members of an
instance in other words the
representation of the adt in question
now constructors do not create objects
the runtime system of c plus is
responsible for actually creating the
object however constructors are
implicitly called when an instance is
created now it is also possible to
explicitly call a constructor and one
would do this when creating a heap
allocated instance of the adt
using new for example
now if part of the object is heap
dynamic
so this would then occur in a situation
where we have a pointer defined within
our class
and this pointer would then be allocated
using new then the allocation of this
pointer would take place within the
constructor
so this is how heap dynamic storage is
allocated inside objects of a particular
adt
now constructors can also include
parameters and this allows us then to
parameterize objects
so
with
constructors that have parameters we
would typically then send through
initial values for the data that would
be stored within the adt object
now c plus allows the definition of
multiple constructors as long as each
constructor has a different set of
parameters
in addition to this however c plus also
provides another special function known
as a destructor
a destructor has the same name as the
class within which it resides however
this name is preceded by a tilde symbol
now the function of a d structure is
essentially the opposite of a
constructor where a construct is used to
allocate resources for a new object
of a particular adt a destructor is used
to clean up after an instance of the adt
is destroyed
so usually this involves reclaiming heap
storage in other words where we would
allocate heap storage using new in a
constructor we would de-allocate it
using a delete in the destructor
additionally however these structures
may also perform other cleanup
operations for example if an object of a
particular adt
maintains open files then the destructor
may be responsible for closing the
handles of these files
now a destructor is implicitly called
when the object's lifetime ends so for
example if we have a local object of a
particular adt
and it goes out of scope then the
destructor would implicitly be called
however it is also possible to
explicitly call a destructor and we can
only do this with heap allocated
objects of a particular adt in which
case we would use the delete special
word and this would then de-allocate
dynamically allocated storage
and we would of course have to do this
through a pointer to an object
c plus also provides support for friend
functions and friend classes
now friend functions and friend classes
allow these functions or classes to
access private members of a different
class
now friendship is granted in c plus so
what this means is if i have a class
called student for example then it isn't
possible for a function or another class
to claim friendship of the student class
the student class must within itself
define which functions or classes are
friends of the student class
any friend then whether it is a function
or a class can then directly access the
student classes private
members
now
generally speaking we will avoid
defining friend classes and this is
because it drastically increases the
exposure of private data
to classes that are not defined for the
specific adt
however sometimes friend functions are
necessary and they are typically used
where an operation is defined in which
the operator must work with multiple
classes so for example we may be
multiplying a matrix with a vector we
may then choose for the multiplication
operator to be defined inside the matrix
class
and then the vector class would define
this multiplication operation as a
friend operation this would then allow
the operator to both access the private
members contained within the matrix
clause as well as the vector class and
this is typically necessary because
multiplication works with the data
contained within each of those classes
next we'll look at a few examples of how
a stack adt can be implemented in c
the example on the next slide is a
relatively simple example of a stack
class
and here the representation and the
implementation of the class are
represented within a single unit so what
this means is we have the representation
of our class in other words the member
variables
as well as the prototypes for all of our
member functions but then also the
implementations of these member
functions and these will all appear
within the same unit
now this is not an ideal approach to use
the reason is that the client code will
be able to see the full implementation
of the stack class
so this means that the client may then
begin depending on the implementation
details and even if they don't depend on
the implementation details they may get
confused by these details
now the private data members are
provided at the top of the stack class
and these are not directly accessible to
client codes in other words client code
must go through the public interface of
the class
there's also one default constructor and
one destructor and then we also show the
implementation of one member function
which is for the push operation
on this slide we have the implementation
of our first basic stack class adt
example
over here you can see we are defining a
class and the name of the class is stack
generally the convention that we follow
is that class names start with an upper
case later
we can also see that the class is
delimited by an opening brace as well as
a closing brace at the end
and this indicates the beginning and the
end of our syntactic unit within which
our stack adt
is located
next we have a private label as you can
see over here and this means that
everything under the private label is
then private to the stack class so in
other words it can only be accessed by
the stack class and not by anything
external to the stack class such as
client code
so under the private section we have
listed a number of member variables and
these represent the data or
alternatively the representation
of our stack adt so we can see that we
have three variables here firstly we
have stack ptr
which is an integer pointer and this is
a pointer to an array that will be
dynamically allocated on the heap
next we have maxlin which is an integer
member variable and this represents the
largest possible subscript value within
our stack ptr array and then finally we
have top sub which is also an integer
value
and top sub indicates the subscript at
the top of our stack
next we have our public label over here
and this indicates that everything under
the public label is public
and therefore can be accessed externally
from outside of the stack class
so in other words client code can then
rely on these public member functions
so the first member function that we
have is our special function this is a
stack constructor we can see that it has
no return and it is named after the
class that it is contained in namely the
stack class
you can also see that there are no
parameters so this indicates that this
is the default constructor
so inside the body of our default
constructor we then set initial values
for our member variables
so stack ptr is initialized using new
which allocates memory for it on the
heap and we are allocating a new integer
array containing 100 integer values
maxlin is initialized to a value of 99
because that is the largest valid
subscript within the stack ptr array and
top sub is set to negative 1 which
indicates that there are no values
contained within the stack ptr array
here we have our d structure we know
this is a destructor because of its name
which contains the name of the class
that it is defined for but also
additionally has this tilde symbol
we don't have any parameters for our
stack destructor
inside our destructor all that we are
doing is deleting the stack ptr array so
we can see that it is allocated using
new in the constructor and then
de-allocated using delete in the
destructor
we also then have our final
implementation that we're showing over
here which is for a member function so
this is publicly available to the client
code and this is a member function
called push it returns nothing because
its return type is void and it receives
a single parameter called number which
is an integer value
so this then indicates the value that we
want to insert into our stack we then
perform a check using an if else
statement and we check to see whether
our top subscript is equal to max length
if it is then it means we have no more
space in our array so in that case we
simply print out a
error message to the standard error
stream
otherwise we enter the else portion
which means we can still insert a value
into our stack and so we access stack
ptr
at top sub which has been incremented by
a value of one so on the first insertion
top top sub will have been incremented
to a value of zero and that will then be
the first position that we insert a
value into the value of course that we
are inserting is number which is the
parameter value
we additionally have three more member
functions over here the implementations
are not shown but we have a pop
operation
top operation and an empty operation
the next example that we'll look at on
the next couple of slides is a better
implementation of the stack class and in
this implementation we enforce a
separation between a header file and an
implementation file and this allows us
to hide the object representation from
the client
so we'll begin by looking at the first
part of our implementation which is the
header file and typically this would be
stored in a dot h file so for our
example this would usually be in a stack
dot h file
now this header file is not compiled and
it only provides function prototypes
so the client can't depend on the
implementation of any of these functions
because the implementations will be in a
secret implementation file which we'll
get to in a moment
now private data members are also
provided in the header file and this is
unfortunately not ideal because the
client may start depending on the
representations in our stack class we
saw that we had three
data elements contained within it as
member variables
and these will then still be present
within our header files so the client
does then know for example
that an array is used in order to
represent our stack now unfortunately we
can't get away from this because the
compiler needs to know this information
and generally this is related to the
fact that the compiler needs to know the
size that a stack object will take up in
memory
so for example the compiler must know
the size of a stack class object for
memory allocation within client code and
this would typically happen when an
object of the stack class is created
either on the stack or the heap
so on this slide we have our stack.h
file which is the header file for our
stack class
we can see that once again we specify
that the class is named stack and we see
that we have braces that delimit our
class
we also have exactly the same private
label
and the three member variables stack ptr
maxlin and top sub
so these are of course visible only to
members of the stack class itself as
well as friends and there aren't any
friends of the stack class defined so
therefore these members are only visible
within the stack class
next we have our public label over here
and then we have all of the public
member functions that we defined in our
previous example including our
constructor our destructor and then our
push pop top and mt member functions
what's important to notice here is that
there are no bodies provided for any of
these functions
and the reason for this is that the
implementation will be provided in the
implementation file which we'll discuss
next
so the client then can only see this
header file and therefore they can only
see
which member functions are provided for
their use
this means that they can't rely on the
implementation of the constructor
destructor or any of the member
functions
now the second part of our beta class
implementation for the stack adt is
called the implementation file and this
is usually contained within either a dot
cpp or a dot c file so for our example
the implementation file would either be
stack dot cpp or stack dot c
now the implementation file is compiled
into an object file which is usually a
dot o or a dot obj file
now within a larger project all of the
implementation files are compiled into
separate object files so for example if
we had a binary search tree
class then its implementation file would
be binarysearchtree.co.cpp
and this would be compiled into a binary
search tree object file
once we've compiled all of our
implementation files into object files
then these object files are combined
together into an executable file by
means of the linking process which is
part of the compilation procedure
now the implementation file contains
definitions for our functions so in
other words the actual implementation of
all of the functions for which
prototypes were included in our stack.h
file
now it's also important to note that at
the top of the implementation file we
include the header file for that
implementation so in our example we
would include our stack dot h
file
at the top of our stack dot cpp or stack
stack.c file
and the reason for this is that the
header file is included wherever the
stack class is actually used
so because the stack.cpp file uses the
stack class we must include the stack.h
file right at the top of the stack.cpp
or stack.c file
additionally because our client code
also uses the stack class we must also
include them at the top of the client
code file and inclusion for our stack.h
file
finally on this slide we have the
implementation file for our beta
implementation of the stack class
we can see that this file is named
stack.cpp
and this includes the actual
implementation of all of the member
functions constructors and destructors
notice that we have a hash include over
here which includes the stack.h file the
stack.h file is included in quotation
marks and the reason for this is that it
is a user-provided header file as
opposed to a system provided header file
such as the iostream header file that
we've also included over here which is
contained within angled brackets
then we can see that we have the
implementations for our stack
constructor over here our stack
destructor and then our push member
function we would of course have had
implementations for all of the other
member functions as well but those are
emitted here just to make the example a
bit simpler these implementations are
exactly the same implementations as we
saw in our original simple example
now notice that none of these members
are included within a class construct
instead we specify for each one which
class it is a member of so here we have
specified that the stack constructor is
a member of the stack class
similarly we've also indicated that the
stack destructor is a member of the
stack class and finally that our push
member function is a member of the stack
class
right so that concludes our discussion
for this lecture
in the next lecture we will be
continuing with and finishing off our
discussion on chapter 11 of the textbook
5.0 / 5 (0 votes)