ICT

Read the following scenario and after answer questions:

In a bank, a Teller has the role of serving the clients. He/she has to organize the
banknotes of same values together and coins of same values together that he/she has
to serve to clients. When a client arrives in the bank, he/she chooses a line to join in the
front of a Teller and the line is formed according to the arrival of clients.

Mr. KARENZI wants to pay 78450 Rwf as his school fees to the bank and he must
organize banknotes and coins before deposit money to facilitate the teller to not mix
the banknotes and coins

1. Observe the above figure and describe what you see;

2. Where a new arrived client will line up?

3. Using the above figure who is going to be served first by the teller 1 or 2;

4. Discuss how KARENZI is going to organize bank notes and coins before
     depositing;

5. Discuss how the teller is going to keep money deposited by Karenzi

Data Structure is a way of collecting and organizing data in such a way that we
can perform operations on these data in an effective way. Data Structures is about
rendering data elements in terms of some relationship, for better organization and
storage.

Example: Library is composed of elements (books) to access a particular book
requires knowledge of the arrangement of the books.

Anything that can store data can be called as a data structure, hence Integer,
Float, Boolean, Char etc., all are data structures. They are known as Primitive Data
Structures. And we also have some complex Data Structures, which are used to store
large and connected data and are called non primitive data structure or Abstract
Data Structure.

Example: Array, Linked List, Tree, Graph, Stack, Queue etc.
All these data structures allow us to perform different operations on data. We select
these data structures based on which type of operation is required.

The data structures have the following importance for programming:

• Data structures study how data are stored in a computer so that operations
   can be implemented efficiently

• Data structures are especially important when there is a large amount of
   information to deal with.

• Data structures are conceptual and concrete ways to organize data for efficient
   storage and manipulation

Beside the simple operations performed on data (unary operators, binary operators and
precedence operators) seen in Senior Four, the data appearing in our data structures are
processed by means of other operations. The following are some of the most frequently
used operations.

Traversing: Accessing each record exactly once so that certain items in the record may be
                     processed.

• Searching: Finding the location of the record with a given key value or finding
    the locations of all records which satisfy one or more conditions

• Inserting: Adding a new record to the structure.

• Deleting: Removing a record from the structure.

• Sorting: Arranging the records in some logical order (e.g., in numerical order
   according to some NUMBER key, such as social security number or account number).

• Merging: Combining the records of two different sorted lists into a single sorted list.

It is important for every Computer Science student to understand the concept of
Information and how it is organized or how it can be utilized.

If we arrange some data in appropriate sequence, then it forms a Structure and gives us
a meaning. This meaning is called information. The basic unit of information in computer
Science is a bit, binary digit. So we found two things in information: One is Data and the
other is Structure

Study the following table

1. Suggest a name for the above table?

2. How many rows and columns in the above table?

3. Identify the location of the value 95 in the above table?

Arrays hold a series of data elements, usually of the same size and data type.
Individual elements are accessed by their position in the array. The position is given
by an index, which is also called a subscript. The index usually uses a consecutive
range of integers, (as opposed to an associative array) but the index can have any
ordinal set of values

Some arrays are multi-dimensional, meaning they are indexed by a fixed number of
integers, for example by a tuple of four integers. Generally, one- and two-dimensional
arrays are the most common. Most programming languages have a built-in array
data type.

In computer programming, a group of homogeneous elements of a specific data
type is known as an array, one of the simplest data structures.

A dimension of array is a direction in which you can vary the specification of an
array›s elements. An array can be of one or many dimensions.

Example: a [3]

It is an array called a with 3 elements. The elements of the array are logically
represented by the name of the array with in brackets its index or positions. For the
one dimensional array a with 3 elements, elements are written like a[0], a[1] and
a[2]. The indexes start always by 0. Graphically, it is

b. Multi-dimensional arrays
    Example:

         Two dimensional array ex: a[2][7]as Integer
        Three dimensional array ex: a[3][2][5]as Integer

A Two dimensional Array is a collection of a fixed number of elements (components)
of the same type arranged in two dimensions.

The two dimensional array is also called a matrix or a table. The intersection of a
column and a row is called a cell. The numbering of rows and columns starts by 0

Example:
The array a[3][4] is an array of 3 rows and 4 columns. In matrix representation, it
looks like the following:

a[i][j] means that it is an element located at the intersection of row i and column j.
Each element is identified by its row and column

The syntax for declaring a two-dimensional array is:
SET Array name=Array of Data type

Where row size and column size are expressions yielding positive integer values,
the two expressions row size and column size specify the number of rows and the
number of columns, respectively, in the array.

1. SET a=Array[2][7] of Integer

2. SET b=Array[4][3] of Integer

Notice that the number of elements =row size*column size

The examples above defines respectively arrays named a and b with 14 (2*7) elements
and 12 (4*3) elements. The expression marks [0] [0] will access the first element of
the matrix marks and marks [1] [6] will access the last row and last column of array a.

If the array marks if filled with the elements 80, 75, 76, 75, 55, 70, 55, 70, 65, 85, 35
and 59, we get the following table.

When a two-dimension array has been declared, it needs to be assigned values for
its elements. This action of assigning values to array elements is called initialization.
Two-Dimensional array is initialized by specifying bracketed values for each row. For
the case of array of integers, the default values of each element is 0 while for others
the default values for other types is not known.

For the case of an array of 3 rows and 4 columns, if the name is A and the type of
elements is integer, the initialization is:

int A[3][4]={{A[0][0], A[0][1], A[0][2], A[0][3]}, /* initializers for row indexed by 0 */
{A[1][0], A[1][1], A[1][2], A[1][3]}, /* initializers for row indexed by 1*/
{A[2][0], A[2][1], A[2][2], A[2][3]} /* initializers for row indexed by 2 */
};

The nested braces, which indicate the intended row, are optional. The following
initialization is equivalent to the previous initialization.

Int A[3][4]={A[0][0], A[0][1], A[0][2], A[0][3], A[1][0], A[1][1], A[1][2], A[1][3], A[2][0],
A[2][1], A[2][2], A[2][3]};

An example of marks for 3 students in 4 courses. The array will look like this:

If the table is called marks, marks [1][3]=15; where the row position is 1 and the
column position is 3.

The expression marks [0] [0] will access the first element of the matrix marks and
marks [2] [3] will access the last row and last column.

The two dimensional array marks which will hold 12 elements can be initialized like:

BEGIN
SET marks=Array[3] [4] of Integer
marks[0][0]=18

1. Four secondary schools in RUHANGO District are displaying the number
   of students per year that they registered in 2015, 2016, 2017 and 2018.

a. How many rows and columns will be in the table that contains the
    displayed data?

b. Declare an array called population to contain the needed data.

c. Initialize the array population with numbers of your choice.

2. Given below the case of array a:

a[0][0]     1      a[1][0] 54

a[0][1]     2       a[1][1] 23

a[0][2]      3       a[1][2] 11

a[0][3]     13          a[1][3] 45

a[0][4]     17          a[1][4] 31

a[0][5 ]    34          a[1][5] 65

a[0][6]     19              a[1][6] 26

a. Give the size of the above array;

b. Declare array a;

c. Initialize the above array.

WRITE marks[1][2] ;
What are the meanings of the above statements

There exist two ways of accessing the elements of an array. The elements’
values of the array can come from the input devices or from a given file so that
these elements are written into the array. The function used is READ or other
versions of it, depending on the programming languages used for programs
writing.

For example READ marks[1][2] stores a value in second row, third column
location of the array marks.

To store multiple values into array you must use a FOR loop.

Syntax:
FOR i=initial value TO upperlimit DO
FOR j=initial value TO upperlimit DO
READ array name[i][j]i=i+1
j=j+1
END FOR
END FOR
Where i refers to the row position and j refers to the column position.

Initial value=lower limit

Example: Write an algorithm of a program that allows the user to enter (store) two
dimensional array elements
BEGIN
SET marks=Array [3] [8] of Integer
Use variable i as integer
Use variable j as integer
FOR i=0 TO 2 DO
FOR j=0 TO 7 DO
READ marks[i] [j]i=i+1
j=j+1

To access two dimensional array elements’ values, we can also take the elements’
values of an array residing in the memory of the computer and write them in any
output device or a given file.

To write (display) elements from an array in an output device or other file, use a
WRITE function or other versions of it depending on the programming languages
used for programs writing together with the array name and location (index) of the
element. In that case the elements of a two dimensional array can be displayed by
the following syntax:

         WRITE Array name [i][j]

Where i refers to the row position and j refers to the column position.

To display a single value of an array you must provide the array name and index to
write operation example:

Example for writing on screen a two dimensional array element
WRITE a[1][2], i=1 and j=2).

Example: Write an algorithm of a program that displays stored two dimensional
array marks’ elements

Example: Write an algorithm that allows the user to enter(store) two dimensional
               array elements and displays those stored elements.

1. Write an algorithm to do the following operations on a two dimensional
     array A of size m x n.

• Declare the array A;

• Read the element ‘values into matrix of size m x n

• Output the elements’ values of matrix of size m x n on the screen;

• Calculate the sum of all elements’ values of matrix of size m x n;

• Write a programme in C++ Language where you apply the above questions

2. Write an algorithm that allows a user to input data through input device
    and display the smallest element’ s value on the screen.

3. Write a programme in C++ language that implements the above
    algorithm.

4. Consider a 2 by 3 array T

a. Write a declaration of T

b. How many rows does T have?

c. How many columns does T have?

d. How many elements does T have?

e. Write name of elements in second row

f. Write the name of element in third column

g. Write a single statement that sets the elements of T in row 1and column 2
    to zero

h. Write a statement that inputs the values of T from keyboard

i. Write a statement that displays the elements of first row of T

1. Observe and analyze the above figure

2. Explain different procedures that you can use to arrange the above books.

Abstract Data structure is a mathematical model of a data structure that specifies the
type of data stored, the operations supported on them and the types of parameters
of the operations with no implementation. Each program language has its own way
to implement abstract data type.

• Data structures study how data are stored in a computer so that operations
can be implemented efficiently;

• Abstract Data structures are especially important when you have a large
   amount of information;

• Conceptual and concrete ways to organize data for efficient storage and
   manipulation

The data appearing in our data structures are processed by means of certain
 operations. Following are some of the most frequently used operations.

• Searching: Finding the location of the record with a given key value or finding
  the locations of all records which satisfy one or more conditions;

• Sorting: Arranging the records in some logical order .

A list is a collection of data in which each element of the list contains the location of
the next element.

In a list, each element contains two parts: data and link to the next element. The data
parts of the list hold the value information and data to be processed. The link part
of the list is used to chain the data together and contains a pointer (an address) that
identifies the next element in the list.
In the list you can do the following operations:

• LIST: Creates an empty list;

• INSERT: inserts an element in the list;

• DELETE: deletes an element from the list;

• RETRIEVE: retrieves an element from the list;

• TRAVERSE: traverses the list sequentially;

• EMPTY: checks the status of the list.

A bank has 10 branches created one after another at different dates. The Bank
Inspector who wants to visit all of them can follow the order of their creation. He/
she will be informed only about the name and location of the first branch. When he
reaches that branch, the Branch Manager will tell him/her the address of the next
branch, and so one.

After visiting all branches, the Bank Inspector will realize that he/she has a list of the
bank branches.

Graphically, it will be represented like a list where each branch is considered as a
node containing the names of the branch and the address of the next branch.

A list is an ordered set of data. It is often used to store objects that are to be processed
sequentially.

An array is an indexed set of variables, such as dancer [1], dancer [2], dancer [3] It is
like a set of boxes that hold things. A list is a set of items. An array is a set of variables
that each store an item.

In a list, the missing spot is filled in when something is deleted. While in an array, an
empty variable is left behind when something is deleted.Simply a list is a sequence
of data, and linked list is a sequence of data linked with each other.

  2.4.2 Linked list

This is a dynamic table/ data structure used to hold a sequence. Its characteristics
 are the following:

• Items forming a sequence are not necessarily held in contiguous data location
   or in the order in which they occur in the sequence.

• Each item in the list is called a node and contains an information field and a
   new address field called a link or pointer field.

• Information field holds actual data for list item; link field contains the address
  of the next item.

• The link field in the last item indicates that there are not further items. E.g. has
   a value of 0.

• Associated with the list is a pointer variable which points to the first node in
   the list.

• We use linked list in linking files, for example, in a hard disk.

• It can grow or shrink in size during execution of a program.

• It can be made just as long as required

• It does not waste memory space.

Linked list is classified into three types as shown below:

 

   • Single linked lists

  • Double linked lists
 

  • Circular linked list

Single linked list is a sequence of elements in which every element has link to its
next element in the sequence. In any single linked list, the individual element is
called as “Node”. Every “Node” contains two fields, data and next. The data field is
used to store actual value of that node and next field is used to store the address of
the next node in the sequence

In a single linked list, the address of the first node is always stored in a reference node
known as “front” (Sometimes it is also known as “head”).Always next part (reference part) of the last node  must be NULL

Creating and read an element in a NODE
BEGIN
struct node{
int info
struct node next
} head, current, temp
head=null
temp=null
current=null
Begin sub
Step 1 Read the element into x
Step 2 Create a temp node in the memory
temp =(struct node )sizeof (node)
Step 3 Assign the values in temp node as follows
temp -> info =x
temp ->next=null
End sub
END

Inserting at Specific location in the list (After a Node)
We can use the following steps to insert a new node after a node in the single linked list

• Step 1: Create a newNode with given value.

• Step 2: Check whether list is Empty (head == NULL)

• Step 3: If it is Empty then, set newNode => next = NULL and head = newNode.

• Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.

• Step 5: Keep moving the temp to its next node until it reaches to the node

after which we want to insert the newNode (until temp1 => data is equal to
location, here location is the node value after which we want to insert the
newNode).

• Step 6: Every time check whether temp is reached to last node or not. If it
   is reached to last node then display ‘Given node is not found in the list!!!
   Insertion not possible!!!’ and termin ate the function. Otherwise move the
  temp to next node.

• Step 7: Finally, Set ‘newNode => next = temp => next’ and ‘temp => next = newNode’

   Deleting a Specific Node from the list

We can use the following steps to delete a specific node from a single linked list

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty then, display ‘List is Empty!!! Deletion is not possible’ and
     terminate the function.

• Step 3: If it is Not Empty then, define two Node pointers ‘temp1’ and ‘temp2’
    and initialize ‘temp1’ with head.

• Step 4: Keep moving the temp1 until it reaches to the exact node to be deleted
  or to the last node. And every time set ‘temp2 = temp1’ before moving the
 ‘temp1’ to its next node.

• Step 5: If it is reached to the last node then display ‘Given node not found in
   the list! Deletion not possible!!!’ And terminate the function.

• Step 6: If it is reached to the exact node which we want to delete, then check
   whether list is having only one node or not

• Step 7: If list has only one node and that is the node to be deleted, then set
   head = NULL and delete temp1 (free (temp1)).

• Step 8: If list contains multiple nodes, then check whether temp1 is the first
   node in the list (temp1 == head).

• Step 9: If temp1 is the first node then move the head to the next node (head =
   head => next) and delete temp1.

• Step 10: If temp1 is not first node then check whether it is last node in the list
   (temp1=> next == NULL).

• Step 11: If temp1 is last node then set temp2 => next = NULL and delete
  temp1 (free (temp1)).

• Step 12: If temp1 is not first node and not last node then set temp2 => next =
   temp1=> next and delete temp1 (free (temp1)).

We can use the following steps to display the elements of a single linked list

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty then, display ‘List is Empty!!!’ and terminate the function.

• Step 3: If it is Not Empty then, define a Node pointer ‘temp’ and initialize with
   head.

• Step 4: Keep displaying temp=> data with an arrow (->) until temp reaches to
   the last node

• Step 5: Finally display temp => data with arrow pointing to NULL (temp =>
   data -> NULL).

 

Double linked list is a sequence of elements in which every element has links to its
previous element and next element in the sequence. So, we can traverse forward by
using next field and can traverse backward by using previous field. Every node in a
double linked list contains three fields and they are shown in the following figure

We can use the following steps to insert a new node after a node in the double
linked list

• Step 1: Create a newNode with given value.

• Step 2: Check whether list is Empty (head == NULL)

• Step 3: If it is Empty then, assign NULL to newNode => previous&newNode =>
            next and newNode to head.

• Step 4: If it is not Empty then, define two node pointers temp1&temp2 and initialize temp1 with head.

• Step 5: Keep moving the temp1 to its next node until it reaches to the node
  after which we want to insert the newNode (until temp1 => data is equal to
  location, here location is the node value after which we want to insert the newNode).

• Step 6: Every time check whether temp1 is reached to the last node. If it is
   reached to the last node then display ‘Given node is not found in the list!!!
   Insertion not possible!!!’ and terminate the function. Otherwise move the
    temp1 to next node.

• Step 7: Assign temp1 => next to temp2, newNode to temp1=> next, temp1
   to newNode => previous, temp2 to newNode => next and newNode to temp2
    => previous.

We can use the following steps to delete a specific node from the double linked list

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty then, display ‘List is Empty!!! Deletion is not possible’ and
             terminate the function.

• Step 3: If it is not Empty, then define a Node pointer ‘temp’ and initialize with head.

• Step 4: Keep moving the temp until it reaches to the exact node to be deleted
    or to the last node.

• Step 5: If it is reached to the last node, then display ‘Given node not found in
  the list! Deletion not possible!!!’ and terminate the fuction.

• Step 6: If it is reached to the exact node which we want to delete, then check
   whether list is having only one node or not

• Step 7: If list has only one node and that is the node which is to be deleted
   then set head to NULL and delete temp (free(temp)).

• Step 8: If list contains multiple nodes, then check whether temp is the first
   node in the list (temp == head).

• Step 9: If temp is the first node, then move the head to the next node (head =
   head => next), set head of previous to NULL (head => previous = NULL) and
    delete temp.

• Step 10: If temp is not the first node, then check whether it is the last node in
   the list (temp => next == NULL).

• Step 11: If temp is the last node then set temp of previous of next to NULL
(temp => previous => next = NULL) and delete temp (free(temp)).

• Step 12: If temp is not the first node and not the last node, then set temp of
   previous of next to temp of next (temp => previous => next = temp => next),
   temp of next of previous to temp of previous (temp => next => previous =
   temp => previous) and delete temp (free(temp)).

We can use the following steps to display the elements of a double linked list

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty, then display ‘List is Empty!!!’ and terminate the function.

• Step 3: If it is not Empty, then define a Node pointer ‘temp’ and initialize with
   head.

• Step 4: Display ‘NULL <= ‘.

• Step 5: Keep displaying temp → data with an arrow (↔) until temp reaches to
   the last node

• Step 6: Finally, display temp → data with arrow pointing to NULL (temp → data ---> NULL).

In circular linked list, every node points to its next node in the sequence but the last
node points to the first node in the list

Inserting at Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the circular
linked list...

• Step 1: Create a newNode with given value.

• Step 2: Check whether list is Empty (head == NULL)

• Step 3: If it is Empty then, set head = newNode and newNode → next = head.

• Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.

• Step 5: Keep moving the temp to its next node until it reaches to the node
  after which we want to insert the newNode (until temp1 → data is equal to
 location, here location is the node value after which we want to insert the newNode).

• Step 6: Every time check whether temp is reached to the last node or not. If
   it is reached to last node then display ‘Given node is not found in the list!!!
  Insertion not possible!!!’ and terminate the function. Otherwise move the
  temp to next node.

• Step 7: If temp is reached to the exact node after which we want to insert the
   newNode then check whether it is last node (temp → next == head).

• Step 8: If temp is last node then set temp → next = newNode and newNode
→ next = head.

• Step 8: If temp is not last node then set newNode → next = temp → next
  and temp → next = newNode.

We can use the following steps to delete a specific node from the circular linked list...

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty then, display ‘List is Empty!!! Deletion is not possible’
  and terminate the function.

• Step 3: If it is Not Empty then, define two Node pointers ‘temp1’ and ‘temp2’
  and initialize ‘temp1’ with head.

• Step 4: Keep moving the temp1 until it reaches to the exact node to be deleted
  or to the last node. And every time set ‘temp2 = temp1’ before moving the
  ‘temp1’ to its next node.

• Step 5: If it is reached to the last node then display ‘Given node not found in
  the list! Deletion not possible!!!’. And terminate the function.

• Step 6: If it is reached to the exact node which we want to delete, then check
   whether list is having only one node (temp1 → next == head)

• Step 7: If list has only one node and that is the node to be deleted then set
   head = NULL and delete temp1 (free(temp1)).

• Step 8: If list contains multiple nodes then check whether temp1 is the first
  node in the list (temp1 == head).

• Step 9: If temp1 is the first node then set temp2 = head and keep moving
   temp2 to its next node until temp2 reaches to the last node. Then set head =
   head → next, temp2 → next = head and delete temp1.

• Step 10: If temp1 is not first node then check whether it is last node in the list

(temp1 → next == head).

• Step 11: If temp1 is last node then set temp2 → next = head and delete
temp1 (free (temp1)).

• Step 12: If temp1 is not first node and not last node then set temp2 → next
= temp1 → next and delete temp1 (free (temp1)).

We can use the following steps to display the elements of a circular linked list

• Step 1: Check whether list is Empty (head == NULL)

• Step 2: If it is Empty, then display ‘List is Empty!!!’ and terminate the function.

• Step 3: If it is Not Empty then, define a Node pointer ‘temp’ and initialize with
             head.

• Step 4: Keep displaying temp → data with an arrow (--->) until temp reaches
   to the last node

• Step 5: Finally display temp → data with arrow pointing to head → data.

A queue is a linear list in which data can only be inserted at one end, called the REAR,
and deleted from the other end, called the FRONT. These restrictions ensure that the
data is processed through the queue in the order in which it is received. In an other
words, a queue is a structure in which whatever goes fist comes out first (first in,
first out(FIFO) structure).

There exist two types of queues:

• Linear queue

• Circular queue

Queue data structure is a linear data structure in which the operations

are performed based on FIFO principle. Queue Operations using Array
before we implement actual operations, first follow the below steps to create an
empty queue.

• Step 1: Include all the header files which are used in the program and define
  a constant ‘SIZE’ with specific value.

• Step 2: Declare all the user defined functions which are used in queue
    implementation.

• Step 3: Create a one dimensional array with above defined SIZE (int queue[SIZE])

• Step 4: Define two integer variables ‘front’ and ‘rear’ and initialize both with
    ‘-1’. (int front = -1, rear = -1)

• Step 5: Then implement main method by displaying menu of operations list
 and make suitable function calls to perform operation selected by the user on
  queue.

• Step 1: Check whether queue is FULL. (rear == SIZE-1)

• Step 2: If it is FULL, then display “Queue is FULL!!! Insertion is not possible!!!””
   and terminate the function.

• Step 3: If it is NOT FULL, then increment rear value by one (rear++) and set
  queue [rear] = value.

• Step 1: Check whether queue is EMPTY. (front == rear)

• Step 2: If it is EMPTY, then display “Queue is EMPTY!!! Deletion is not possible!!!”
   and terminate the function.

• Step 3: If it is NOT EMPTY, then increment the front value by one (front ++).
  Then display queue[front] as deleted element. Then check whether both front
   and rear are equal (front == rear), if it TRUE, then set both front and rear to ‘-1’
   (front = rear = -1).

We can use the following steps to display the elements of a queue

• Step 1: Check whether queue is EMPTY. (front == rear)

• Step 2: If it is EMPTY, then display “Queue is EMPTY!!!” and terminate the
  function.

• Step 3: If it is NOT EMPTY, then define an integer variable ‘I’ and set ‘i = front+1’.

• Step 3: Display ‘queue[i]’ value and increment ‘I’ value by one (i++). Repeat
   the same until ‘I’ value is equal to rear (i<= rear)

Circular Queue is a linear data structure in which the operations are performed
based on FIFO (First In First Out) principle and the last position is connected back to
the first position to make a circle.

To implement a circular queue data structure using array, we first create it.

• Step 1: Include all the header files which are used in the program and define a
   constant ‘SIZE’ with specific value.

• Step 2: Declare all user defined functions used in circular queue implementation.

• Step 3: Create a one dimensional array with above defined SIZE (int cQueue[SIZE])

• Step 4: Define two integer variables ‘front’ and ‘rear’ and initialize both with ‘-1’. (int
   front = -1, rear = -1)

• Step 5: Implement main method by displaying menu of operations list and make
  suitable function calls to perform operation selected by the user on circular queue.

• Step 1: Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front ==
   rear+1))

• Step 2: If it is FULL, then display “Queue is FULL!!! Insertion is not possible!!!” and
   terminate the function.

• Step 3: If it is NOT FULL, then check rear == SIZE - 1 && front != 0 if it is TRUE, then
   set rear = -1.

• Step 4: Increment rear value by one (rear++), set queue[rear] = value and check
‹front == -1’ if it is TRUE, then set front = 0.

• Step 1: Check whether queue is EMPTY. (front == -1 && rear == -1)

• Step 2: If it is EMPTY, then display “Queue is EMPTY!!! Deletion is not possible!!!” and
   terminate the function.

• Step 3: If it is NOT EMPTY, then display queue[front] as deleted element and
   increment the front value by one (front ++). Then check whether front == SIZE, if it
   is TRUE, then set ‘front = 0’. Then check whether both ‘front – 1’ and rear are equal
   (front -1 == rear), if it TRUE, then set both front and rear to ‘-1’ (front = rear = -1).

• Step 1: Check whether queue is EMPTY. (front == -1)

• Step 2: If it is EMPTY, then display “Queue is EMPTY!!!” and terminate the function.

• Step 3: If it is NOT EMPTY, then define an integer variable ‘i’ and set ‘i = front’.

• Step 4: Check whether ‘front <= rear’, if it is TRUE, then display ‘queue[i]’ value and
   increment ‘I’ value by one (i++). Repeat the same until ‘i <= rear’ becomes FALSE.

• Step 5: If ‘front <= rear’ is FALSE, then display ‘queue[i]’ value and increment ‘I’ value
   by one (i++). Repeat the same until ‘i <= SIZE – 1’ becomes FALSE.

• Step 6: Set i to 0.

• Step 7: Again display ‘cQueue[i]’ value and increment i value by one (i++). Repeat
   the same until ‘i <= rear’ becomes FALSE.

There are three main operations related to queues.

• Enqueue: the enqueue operation inserts an items at the rear of the queue

• Dequeue: the dequeue operation deletes the item at the front of the queue

• Display: show elements in the array

   2.6 Stack

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. Data input as 5, 10, 15, 20, for example would be
removed as 20, 15, 10, and 5. This reversing attribute is why stacks are known as Last
in, First out (LIFO) data structures.

We use many different types of stacks in our daily lives. We often talk of a stack of
coins, stack of books on a table and stack of plates in a kitchen. Any situation in which

we can only add or remove an object at the top is a stack. If we want to remove an
object other than the one at the top, we must first remove all objects above it. The
following charts illustrates cases of stack

A Stack is a Last in First out (LIFO) dynamic table or data structure. It has the following
characteristics:

• List of the same kind of elements;

• Addition and deletion of elements occur only at one end, called the top of the
  stack;

• Computers use stacks to implement method calls;

• Stacks are also used to convert recursive algorithms into non recursive
  algorithm.

The different operations performed on stacks are as follows:

• Push: adds an element to the stack

• Pop: removes an element from the stack

• Peek: display at top element of the stack

Before implementing actual operations, first follow the below steps to create an
empty stack.

Step 1: Include all the header files which are used in the program and define a
constant ‘SIZE’ with specific value.

• Step 2: Declare all the functions used in stack implementation.

• Step 3: Create a one dimensional array with fixed size (int stack[SIZE])

• Step 4: Define a integer variable ‘top’ and initialize with ‘-1’. (int top = -1)

• Step 5: In main method display menu with list of operations and make suitable
  function calls to perform operation selected by the user on the stack.

• Step 1: Check whether stack is FULL. (top == SIZE-1)

• Step 2: If it is FULL, then display “Stack is FULL!!! Insertion is not possible!!!” and
  terminate the function.

• Step 3: If it is NOT FULL, then increment top value by one (top++) and set stack [top]  to value (stack[top] = value).

• Step 1: Check whether stack is EMPTY. (top == -1)

• Step 2: If it is EMPTY, then display “Stack is EMPTY!!! Deletion is not possible!!!’” and
  terminate the function.

• Step 3: If it is NOT EMPTY, then delete stack [top] and decrement top value by
   one(top-).

• Step 1: Check whether stack is EMPTY. (top == -1)

• Step 2: If it is EMPTY, then display “Stack is EMPTY!!!” and terminate the function.

• Step 3: If it is NOT EMPTY, then define a variable ‘I’ and initialize with top.
  Display stack[i] value and decrement i value by one (i--).

• Step 3: Repeat above step until i value becomes ‘0’.

  2.6.2 Stack exceptions

Adding an element to a full stack and removing an element from an empty stack
would generate errors or exceptions:

• Stack overflow exception: it occurs if you try to add an item to stack or queue
  which is already full.

• Stack underflow exception: it occurs if you try to remove an item from an
empty queue or stack.

Notec 1: Stack and Queue data structures can be implement in two ways: By using
array or by using linked list.

Notice 2: When stack or Queue is implemented using array, that stack or Queue can
organize only a limited number of elements. When stack or Queue is implemented
using linked list, that stack or Queue can organize an unlimited number of elements.

   2.7 Tree

In linear data structure, data is organized in sequential order and in non-linear data
structure; data is organized in random order. Tree is a very popular data structure
used in wide range of applications. A tree data structure can be defined as follows.

In a tree data structure, if we have N number of nodes then we can have a maximum
of N-1 number of links.

Tree data structure is a collection of data (Node) which is organized in hierarchical
structure and this is a recursive definition.

Example

In a tree data structure, we use the following terminology:

In a tree data structure, the first node is called as Root Node. Every tree must have
root node..

In a tree data structure, the connecting link between any two nodes is called an Edge.
In a tree with ‘N’ number of nodes there will be a maximum of ‘N-1’ number of edges.

In a tree data structure, the node which is predecessor of any node is called a
PARENT NODE. In simple words, the node which has branch from it to any other
node is called as parent node.

      d. Child

In a tree data structure, the node which is descendant of any node is called a CHILD
Node. In a tree, any parent node can have any number of child nodes. In a tree, all
the nodes except root are child nodes.

     e. Siblings
In a tree data structure, nodes which belong to same Parent are called SIBLINGS.

In a tree data structure, the node which does not have a child is called a LEAF Node.
In a tree data structure, the leaf nodes are also called a External Nodes or Terminal
node.

           g. Internal Nods

In a tree data structure, the node which has at least one child is called INTERNAL Node.
In a tree data structure, nodes other than leaf nodes are called Internal Nodes. The
root node is also said to be Internal Node if the tree has more than one node. Internal
nodes are also called as ‹Non-Terminal’ nodes.

In a tree data structure, the total number of children of a node is called as DEGREE of
that Node. In simple words, the Degree of a node is total number of children it has. The
highest degree of a node among all the nodes in a tree is called as ‹Degree of Tree’

In a tree data structure, the root node is said to be at Level 0 and the children of root
node are at Level 1 and the children of the nodes which are at Level 1 will be at Level
2 and so on... In simple words, in a tree each step from top to bottom is called as a
Level and the Level count starts with ‘0’ and incremented by one at each level (Step).

In a tree data structure, the total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that Node. In a tree, height of the root

node is said to be height of the tree. In a tree, height of all leaf nodes is ‘0’.

Figure 2.25.: Height representation
            

           k. Depth
In a tree data structure, the total number of edges from root node to a particular
node is called DEPTH of that Node. In a tree, the total number of edges from root node
to a leaf node in the longest path is said to be Depth of the tree. In a tree, depth of
the root node is ‘0’.

In a tree data structure, the sequence of Nodes and Edges from one node to another
node is called as PATH between those two Nodes. Length of a Path is total number of
nodes in that path. In below example the path A - B - E - J has length 4.

In a tree data structure, each child from a node forms a sub tree recursively. Every
child node will form a sub-tree on its parent node.

   2.7.2 Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are
as follows:

• Linked List of Binary Tree representation

• Array Representation
Let T be a Binary Tree. There are two ways of representing T in the memory as follow
Linked

Consider a Binary Tree T. T will be maintained in memory by means of a linked list
representation, which uses three parallel arrays; INFO, LEFT, and RIGHT pointer
variable ROOT as follows. In Binary Tree, each node N of T will correspond to a
location k such that:

1. LEFT [k] contains the location of the left child of node N.

2. INFO [k] contains the data at the node N.

3. RIGHT [k] contains the location of right child of node N.
    • Representation of a node:

In this representation of binary tree, root will contain the location of the root R of T.
If any one of the sub tree is empty, then the corresponding pointer will contain the
null value if the tree T itself is empty, the ROOT will contain the null value.

Consider the binary tree T in the figure of Binary Tree

b. Array Representation of Binary Tree
Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary
tree. Then there is an efficient way of representing T in the memory called the sequential
representation or array representation of T. This representation uses only a linear array
TREE as follows:

1. The root N of T is stored in TREE [1].

2. If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its
   right child is stored into TREE [2 * k + 1].

For Example:
Consider the following Tree:

When we wanted to display a binary tree, we need to follow some order in which all
the nodes of that binary tree must be displayed. In any binary tree displaying order
of nodes depends on the traversal method.

There are three types of binary tree traversals.

• In - Order Traversal

• Pre - Order Traversal

• Post - Order Traversal

Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root
(head) node. That is, we cannot randomly access a node in a tree.

Generally, we traverse a tree to search or locate a given item or key in the tree or to
print all the values it contains.

In this traversal method, the left sub tree is visited first, then the root and later the
right sub-tree. We should always remember that every node may represent a sub
tree itself.

If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is
also traversed in-order. The process goes on until all the nodes are visited. The output
of inorder traversal of this tree will be −

D → B → E → A → F → C → G

Algorithm:

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.

Step 2 − Visit root node.

Step 3 − Recursively traverse right subtree.

In this traversal method, the root node is visited first, then the left subtree and finally
the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then
move to its left subtree B. B is also traversed pre-order. The process goes on until all the
nodes are visited. The output of pre-order traversal of this tree will be −

A → B → D → E → C → F → G

Algorithm:

Until all nodes are traversed −

Step 1 − Visit root node.

Step 2 − Recursively traverse left subtree.

Step 3 − Recursively traverse right subtree.

In this traversal method, the root node is visited last, hence the name. First we
traverse the left sub tree, then the right sub tree and finally the root node.

We start from A, and following Post-order traversal, we first visit the left sub tree B. B is also
traversed post-order. The process goes on until all the nodes are visited. The output of
post-order traversal of this tree will be −
D → E → B → F → G → C → A

Algorithm:

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.

Step 2 − Recursively traverse right subtree.

Step 3 − Visit root node.

Binary Search tree exhibits a special behavior. A node’s left child must have a value
less than its parent’s value and the node’s right child must have a value greater than
its parent value.

    2.7.4. Basic Operations on binary tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
   properties

• The left sub-tree of a node has a key less than or equal to its parent node’s key.

• The right sub-tree of a node has a key greater than to its parent node’s key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right

sub-tree and can be defined as
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

BST is a collection of nodes arranged in a way where they maintain BST properties.
Each node has a key and an associated value. While searching, the desired key is
compared to the keys in BST and if found, the associated value is retrieved.
Following is a pictorial representation of BST