Lesson 4

Lesson 8

Abstraction

Reasoning about the essential properties of an object, ignoring the unimportant details.

It is the process of separating the inherent qualities of the actual physical object to which they belong.

Abstract Data Type (ADT)

A description of the domain of a type and the set of operations that can be performed on objects of that type.

Two examples of ADTs are :-
Stack

dynamic data structure

elements appear in Last In First Out (LIFO) order.

elements are removed and inserted at one end known as the TOP.

PUSH : operation involving addiing items to a stack.

POP : operation involving removing item from a stack.

eg: stack of books, plates etc.

may be implemented using pointers(dyanmic) or arrays (static).

Queue

dynamic data structure

elements appear in First In First Out (FIFO) order.

elements are removed at the front and inserted at the rear.

eg: a queue of people.

may be implemented using pointers(dynamic) or arrays (static).

PROGRAM StackExample;

CONST

MaxStack = 10;

TYPE

ElementType = Char;

StackElementType = Array [1..MaxStack] OF ElementType;

StackType = RECORD

Top : 0..MaxStack;

Element : StackElementType;

END;

VAR

Stack :StackType;

Ch : Char;

FUNCTION IsFull (St : StackType) : Boolean;

BEGIN

IsFull := St.Top = MaxStack;

END;

FUNCTION IsEmpty (St : StackType) : Boolean;

BEGIN

IsEmpty := St.Top = 0;

END;

PROCEDURE Initialise (VAR St : StackType);

BEGIN

St.Top := 0;

END;

PROCEDURE Push (VAR St : StackType;Item : ElementType);

BEGIN

If IsFull (St) THEN

WriteLn('Cannot Push - stack is FULL !')

ELSE

begin

St.Top := St.Top + 1;

St.Element[St.Top] := Item;

end;

END; { Push }

PROCEDURE Pop (VAR St : StackType;VAR Item : ElementType);

BEGIN

If IsEmpty (St) THEN

WriteLn('Cannot Pop - stack is EMPTY !')

ELSE

begin

Item := St.Element[St.Top] ;

St.Top := St.Top - 1;

end;

END; { Pop }

BEGIN { StackExample }

Push (Stack,'A');

Push (Stack,'b');

Push (Stack,'C');

Push (Stack,'d');

While NOT (IsEmpty(Stack)) DO

begin

POP (Stack, Ch);

WriteLn(Ch);

end;

ReadLn;

END. { StackExample }

QUEUE

Example - Array implementation

A queue can be implemented using an array.

eg: Array of character

[1] [2] [3] [4] [5]

Add character ‘C’ to the Queue

Add character ‘A’ to the Queue

Add character ‘Q’ into the Queue

Delete one item from the Queue

(‘C’ and ‘A’ will be removed)

Add two more items from the Queue

Delete two more items from the Queue

(‘C’ and ‘A’ will be removed)

In order to add more items to the Queue, the current items in the Queue must be moved to the front.