Chapter One

 Data Structure
In data structure, we study that how many ways are there to organize data. It means the
different possible ways of representing the data items in Computer memory.
 Logical or mathematical model of a particular organization of data is called a data
structure .The choice of a particular data model depends on two considerations.
o it must be rich enough in structure to represent the actual relationships of the
data in the real world.
o the structure should be simple enough that one can effectively process the data
when necessary
 Data structure Is a particular way of storing and organizing data in a computer so that it
can be used efficiently
 Different kinds of data structures are suited to different kinds of applications and some
are highly specialized to specific tasks

 Data Structure Operations

Following are the major operations:
 Traverse Accessing each record exactly once so that certain items in the
record may be processed. (This accessing and processing is sometimes
called "visiting" the record.)
 Search Finding the location of the record with a given key value, or finding
the locations of all records that satisfy one or more conditions
 Insert Adding a new record to the structure

 Delete Removing a Record from the data structure

 Sort Arranging the records in some logical order. (e.g. alphabetically

according to some NAME key, or in numerical order according to some
NUMBER key, such as account number)
 Merge Combining the records in two different sorted files into a single

Khurasan University, Jalalabad Page 1

 sorted [Link] operations, e.g., copying and concatenation, are also

used.

 Data Structure Classification

 Linear and Non Linear Data Structures
Linear data structure the data items are arranged in a linear sequence like in an array.
In a non-linear, the data items are not in sequence. An example of is a tree
 Homogenous and non- homogenous data structures.
An Array is a homogenous structure in which all elements are of same type.
In non-homogenous structures the elements may or may not be of the same type.
Records are common example.
 Static and dynamic Data structures
Static structures are ones whose sizes and structures associated memory location are
fixed at compile time Arrays, Records
Dynamic structures are ones, which expand or shrink as required during the program
execution and their associated memory locations change e.g.
Linked List
 Primitive Data Structures
They are not composed of other data structures Examples are: integers and characters
other data structures can be constructed from one or more primitives.

 Simple Data Structures

Built from primitives examples are strings, arrays, and records many programming
languages support these data structures.

 Algorithm
An algorithm is a finite set of instructions, which accomplishes a particular task.
OR

Khurasan University, Jalalabad Page 2

 An algorithm is a finite step-by-step list of well-defined instructions for solving a
particular problem.

Algorithms must satisfy the following criteria.

 Input: The algorithms must have input values from the specified set.

 Output: Each algorithm is written to produce the output.

 Definiteness: Each instruction must be clear and unambiguous.

 Finiteness: It means that algorithm must terminate in the finite number of steps.

 Effectiveness: Every algorithm must be effective which performs some specific Action on

the given data (i.e. means to produce a meaningful result).

 ALGORITHM NOTATION
A complete algorithmic notation is given below.
 Name of algorithm: Every algorithm is given an identifying name, written in capital
letters.
 Introductory Comments: The algorithm name is followed by a brief description of the
tasks the Algorithms perform.
 Steps: The algorithm is made of a sequence of numbered steps.
 Comments: An algorithm step may terminate with a comment enclosed in bracket,
which is used to help the reader better understand that step.

Khurasan University, Jalalabad Page 3

  Algorithm: AVERAGE
This algorithm reads four marks denoted by M 1, M2, M3, M4 and compute. The
average grade, placing it in average. All variables are assumed to be real.

(l) [Input individual marks]

Read (Ml, M2, M3, M4)
2) [Compute average grade]
Average = (M 1+M2+M3+M4)/4
3) [Output Result]
Print Average
4) [Finish]
Exit

 Algorithm – SUM
This algorithm get two numbers and to calculate their sum.
1. INPUT first number in N
2. INPUT second number in M
3. Add N to M and store result in s, i.e. s = N + M
4. Print s
5. End

Khurasan University, Jalalabad Page 4

  Algorithm – EXCHANGE VALUE
This algorithm exchange values of two variables.
1. N = 10 [assign value 10 to variable N]
2. M = 20 [assign value 20 to variable M]
3. Temp = N [assign value of N to variable Temp]
4. N = M [assign the value of M to N]
5. M = Temp [assign the value of Temp, i.e. previous value of N to M]

 Input & Output Statements

Input or Read statement is used in algorithms to enter data into a variable.

The statement is written as:
Input variable – name
For example, to input a value into variable N, the Input statement is written as:
Input N
Similarly, to print a message or contacts of a variable, PRINT statement is used with the
following format.
 PRINT message of variable name
The message is written within double quotes. To print the contents of a variable, it is
written without using double quotes. In C++, usually the “cin” object is used to get input from
the keyboard and “cout” object is used to print the output on the screen.

 Selection Statements
Selection statements are used for making decisions. The decision is made by testing a
given condition. After testing a condition, a statement or a set of statements are executed or
ignored. The structure that implements this logic in a programming language is called
conditional structure. A conditional statement is represented by the IF structure. It has one of
the following two forms:
1– IF condition THEN
Statement (s)
End IF

Khurasan University, Jalalabad Page 5

2- IF condition THEN
Statements
ELSE
Statements
End IF

In the first “IF structure”, the statements following the “IF structure” are executed when
the given condition is true. Otherwise, these statement(s) are ignored.

In the second “IF structure”, one of the two blocks of statements are executed. If the
given condition is true, then the block of statements under “IF statement” is executed
otherwise the block following the “ELSE statement” will be executed.

 Algorithm – GREATER NUMBER

This algorithm finds the greater of the two given numbers.
1. Start
2. Input two numbers in A & B
3. IF A > B THEN
PRINT “A is greater”
ELSE
PRINT “B is greater”
End IF
4. Exit

 Algorithm – GREATER NUMBER

This algorithm finds out the largest number from a given set of three numbers by using
nested IF structure.

1. Start
2. Input Three Numbers A, B & C.
3. IF A > B THEN
IF A > C THEN [Nested If Structure]
PRINT “A is greater”
ELSE
PRINT “C is greater”
END IF
ELSE
IF B > CTHEN

Khurasan University, Jalalabad Page 6

 PRINT “B is greater”
ELSE
PRINT “C is greater”
END IF
END IF
4. Exit

 Looping Statements
The looping statements are used to execute certain statement (s) repeatedly.
The statements that are executed repeatedly are called body of loop. In algorithm notation,
“Repeat” statement is used to execute the statements repeatedly. The “Repeat” statement has
two different forms:

 Repeat For Loop

 Repeat While Loop

 Repeat For Loop

“Repeat For” loop is used to execute statement(s) for a specified number of times. This
loop is also called the counter loop. Its general format is:
REPEAT FOR Index = I – value To F – value By S – value
Where

I-value represents the initial value for index variable.

F-value represents the final value.
S-value represents the step value, i.e. increment/decrement value.
Its use is optional. If it is omitted, the value of the index
Variable is incremented by 1 after each iteration.

The REPEAT FOR loop structure uses an index variable to control the number of
iterations of the loop. In the above syntax ‘Index’ is the control variable.

Khurasan University, Jalalabad Page 7

  Algorithm – NATURAL NUMBERS
This algorithm prints first ten natural numbers using REPEAT FOR Structure.

1. Start
2. REPEAT Step – 3 FOR C = 1 To 10 BY 1
3. PRINT C
[End of step – 2 Loop]
4. Exit
 Repeat WHILE Structure
This loop structure is used to execute a statement or a set of statements repeatedly
until the given condition remains true. It is also referred to as conditional loop. Its general
syntax is:

REPEAT WHILE (condition)

Body of loop
[end of loop]

The condition is tested at the beginning of the loop. There must be a statement in the body of
the loop that will change the condition during the execution of the program to bring it near the
specified condition.

 Algorithm – NATUAL NUMBERS

This algorithm print first ten natural numbers using REPEAT WHILE loop structure.

1. C = 1
2. Repeat Steps 3 To 4 WHILE (C <=10)
3. PRINT C
4. C = C + 1
[End of Step – 2 Loop]
5. Exit

Khurasan University, Jalalabad Page 8

  Sub-Algorithms
A sub-algorithm is a complete and independently defined algorithmic module. It is called
by the main algorithm or by some other sub-algorithm. It can receive values from the calling
algorithm. The general form of a sub-algorithm is:

Name (p1, p2, - - - - , pn)

{
Body of sub-algorithm
}
Where
Name: represents the name of sub-algorithm
P1,p2,----,pn: represent the parameters or arguments

The RETURN statement is used as the last statement of the sub-algorithm to return the
control back to the calling program.

 Type of Sub-Algorithm
The sub-algorithm is divided into two categories:
1- Function sub-algorithm
2- Procedure sub-algorithm
Both sub-algorithms are independent modules and are written to perform specific tasks.
The difference between the two that:
 The function sub-algorithm returns a single value to the calling algorithm through
RERUN statement.
 Procedure sub-algorithm may return more than one values. It returns values through
parameters.
 The function sub-algorithm is called as an expression or as a variable. The returned
value is used in an expression.
 The procedure sub-algorithm is called by the CALL statement in algorithms.
 Function: Mean (A, B, C)
Write a function sub-algorithm to find the average of three numbers.

MEAN (A, B, C)
1 AVG = (A+B+C)/3
2 Return (AVG)

Khurasan University, Jalalabad Page 9

  Procedure Algorithm – Exchange Values
Write a procedure sub-algorithm to interchange values of two variables.

Exchange (A, B)
1 TEMP = A
2 A = B
3 B = TEMP
4 RETURN

Khurasan University, Jalalabad Page 10

 Chapter Two
 Array
An array is a list of a finite number of homogeneous data elements such that
i) The elements of the array are referenced respectively by an index set consisting
of "n" consecutive numbers.
ii) The elements of an array are stored respectively in successive memory locations.
An array is a powerful data structure for storing and manipulating large blocks of data. It
is a group of related memory locations. These locations are referred to by one name.
There are different types of arrays but the most commonly used are:
I) One Dimensional arrays(Linear Array)
II) Two Dimensional arrays

 One Dimensional arrays

The simplest type of data structure is a Linear or one-dimensional array. It is like a list of
data items. For one dimensional array, a single subscript or index is used to access its
elements.
The number 'n' of elements is known as the length or size of the array.
In general the length or the number of data elements of an array can be obtained from
the index set by the formula
Length=UB - LB + 1
Where UB is the largest index, called the upper bound, and LB is the smallest index ,
called lower bound.
The element of an array A may be denoted by subscript notation
A1 , A2 , A3,………………………………, An

For example, the following is a one dimensional array A with 10 elements.

Length or Size of an array = 9 – 0 + 1 = 10

Khurasan University, Jalalabad Page 11

 An array A[10], where A is the name of the array and 10 is the maximum number of
elements that will be stored in this array i.e. A[0]=2, A[1]=4, A[2]=6, A[3]=3, A[4]=8,
A[5]=8, A[6]=9, A[7]= 2, A[8]=4, A[9]=2

EXAMPLE
(a) Let DATA be a 6-element linear array of integers such that
DATA [1] = 247 DATA [2] = 56 DATA [3] = 429 DATA [4] = 135 DATA
[5] = 87 DATA [6] = 156
Sometimes we will denote such an array by simply writing
DATA: 247, 56, 429, 135, 87, 156
The array DATA is frequently pictured as in Fig. (a) or Fig. (b).
DATA
1 247
2 56 DATA
3 429
247 56 429 135 87 156
4 135
5 87 1 2 3 4 5 6
6 156

(a) (b)

(b) An automobile company uses an array AUTO to record the number of automobiles sold
each year from 1932 through 1984. Rather than beginning the index set with 1. If is
more useful to begin the index set with 1932 so that

AUTO[K] = number of automobiles sold in the year K

Then LB = 1932 is the lower sound and UB = 1984 is the upper bound of AUTO.
Length = UB –LB +1 = 1984- 1930 +1 = 55

Khurasan University, Jalalabad Page 12

  REPRESENTATION OF LINEAR ARRAYS IN MEMORY
Let LA be a linear array in the memory of the computer as we know that the memory of the
computer is simplify a sequence of addressed locations. Let us use the notation
LOC(LA[K]) = address of the element LA[K] of the array LA
the elements of LA are stored in successive memory [Link] computer does not need to keep
track of the address of every element of LA, but needs to keep track only of the address of the
first element of LA, denoted by
Base(LA)
And called the base address of LA. Using this address Base(LA), the computer calculates the
address of any element of LA by the following formula:
LOC(LA[K]) = Base(LA) + w(K- lower bound)
Where w is the number of words per memory cell for the array LA. Observe that the time to
calculate LOC(LA[K]) is essentially the same for any value of K. furthermore, given any subscript
K , one can locate and access the content of LA[K] without scanning any other element of LA.

 Operations on Linear Arrays

 TRAVERSING LINEAR ARRAYS

Let A be a collection of data elements stored in the memory of the computer. Suppose we want
to print the contents of each element of A of suppose we want to count the number of
elements of A with a given property. This can be accomplished by traversing A, that is , by
accessing and processing (frequently called visiting) each element of A exactly once.

 Traversing using While Loop

Algorithm 1. (Traversing a linear Array) Here LA is a linear array with lower bound LB and
upper bound UB. This algorithm travers LA applying an operation PROCESS to each element of
LA.
1. [Initialize counter .] set K=LB.
2. Repeat Steps 3 and 4 while K≤UB.
3. [Visit element .] Apply PROCESS to LA[K].
4. [Increase counter.] set K=K+1.
[End of Step 2 loop.]
5. Exit.

 Traversing using For Loop

Algorithm 2. (Traversing a linear Array) This algorithm traverses a linear array LA with lower
bound LB and upper bound UB.
1. Repeat for K = LB to UB:
Apply PROCESS to LA[K].
[End of loop.]
2. Exit
 INSERTING AND DELETING

Khurasan University, Jalalabad Page 13

Let A be a collection of data elements in the memory of the computer. “Inserting” refers to the
operation of adding another element to the collection A, and “deleting” refers to the operation
of removing one of the elements from A . This section discusses inserting and deleting when A
is a linear array.
Inserting an element at the “end” of a linear array can be easily done provided the memory
space allocated for the array is large enough to accommodate the additional element. On the
other hand, suppose we need to insert an element in the middle of the array. Then, on the
average, half of the element must be moved downward to new locations to accommodate the
new element and keep the order of the elements.

 Insertion in linear Array

Algorithm 3. (Inserting into a Linear array) INSERT(LA, N, K, ITEM)
Here LA is a linear array with N elements and K is a positive integer such that
K≤N. This algorithm inserts an element ITEM into the Kth position in LA .
1. [Initialize counter.] Set J=N.
2. Repeat Step 3 and 4 while J ≥ K.
3. [Move Jth element downward.] Set LA[J+1] = LA[J].
4. [Decrease counter.] Set J = J – 1.
[End of Step 2 loop.]
5. [Insert element.] Set LA[K] = ITEM.
6. [Reset N.] Set N = N+1.
7. Exit

 Deletion in linear Array

Algorithm 4. (Deleting from a linear Array) DELETE(LA, N, K, ITEM)
Here LA is a linear array with N elements and K is a positive integer such
that K ≤ N. This algorithm deletes the Kth element from LA.
1. Set ITEM = LA[K].
2. Repeat for J = K to N-1:
[Move J + 1st element upward.] Set LA[J] = LA[J+1].
[End of loop.]
3. [Reset the number N of elements in LA.] Set N = N-1.
4. Exit.

Khurasan University, Jalalabad Page 14

  Two-Dimensional Arrays
The two dimensional array consists of rows and columns. It is also. Called table or matrix. The
elements of a two-dimensional array are referenced by two subscripts or index values. A
matrix with the same number of rows and columns is called square matrix.
The elements of the array are denoted as:
A [ i, j]
i – represents the row number
j – represents the column number
a two-dimensional array abc having 2 rows and 3 columns is shown below
abc
(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)

The total number of elements of a two-dimensional array having m rows and n columns is m x
n. For example, an array having 2 rows and 4 columns has 2 x 4 = 8 elements.
Each programming language has different rules to declare multi-dimensional arrays. In
C++, a two-dimensional array “temp” of integer data type having 6 rows and 4 columns is
declared as:
Int temp [6] [4] ;
 Representation of Two-Dimensional Arrays In Memory
Two-dimensional arrays are represented in memory in two ways. These are Row-major
order and Column-major order.
In row-major order, a two-dimensional array is represented in memory by row order.
For example, a two-dimensional array having 2 rows and 3 columns is stored in row-major
order as:
{X[1, 1], X[1, 2], X[1, 3]}, {X[2, 1], X[2, 2], X[2, 3]}
In column-major order, a two-dimensional array is represented in memory by column
order. For example, a two-dimensional array having 2 rows and 3 columns is stored in
column-major order as:
{X[1, 1], X[2, 1]}, {X[1, 2], X[2, 2]}, {X[1, 3], X[2, 3]}

Bibliography
1. Data Structures by SEYMOUR LIPSCHUTZ ( SCHAUM `S Outlines)
2. Data Structures in C++ By Muhammad Tauqeer ( AIKMAN SERIES)
3. Data Structures and Algorithms in C++ by Michael T. Goodrich, Roberto Tamassia and
David Mount (WILEY)

Khurasan University, Jalalabad Page 15

 Chapter Three
 STACKS
A stack is a special kind of linear list in which only two operations, insertion and deletion,
can be performed. These operations may occur only at its top end. The item in it are stored and
retrieved in last In First Out (LIFO) manner.
Examples: a stack of dishes, a stack of coins and a stack of folded towels.

Or:
A stack is a list of elements in which an element may be inserted or deleted only at one
end, called the top of the stack. This means, in particular, that elements are removed from a
stack in the reverse order of that in which they were inserted into the stack.
(a) “Push” is the term used to insert an element into a stack.
(b) “Pop” is the term used to delete an element from a stack.
These terms are used only with stacks, not with other data structures.

EXAMPLE
Suppose the following 6 elements are pushed, in order, onto an empty stack:

AAA, BBB, CCC, DDD, EEE, FFF

Figure shows three ways of picturing such a stack.

STACK: AAA, BBB, CCC, DDD, EEE, FFF

Khurasan University, Jalalabad Page 16

 1 AAA
2 BBB
3 CCC
TOP
4 DDD
TOP EEE
5
FFF
6 FFF
EEE
7
DDD
8
CCC
9
BBB
AAA
N–1
N

(a) (b)
AAA BBB CCC DDD EEE FFF …

1 2 3 4 5 6 7 8 9 … N–1 N

TOP
Fig. Diagrams of stacks.

Array Representation of Stack

Stacks may be represented in the computer in usually by one-way list or a linear array.
Each of our stacks will be maintained by a linear array STACK; a pointer variable TOP, which
contains the location of the top element of the stack; and a variable MAXSTK which gives the
maximum number of elements that can be held by the stack. The condition TOP = 0 or TOP =
NULL will indicate that the stack is empty.
Figure pictures such an array representation of a stack. (For notational convenience, the array is
drawn horizontally rather than vertically.) Since TOP = 3, the stack has three elements, XXX, YYY
and ZZZ; and since MAXSTK = 8, there is room for 5 more items in the stacks.

STACK
XXX YYY ZZZ

1 2 3 4 5 6 7 8

TOP 3 MAXSTK 8

Fig

Khurasan University, Jalalabad Page 17

 The operation of adding (pushing) an item onto a stack and the operation of removing
(popping) an item from a stack may be implemented, respectively, by the following procedures,
called PUSH and POP. In executing the procedure PUSH, one must first test whether there is
room in the stack for the new item; if not, then we have the condition known as overflow.
Analogously, in executing the procedure POP, one must first test whether there is an element in
the stack to be deleted; if not, then we have the condition known as underflow.

Procedure: PUSH(STACK, TOP, MAXSTK, ITEM)

This procedure pushes an ITEM onto a stack.

1. [Stack already filled?]

If TOP = MAXSTK, then: Print: OVERFLOW, and Return.
2. Set TOP := TOP + 1. [Increases TOP by 1.]
3. Set STACK[TOP] := ITEM. [Inserts ITEM in new TOP position.]
4. Return.

Procedure: POP(STACK, TOP, ITEM)

This procedure deletes the top element of STACK and assigns it to the variable ITEM.

1. [Stack has an item to be removed?]

If TOP = 0, then: Print: UNDERFLOW, and Return.
2. Set ITEM := STACK[TOP]. [Assigns TOP element to ITEM.]
3. Set TOP := TOP -1. [Decreases TOP by 1.]
4. Returen.

Frequently, TOP and MAXSTK are global variables; hence the procedures may be called
using only
PUSH(STACK, ITEM) and POP(STACK, ITEM)
Respectively. We note that the value of TOP is changed before the insertion in PUSH but the
value of TOP is changed after the deletion in POP.

EXAMPLE
(a) Consider the stack in Fig. we simulate the operation PUSH(STACK, WWW):

1. Since TOP = 3, control is transferred to Step 2.

2. TOP = 3 + 1 = 4,
3. STACK[TOP] = STACK[4] = WWW.
4. Return.
Note that WWW is now the top element in the stack.

Khurasan University, Jalalabad Page 18

 (b) Consider again the stack in Fig. this time we simulate the operation POP(STACK, ITEM):

1. Since TOP = 3, control is transferred to Step 2.

2. ITEM = ZZZ
3. TOP = 3 – 1 = 2.
4. Return.

 Evaluation of Expressions
An arithmetic expression is made up of operands, arithmetic operators and parentheses.
The operands may be numeric variables or numeric constants. Following are some examples of
arithmetic expressions:
A+B, X*Y, A*(B-C)/2, (A+B)^2
The arithmetic operators +, -, * and / are the same that are used in ordinary algebra. The
operator ^ is used as to compute the exponential. This operator is not available in C++. Instead
‘pow’ function is used to calculate the exponential. The expression is always evaluated from left
to right. The order in which the expression is evaluated is:

o If the expression has parenthesis, then they are evaluated first.

o Exponential (^) is given highest priority.
o Multiplication (*) and division (/) have the next highest priority.
o Addition (+) and subtraction (-) have the lowest priority.

Example: Describe the steps to evaluate the following expression.

2^3 + 6*2 - 9/3

Step-1: The expression is evaluated from left to right. Exponential is evaluated first. After
evaluating the exponential, the expression becomes:

= 8 + 6*2 - 9/3

Step-2: Multiplication and division are performed nest and the expression becomes:

= 8 + 12 - 3

Step-3: Addition and subtraction are performed last, from left to right, and the final
result is;

= 17

Khurasan University, Jalalabad Page 19

 Polish Notation
In most arithmetic expressions, the arithmetic operator is plaved between two operands,
e.g. x+y, x/y. The type of notation is called infix notation. In polish notation, however, the
arithmetic operator is placed before its two operands. Following are some examples of polish
notation.

Infix notation Polish notation

i) X+Y +XY

ii) X/Y /XY

iii) (X+Y) *Z *+XYZ

iv) X+(Y*Z) +X*YZ

Since the operators are used before the operands in polish notation, it is also called
prefix notation. The polish notation is named in honour of polish mathematics Jan Lukasiewiez.
Parenthesis are not used in polish notation.

 Reverse Polish Notation or Postfix Notation

In this notation the arithmetic operator is placed after the operands. This notation is
also known as suffix notation. The following table shows expressions in infix notation and
equivalent prefix and postfix notations.

Prefix Postfix
Infix
(Polish notation) (Reverse Polish notation)
A+B +AB AB*
A*B *AB AB*
A/B /AB AB/
A-B -AB AB-

The computer evaluate an expression given in infix notation by converting it into postfix
notation. The stack is used to perform this operation.
The following steps are taken to evaluate a postfix expression:

Khurasan University, Jalalabad Page 20

 1. The expression is scanned from left to right until the end of the expression.
2. When an operands is encountered, it is pushed into stack.
3. When an operator is encountered, then:
 The top two operands of stack are removed.
 The arithmetic operation is performed.
 The computed result is pushed back to the stack.
4. When end of the expression is reached, the top value from the stack is
picked. It is the computed value of the expression.

Example:
Consider the following arithmetic expression P written in postfix notation:
P: 5, 6, 2, +, *, 12, 4, /, ₋
Symbol Scanned STACK
(1) 5 5
(2) 6 5, 6
(3) 2 5, 6, 2
(4) + 5, 8
(5) * 40
(6) 12 40, 12
(7) 4 40, 12, 4
(8) / 40, 3
(9) – 37

Example: Evaluate expression 12, 6, 1, 3, -, 4, 5, *, +,

Symbol Scanned STACK

(1) 12 12
(2) 6 12, 6
(3) / 2
(4) 3 -1
(5) 4 -1, 4
(6) 5 -1, 4, 5
(7) * -1, 20
(8) + 19
(9)

Khurasan University, Jalalabad Page 21

 Infix to Postfix Conversion
The stack is used to convert an infix expression to postfix. The stack is used to store
operands and then pass to the postfix expression according to their precedence. The infix
expression is converted into postfix expression according to the following rules:
1. The infix expression is scanned from left to right until end of the expression.
2. Whenever an operand is encountered, it is added to the output, i.e. to the postfix
expression.
3. Each time an operator is read, the stack is repeatedly popped and operators are
passed to the output, until an operator is reached that has a lower precedence than
the most recently read operator. The most recently read operator is then pushed
onto the stack.
4. When end of the infix expression is reached, all operator remaining in the stack are
popped and passed to the output in the same sequence.
5. Parenthesis can be used in the infix expression but these are not used in the postfix
expression. During conversion process, parentheses are treated as operators that
have higher precedence than any other operator. The left parenthesis is pushed into
the stack when encountered.
6. The right parenthesis is never pushed to the stack. The left parenthesis is popped
only when right parenthesis is encountered. The parentheses are not passed to the
output postfix expressions; they are discarded.
7. When end of expression is reached, then all operators from stack are popped and
added to the output.

Example Convert the following infix expressions into postfix expressions:

1. (A+B) *C
2. A+ (B*C)
3. A+B*C+ (D*E+F) *G

Khurasan University, Jalalabad Page 22

 (i) (A+B) *C
Steps Symbol Scanned Stack Output
1 ( (( Empty
2 A (( A
3 + ((+ A
4 B ((+ AB
5 ) ( AB+
6 * (* AB+
7 C (* AB + C
8 ) Empty AB + C*

(ii) A+ (B*C)
Steps Symbol Scanned Stack Output
1 A ( A
2 + (+ A
3 ( (+ ( A
4 B (+ ( AB
5 * (+ ( * AB
6 C (+ ( * ABC
7 ) (+ ABC*
8 ) Empty ABC* +

Khurasan University, Jalalabad Page 23

 (iii) A+B *C + (D*E+F) * G
Step Symbol Scanned Stack Output
1 A Empty A
2 + (+ A
3 B (+ A B
4 * ( +* A B
5 C ( +* A B C
6 + (+ A B C * +
7 ( (+( A B C * +
8 D (+( A B C * + D
9 * ( + (* A B C * + D
10 E ( + (* A B C * + D E
11 + (+(+ A B C * + D E *
12 F (+(+ A B C * + D E * F
13 ) (+ A B C * + D E * F +
14 * ( +* A B C * + D E * F +
15 G ( +* A B C * + D E * F + G
16 ) Empty A B C * + D E * F + G * +

Khurasan University, Jalalabad Page 24

 Chapter Four
 QUEUES
A queue is a linear list of elements in which deletions can take place only at once
end, called the front, and insertions can take place only at the other end, called the rear,
the terms “front” and “rear” are used in describing a linear list only when it is
implemented as a queue.
Queues are also called first-in first-out (FIFO) lists, since the first element in a
queue will be the first element out of the queue. In other words, the order in which
elements enter a queue is the order in which they leave. This contrasts with stacks,
which are last-in first-out (LIFO) lists.
For example: The people waiting in line at a bank form a queue, where the first person
in line is the first person to be waited on; and so on. An important example of a queue in
computer science occurs in a timesharing system, in which programs with the same
priority form a queue while waiting to be executed.

 Representation of Queues
Queues may be represented in the computer is usually be means of one-way lists or
linear arrays. Each of our queues will be maintained by a linear array QUEUE and two
pointer variables: FRONT, containing the location of the front element of the queue; and
REAR, containing the location of the rear element of the queue. The condition FRONT =
NULL will indicate that the queue is empty
Observe that whenever an element is deleted from the queue, the value of FRONT is
increased by 1; this can be implemented by the assignment
FRONT = FRONT + 1
Similarly, whenever an element is added to the queue, the value of REAR is
increased by 1; this can be implemented by the assignment
REAR = REAR + 1
QUEUE

Khurasan University, Jalalabad Page 25

FRONT: 1
REAR: 4 AAA BBB CCC DDD ...

1 2 3 4 5 6 7 ... N

(a)

QUEUE
FRONT: 2
REAR: 4 BBB CCC DDD ...

1 2 3 4 5 6 7 ... N

(b)

QUEUE
FRONT: 2
REAR: 6 BBB CCC DDD EEE FFF ...

1 2 3 4 5 6 7 ... N

(c)

QUEUE
FRONT: 3
REAR:(d) 6 CCC DDD EEE FFF ...

1 2 3 4 5 6 7 ... N

(d)

Fig. Array representation of a queue.

QUEUE is circular, that is, that QUEUE[1] comes after QUEUE[N]. in the array.
With this assumption, we insert ITEM into the queue by assigning ITEM to QUEUE[1].
Specifically, instead of increasing REAR to N + 1, we reset REAR = 1 and then assign
QUEUE[REAR] = ITEM
Similarly, if FRONT = N and an element of QUEUE is deleted, we reset FRONT = 1
instead of increasing FRONT to N + 1.
Suppose that our queue contains only one element, i.e., suppose that
FRONT = REAR ≠ NULL
And suppose that the element is deleted. Then we assign
FRONT = NULL and REAR = NULL
To indicate that the queue is empty

Khurasan University, Jalalabad Page 26

EXAMPLE
Figure shows how a queue may be maintained by a circular array QUEUE with N =
5 memory locations. Observe that the queue always occupies consecutive locations
except when it occupies locations at the beginning and at the end of the array.
QUEUE
(a) Initially empty: FRONT: 0
REAR: 0
1 2 3 4 5

(b) A, B and then C inserted: FRONT: A B C

1
REAR: 3

(c) A deleted: FRONT:

B C
2
REAR:
3

(d) D and E inserted: FRONT:

B C D E
2
REAR:
5

(e) B and C deleted: FRONT:

D E
4
REAR:
5

(f) F inserted: FRONT:

F D E
4
REAR:
1

(g) D deleted: FRONT:

F E
5
REAR:
1

Khurasan University, Jalalabad Page 27

 (h) G and then H inserted: FRONT:
F G H E
5
REAR:
3
(i) E deleted: FRONT:
F G H
1
REAR:
3

(j) F deleted: FRONT:

G H
2
REAR:
3

(k) K inserted: FRONT:

G H K
2
REAR:
4

(l) G and H deleted: FRONT:

K
4
REAR:
4

(m) K deleted, QUEUE empty: FRONT:

0
REAR:
0

Procedure: QINSERT(QUEUE, N, FRONT, REAR, ITEM)

This procedure inserts an element ITEM into a queue.

1. [Queue already filled?]

If FRONT = 1 and REAR = N, or if FRONT = REAR +1, then:
Write: OVERFLOW, and Return.
2. [Find new value of REAR.]
If FRONT = NULL, then: [Queue initially empty.]

Khurasan University, Jalalabad Page 28

 Set FRONT = 1 and REAR = NULL.
Else if REAR = N, then;
Set REAR = 1.
Else:
Set REAR = REAR + 1.
[End of If structure.]
3. Set QUEUE[REAR] = ITEM, [This inserts new element.]
4. Return.

Procedure: QDELETE(QUEUE, N, FRONT, REAR, ITEM)

This procedure deletes an element from a queue and assigns it to the
variable ITEM.

1. [Queue already empty?]

If FRONT = = NULL, then: Write: UNDERFLOW, and Return.
2. Set ITEM = QUEUE[FRONT].
3. [Find new value of FRONT.]
If FRONT = REAR, then: [Queue has only one element to start.]
Set FRONT = NULL and REAR = NULL.
Else if FRONT = N, then:
Set FRONT = 1.
Else:
Set FRONT = FRONT + 1.
[End of If structure.]
4. Return.

Khurasan University, Jalalabad Page 29

 DEQUES (double ended queue)
A deque (pronounced either “deck” or “dequeue”) is a linear list in which elements can be added or
removed at either end but not in the middle.
Deque is maintained in memory by a circular array DEQUE with pointers LEFT and RIGHT, which point to
the two ends of the deque. Figure pictures two deques, each with 4 elements maintained in an array
with N = 8 memory locations. The condition LEFT = NULL will be used to indicate that a deque is empty.

DEQUE
LEFT: 4
RIGHT: 7 AAA BBB CCC DDD

1 2 3 4 5 6 7 8

(a)

DEQUE
LEFT: 7
RIGHT:(b) 2 YYY ZZZ WWW XXX

1 2 3 4 5 6 7 8

(d)
There are two variations of a deque-namely, an input-restricted deque and an output-restricted deque.
Specifically, an input-restricted deque is a deque which allows insertions at only one end of the list but
allows deletions at both ends of the list; and an output-restricted deque is a deque which allows
deletions at only one end of the list but allows insertion at both ends of the list.

PRIORITY QUEUES
A priority queue is a collection of elements such that each element has been assigned a priority and such
that the order in which elements are deleted and processed comes from the following rules:

(1) An element of higher priority is processed before any element of lower priority.
(2) Two elements with the same priority are processed according to the order in which they
were added to the queue.

A prototype of a priority queue is a timesharing system: programs of high priority are processed first,
and programs with the same priority from a standard queue.

One-Way List Representation of a Priority Queue

One way to maintain a priority queue in memory is by means of a one-way list, as follows:

(a) Each node in the list will contain three items of information: an information field INFO, a priority
number PRN and a link number LINK.
(b) A node X precedes a node Y in the list (1) when X has higher priority than Y or (2) when both
have the same priority but X was added to the list before Y. this means that the order in the
one-way list corresponds to the order of the priority queue.

Priority numbers will operate in the usual way: the lower the priority number, the higher the priority.

Khurasan University, Jalalabad Page 30

SEARCHING & SORTING

Searching & sorting are two most important operations that are frequently performed on data
structures. These are fundamental operations in computer science. These are mostly performed on data
structures like arrays, linked lists.

SEARCHING

Computer systems are often used to store large amounts of data from which individual records
are retrieved according to some search criterion. The process of finding a specific data item or record
from a list is called searching.
The efficient storage of data to facilitate fast searching is an important task. All other operations like
inserting, deletion, etc. are dependent on this operation. For example, to delete a data item from a list,
its position is first located in the list and then the deletion operation is performed.

The search is successful if the specified data item or record is found during searching process.
Search operation terminates when it is successful. If the specified data is not found then the search is
unsuccessful. Different techniques are used to carry out search operations. The commonly used
searching methods are:

 Sequential Search
 Binary Search

Sequential Search

The sequential search is a simple and straightforward technique to search a specified item in an
unordered list. The specified value is searched in the list sequentially, i.e. starting from the first element
to the last element in the list in a sequence. When the required value is found, search operation stops.

The sequential search is a slow process. It is used for small amounts of data. This method is not
recommended for large amount of data.

BINARY SEARCH

It is a more efficient technique to search a specific item from list of item.

It is mostly used for relatively large lists or table of records that are sorted in ascending or descending
order.
A binary search begins by searching the required value from the middle of the list. If the
required value is in the middle of the list then search process terminates at that point. If the list is sorted
in ascending order and the required value is greater than the value at the middle, the control goes to the
higher value to search the required value. Similarly, if the list is sorted in ascending order and the
required value is less than the value at the middle, the control goes to the lesser values to search the
required value. In both cases, half of the list is searched to find the required value.

Khurasan University, Jalalabad Page 31

Searching is a process of finding an element within the list of elements stored in any order or randomly.
Searching is divided into two categories linear and binary search. Linear searching is the basic and
simple method of searching. Less time is taken by binary search to search an element from the sorted
list of elements. So it is t say that binary search method is more efficient than the linear search. The only
drawback between the two searches is that when where there is no prerequisite for the linear search.

LINEAR SEARCHING
In linear search, we access each element of an array one by one sequentially and see whether it is
desired element or not. A search will be unsuccessful if all the elements are accessed and the desired
element is not found.
Therefore linear search can be defined as the technique which traverses the array sequentially to locate
the given item.

Algorithm
Here a is a linear array with n elements, and item is a given item of information. This algorithm finds the
location loc of item in a, or set loc = 0 if the search is unsuccessful.
1. [Insert item at the end of data.] Set data [n+1] = item.
2. [Initialize counter] set loc = 1.
3. [Search for item ]
Repeat while data [loc] =! item:
Set loc = loc + 1.
4. Successful] if loc = n + 1, then set loc = 0.
5. Exit.

BINARY SEARCHING
Binary search is an extremely efficient algorithm. This search technique searches the given item in
minimum possible comparisons. To do the binary search, first we had to sort the array elements. The
logic behind this technique is given below :
 First find the middle element of the array.
 Compare the mid element with an item
 There are three cases :
(a) If it is a desired element then search is successful.
(b) If it is less than desired item then search only the first half of the array.
(c) If it is greater than the desired element search in the second half of the array

Searched in 1st half of array Mid value Searched in 2nd half of array


  
First value Mid = (First + last)/2 Last value

Binary Search Sketch Diagram for Middle Value

Repeat the same steps until an element is found or exhausts in the search area. In this algorithm every
time we are reducing the search area. So number of comparisons keeps on decreasing. So it is an
efficient algorithm compared to linear search but the array has to be sorted before doing binary search.

Khurasan University, Jalalabad Page 32

 Algorithm
Here a is sorted array with lower bound LB and upper bound UB, and item is a given item of information.
The variables beg, end and mid denoted, respectively, the beginning, end and middle location of a
segment of element of a. this algorithm finds the location loc of item in a or sets loc = NULL.
1. [Initialize segment variables]
Set beg = LB, end = UB and mid = int ( ( beg + end ))/2
2. Repeat steps 3 and 4 while beg <= end and a [mid] != item
3. If item < a [mid], the
Set end = mid -1
Else
Set be = mid + 1
[End of if structure]
4. Set mid = int ((beg + end )) /2
[End of step 2 loop]
5. If a[mid]= item then
Set loc = mid
Else
Set loc = NULL
[End of if structure]
6. exit

Suppose we have an array a of 7 elements

9 12 24 30 36 45 70
0 1 2 3 4 5 6

The steps to search 45 using binary search in array a[7] are:

Step I : The given array is in ascending order ; item ot be searched for is 45.
Beg = 0, last = 6
Mid = int ((beg + last)/2) = int (0 + 6/2) = int (3) = 3

Beg Last
0 1 2 3 4 5 6
9 12 24 30 36 45 70

Step II : a[mid] i.e. a[3] is 30

30 < 45 then
Beg = mid + 1 = 3 + 1 = 4

Step III : mid = int((beg + last)/2) = int (4 + 6) / 2 = int (5) = 5

beg Last
4 5 6
36 45 70
a[mid] i.e. a[5] is 45.
45 = 45
Search successful ! ! At location number 5 (element number 6).

Khurasan University, Jalalabad Page 33

Sorting
Introduction
Sorting is a basic operation in computer science. Sorting refers to the operation of arranging data in
some given sequence i.e., increasing order or decreasing order.
Sorting is categorized as Internal Sorting and External Sorting. By internal sorting means we are
arranging the numbers within the array obnly which is in computer primary memory, whereas the
external sorting is the sorting of numbers from the external file by reading it from secondary memory.

SORTING
Let p be a list of m elements p1, p2, p3 , . . ., pn in memory. Sorting p means arranging the contents of p
in either increasing or decreasing order i.e.,

p1≤ p2 ≤ p3 ≤ p4 ≤ p5 . . . ≤pn
There are m elements in the list, therefore there are m! ways to arrange them.

Example
Suppose an array value contain 10 elements as follows:
VALUE : 7, 9, 3, 6, 8, 2, 1, 4, 18, 5
After Sorting, VALUE must appear as
VALUE : 1, 2, 3 4, 5, 6, 7, 8, 9, 18

BUBBLE SORT
In bubble sort, each element is compared with its adjacent element. If the first element is larger than
the second one then the position of the elements are interchanged, otherwise it is not changed. Then
next element is compared with its adjacent element and the same process is repeated for all the
elements in the array. During the pass, the second largest element occupies the second last position.
During the next pass, the same process is repeated leaving the largest element. During this pass, the
largest element occupies the n-1 position. The same process is repeated until no more elements are left
for comparison.
Finally the array is sorted one.

The various steps involved in sorting of an array of 5 elements are given as under :
INITIAL ELEMENTS (without sorting)
11
15
2
13
6

Khurasan University, Jalalabad Page 34

 FIRST PASS
11 no swapping 11 11 11
2 2 swapped 2 2
15 15 13 swapped 13
13 13 6 6 swapped
6 6 15 15
SECOND PASS
2 swapped 2 2 2
11 11 no swapped 11 11
13 6 6 swapped 6
6 13 13 13 no swapping
15 15 15 15
THIRD PASS
2 no swapping 2 2 2
11 6 swapped 6 6
6 11 11 no swapping 11
13 13 13 13 no swapping
15 15 15 15

Algorithm : Bubble Sort a[N]

This algorithm sorts the Array A with N elements
1. initialization
set I = 0
2. REPEAT steps 3 to 5 until I < N
3. Set J = 0
4. REPEAT step 5 until J < N – I – 1
5. If A[J] > A [ J + 1 ] then
Set temp = A[ J ]
Set A[ J ] = A[ J + 1 ]
Set A[ J + 1] = temp
End If
6. Exit

Khurasan University, Jalalabad Page 35

SELECTION SORT
The selection sort technique is based upon the extension of the minimum/maximum technique. By
means of a nest of for loops, a pass through the array is made to locate the minimum value. Once this
found, it is placed in the first position of the array (position 0). Another the remaining elements, is made
to find the next smallest element, which is placed in the second position (position 10, and so no. once
the next to last element is compared with the last element, all the elements have been sorted into
ascending order.

More precisely : Let a be a linear array of n elements.

Pass 1. Find the location loc of the smallest in the list of n elements.
A[1], a[2], . . . , a[n], and then interchange a[loc] and a[1]. Then :

Pass 2. Find the location loc of the smallest in the sub list of n – 1 elements
a[2], a[3], . . , a[n], and then interchange a[loc] and a[2]. Then :
a[1], a[2] is stored, since a [1] ≤ a[2].

Pass 3. Find the location loc of the smallest in the sub list of n-2 elements
a[3], a[4], . . , a[n], and then interchange a[loc] and a[3]. Then :
a[1], a[2], . . , a[3] is stored, since a[2] ≤ a[3].

... .......................................................................

... .......................................................................

Pass n – 1. Find the location loc of the smaller of the elements a[n – 1], a[n], and then interchange
a[loc] and a[n – 1]. Then :
a[1], a[2], . . , a[n] is stored, since a[n – 1] <<=a[n].
Thus a is sorted after n – 1 passes.

For example, suppose we have a list, which contains the elements: 40, 30, 50, 20 and 10. If we want to
sort this list of elements using the selection sort technique.

a[0] a[1] a[2] a[3] a[4]

16 15 2 13 6

a[0] a[1] a[2] a[3] a[4]

Pass 1 16 15 2 13 6 Loc = 2
 
min loc

Therefore, interchange a[0] & a[4] i.e., 11 & 2 to obtain following array

a[0] a[1] a[2] a[3] a[4]

Pass 2 Loc = 4

Khurasan University, Jalalabad Page 36

 2 15 16 13 6
 
min loc
Therefore, interchange a[1] & a[4] i.e., 15 & 6 to obtain following array

a[0] a[1] a[2] a[3] a[4]

Pass 3 2 6 16 13 15 Loc = 3
 
min loc
Therefore, interchange a[2] & a[3] i.e., 16 & 13 to obtain following array

a[0] a[1] a[2] a[3] a[4]

Pass 4 2 6 13 16 15 Loc = 4
 
min loc

Therefore, interchange a[0] & a[2] i.e., 11 & 2 to obtain following array

a[0] a[1] a[2] a[3] a[4]

Pass 5 2 6 13 15 16

min

Algorithm
Procedure min (a, k, n, loc)
An array a is in memory. This procedure finds the location loc of the smallest element among
a[k], a[k + 1], . . , a[n] during k pass. min (a, k, n, loc)

1. Set min : = a[ k] and loc : = k. [Initializes pointers.]

2. Repeat for j = k + 1, k + 2 , . . , n :
If min > a[ j ], then : Set min : = a[ j ] and loc : = j.
[End of loop.]
3. Return.

Algorithm
Selection sort A[MAXSIZE], N)
This algorithm can now be easily started
1. Repeat steps 2 and 3 for k = 1, 2, . . , n – 1:
2. Call min(a, k, n, loc).
3. [Interchange a[ k ] and a[loc].]
Set temp : = a[ k ], a[ k ] : = a[loc] and a[loc] : = temp.
[End of step 1 loop.]
4. Exit.

The selection sort makes first pass in n – 1 comparisons, the second pass in n – 2 comparisons and so on.
The total number of comparisons are ((n – 1) + (n + 2)) + . . . . + 1 = n(n – 1) /2 which is O(n2). Selection

Khurasan University, Jalalabad Page 37

sort is faster than bubble sort. There is no improvement if the file is completely sorted or unsorted. The
selection sort takes more time than the bubble sort even in those cases where the objects/records are
already in order. The inner loop will take n*(n – 1)/2 comparisons (number[i]<min) to complete sorting
in all cases. Selection sort will be useful where n is very small. If the list is already sorted, selection sort is
slower than insertion sort.
There is not much difference between the worst time and best time in selection sort.

INSERTION SORT
An insert5ion sort is one that sorts a set of values by inserting values into an existing sorted file.
Suppose an array a with n elements a[1], a[2], . . , a[n] is in memory. The insertion sort algorithm scans a
from a[1] to a[n], inserting each element a[k] into its proper position in the previously sorted subarray
a[1], a[2], . . , a[k – 1]. That is :

Pass 1. a[1] by itself is trivially sorted.

Pass 2. a[2] is inserted either before or after a[1] so that: a[1], a[2] is sorted.
Pass 3. a[3] is inserted into its proper place in a[1], a[2], that is, before a[1], between a[1] and
a[2], or after a[2], so that: a[1], a[2] a[3] is sorted.
Pass 4. a[4] is inserted into its proper place in a[1], a[2], a[3] so that :
a[1], a[2], a[3], a[4] is sorted.
.......... ........... ........... ........... ........... ........... ........... ..........

Pass N. a[n] is inserted into its proper place in a[1], a[3], . . , a[n – 1] so that :
a[1], a[2], . . , a[n] is sorted.
To illustrate the insertion sort method, consider the following array a with 7 elements :
25, 15, 30, 9, 99, 20, 26
Array a of 7 elements

25 15 30 9 99 20 26
0 1 2 3 4 5 6

Pass I : a[1] < a[0], interchanging the position of elements, we get.

15 25 30 9 99 20 26
0 1 2 3 4 5 6
Pass II: a[2] > a[1], position of elements remains same.

15 25 30 9 99 20 26
0 1 2 3 4 5 6
Pass III: a[3] is less than a[0], a[1] and a[2], so insert a[3] before a[0], we get.
a[5] before a[2], we get

9 15 25 30 99 20 26
0 1 2 3 4 5 6
Pass IV: a[4] > a[3], no change is performed.

9 15 25 30 99 20 26

Khurasan University, Jalalabad Page 38

 0 1 2 3 4 5 6

Pass V: a[5] is less than a[2], a[3] and a[4], therefore insert a[5] before a[2], we get

9 15 20 25 30 99 26
0 1 2 3 4 5 6
Pass VI: Now a[6] is less than a[4], a[5] therefore insert a[6] before a[4], giving the following
array :

9 15 20 25 26 30 99
0 1 2 3 4 5 6

After the pass VI, we get array with sorted elements.

Algorithm
Insertion sort (A[MAXSIZE], Item)
Let a be an array of n elements which we want to sort temp be a temporary variable to
interchange the two values. K be the total no. of passes and j be another control variable.
1. Set k = 1.
2. For k = 1 to (n – 1)
Set temp = a[ k ]
Set j = k – 1
While temp < a[ j ] and (j > = 0) perform the following steps.
Set a[j+1] = a[ j ]
[End of loop structure]
Assign the value of temp to a[j+ 2].
[End of for loop structure]
3. Exit.

Khurasan University, Jalalabad Page 39

 Algorithm
Quick_ sort t (a, l, h)
Where
a  Represents the list of elements.
l  Represents the position of the first element in the list (only at the starting point, it’s
value change during the execution of the function).
h  Represents the position of the last element in the list (only at starting point the value of
its changes during the execution of the function).

Step 1 : [Initially]
low = l
high = h
key = a [(l + h)/2] [Middle element of the element of the list]
Step 2 : Repeat through step 7 while (low <= high)
Step 3 : Repeat step 4 while (a([low] < key))
Step 4 : low = low + 1
Step 5 : Repeat step 6 while (a([high] < key))
Step 6 : high = high – 1
Step 7 : if(low <= high)
(a) temp = a[low]
(b) a[low] = a[high]
(c) a[high] = temp
(d) low = low + 1
(e) high = high – 1
Step 8 : if(l<high)) Quick_sort (a, l, high)
Step 9 : if (low<h) Quick_sort (a, low, h)
Step 10 : Exit

Khurasan University, Jalalabad Page 40