IMPLEMENTING ADTS IN THE BASE
LANGUAGE.
1. Simple ADTs
Many
programming languages already define some simple ADTs as integral parts of the
language. For example, the C language defines a simple ADT as an integer. The
type of this ADT is an integer with predefined ranges. C also defines several
operations that can be applied to this data type (addition, subtraction,
multiplication, division and so on). C explicitly defines these operations on
integers and what we expect as the results. A programmer who writes a C program
to add two integers should know about the integer ADT and the operations that
can be applied to it.
2. Complex ADTs
Although
several simple ADTs, such as integer, real, character, pointer and so on, have
been implemented and are available for use in most languages, many useful
complex ADTs are not. As we will see in this chapter, we need a list ADT, a
stack ADT, a queue ADT and so on. To be efficient, these ADTs should be created
and stored in the library of the computer to be used.
Model for
an abstract data type
The ADT
model is shown in Figure 12.1. Inside the ADT are two different parts of the
model: data structure and operations (public and private).
Implementation
Computer
languages do not provide complex ADT packages. To create a complex ADT, it is
first implemented and kept in a library. The main purpose of this chapter is to
introduce some common user-defined ADTs and their applications. However, we
also give a brief discussion of each ADT implementation for the interested
reader. We offer the pseudocode algorithms of the implementations as
challenging exercises.
3. STACKS
A stack
is a restricted linear list in which all additions and deletions are made at
one end, the top. If we insert a series of data items into a stack and then
remove them, the order of the data is reversed. This reversing attribute is why
stacks are known as last in, first out (LIFO) data structures.
Operations on stacks
The pop
operation deletes the item at the top of the stack. The following shows the
format.
The empty operation
The empty
operation checks the status of the stack. The following shows the format
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.