Unit -1 Syllabus

Introduction to Data Structures:

Introduction to Linear and Non Linear data structures.

Data Structure:
A data structure is a method for organizing and storing data, which would allow efficient data
retrieval and usage.
Linear data structures
Linear data structure is a structure that organizes its data elements in linear fashion i.e. one
after the other.
Ex: stacks, queues, linked lists

Non Linear data structures.

Non linear data structure is a structure that organizes its data elements in hierarchical
fashion. A data item in a nonlinear data structure could be attached to several other data
elements to reflect a special relationship among them

Difference between linear and non linear data structures

Linear data structure Non linear data structure

1) In linear data structures, data elements are 1) In non linear data structures, data elements
organized sequentially are organized hierarchically

2) Data elements are attached one after the 2) A data element can be attached to several
other. other data elements

3) Linear data structures are very easy to 3)Difficult to implement compared to linear data
implement structures

4)Ex: stacks, queues, linked lists 4)Ex: trees, graphs

Abstract Data type (ADT)

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set
of value and a set of operations.

The definition of ADT only mentions what operations are to be performed but not how these
operations will be implemented. It does not specify how data will be organized in memory
and what algorithms will be used for implementing the operations. It is called “abstract”
because it gives an implementation-independent view. The process of providing only the
essentials and hiding the details is known as abstraction.
The user of data type does not need to know how that data type is implemented, for
example, we have been using Primitive values like int, float, char data types only with the
knowledge that these data type can operate and be performed on without any idea of how
they are implemented. So a user only needs to know what a data type can do, but not how it
will be implemented. Think of ADT as a black box which hides the inner structure and design
of the data type

Stack ADT definition, operations

The stack abstract data type is defined by the following structure and operations.

A stack is an ordered collection of items where items are added to and removed from the
end called the “top.” Stacks are ordered LIFO.

The stack operations are given below.

 push(item) adds a new item to the top of the stack.

 pop() removes the top item from the stack.
 isempty() tests to see whether the stack is empty
 isfull( ) tests to see whether the stack is full;.
 display( ) displays all the elements of the stack

Stack ADT

Object:
Ordered finite collection of zero or more elements from basic type. The right most element of
the sequence is the top most element.
Functions:

 push(item) ::= adds a new item to the top of the stack. It needs the item and returns
nothing.
 pop() ::= removes the top item from the stack. It needs no parameters and returns
the item. The stack is modified.
 tos() ::= returns the top item from the stack but does not remove it. It needs no
parameters. The stack is not modified.
 isempty() ::= tests to see whether the stack is empty. It needs no parameters
 isfull( ) ::= tests to see whether the stack is full;. It needs no parameters
 display( ) ::= displays all the elements of the stack

Stack Examples:
  Stack of plates in a cafeteria

 Discard pile in a game of rummy

Stack :

 It is a linear data structure where data is inserted and removed only at one end.

top

Representation:

‘top’ will always point to the top most element in the stack

 Operations
1) push – inserting an element into a stack

2) Pop – Deleting an element from a stack

LIFO – Last In First Out

2 Size = 5

1. Push (10)
4

3 top++

2 a [top] = 10

1
 10

2. Push (20)
4

3 top++

2 a [top] = 20

1 top

0
20

10

3. Push (30)
4

3 top++

2  top a [top] = 30

1
30
0
20

10

4. push (40)

3  top

1
 40

30

20

10

5. push (50)

50 4  top
40 3

30 2

20 1

10 0

6. push (60)

stack over flow

7. pop ( )

50 4
40 Deleted element = 50
3  top

30 2 Item = a [top]

20 1 top --

10 08. pop() ,pop(),pop(), pop()

Deleted element = 40

Deleted element=30

Deleted element=20

Deleted element =10

9. Pop ( )

Stack under flow

Conditions

1. stack over flow

Trying to insert an element into a full stack

2. stack under flow :

Trying to delete an element from an empty stack

Algorithms for Push ( ), Pop ( ) , Display ( )

Algorithm for Push ( )

1. Check for stack overflow

if (top = = n-1)

printf(“stack over flow”);

2. Otherwise, insert an element into the stack.

top ++

a[top] = item

Algorithm for Pop ( )

1. check for stack underflow

if ( top = = -1)

printf( “stack under flow”);

2. Otherwise, delete the element from the stack

 item = a[top]

top --

Algorithm for Display ( )

1. if (top == -1)

printf (“stack is empty”);

2. Otherwise

for (i=0; i<top; i++)

printf (“%d”, a[i]);

Stack ADT definition, operations

The stack abstract data type is defined by the following structure and operations.

A stack is an ordered collection of items where items are added to and removed from the end called
the “top.” Stacks are ordered LIFO.

The stack operations are given below.

 push(item) adds a new item to the top of the stack.

 pop() removes the top item from the stack.
 isempty() tests to see whether the stack is empty
 isfull( ) tests to see whether the stack is full;.
 display( ) displays all the elements of the stack

Stack ADT

Object:
Ordered finite collection of zero or more elements from basic type. The right most element
of the sequence is the top most element.
Functions:

 push(item) ::= adds a new item to the top of the stack. It needs the item and returns
nothing.
  pop() ::= removes the top item from the stack. It needs no parameters and returns
the item. The stack is modified.
 tos() ::= returns the top item from the stack but does not remove it. It needs no
parameters. The stack is not modified.
 isempty() ::= tests to see whether the stack is empty. It needs no parameters
 isfull( ) ::= tests to see whether the stack is full;. It needs no parameters
 display( ) ::= displays all the elements of the stack

Stack Examples:

 Stack of plates in a cafeteria

 Discard pile in a game of rummy

Stack applications

 Expression conversions,
 Expression evaluation
 recursion implementation,
 Backtracking (game playing, finding paths, exhaustive searching)
 Memory management, run-time environment for nested language features.

infix to postfix conversion

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

In infix expression operator comes in between two operands.

Postfix Expression :

In infix expression operator comes after two operands.

The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+.

The algorithm for the conversion is as follows :

 Scan the Infix string from left to right.

 Initialize an empty stack.
 If the scanned character is an operand, add it to the Postfix string.
 If the scanned character is an operator and if the stack is empty Push the character to stack.

 If the scanned character is an operator and the stack is not empty, compare the
precedence of the character with the element on top of the stack (topStack). If
topStack has higher precedence over the scanned character Pop the stack else Push the
scanned character to stack. Repeat this step as long as stack is not empty and topStack
has precedence over the character.

Repeat this step till all the characters are scanned.

 (After all characters are scanned, we have to add any character that the stack may have to
the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack.
Repeat this step as long as stack is not empty.
 Return the Postfix string.

Example :

Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned
is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is
pushed to the stack.

Postfix String

Stack

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is
an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will
be pushed to the stack.

Postfix String

Stack

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The
topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped
out from the stack and added to the Postfix string. Even now the stack is not empty. Now the
topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and
add it to the Postfix string. The '-' will be pushed to the stack.

Postfix String

Stack
Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we
must pop the remaining elements from the stack and add it to the Postfix string. At this stage we
have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters
are scanned, this is how the stack and Postfix string will be :

Postfix String

Stack

End result :

 Infix String : a+b*c-d

 Postfix String : abc*+d-

1. A * B + C becomes A B * C +

current symbol operator stack postfix string

A A

2 * * A

3 B * AB

4 + + AB*
{pop
and
print
the '*'
before
pushing
the '+'}

5 C + AB*C

6 AB*C
+
 2. A + B * C becomes A B C * +

current symbol operator stack postfix string

1 A A

2 + + A

3 B + AB

4 * +* AB

5 C +* ABC

6 ABC*
+
3. A * (B + C) becomes A B C + *

current symbol operator stack postfix string

1 A A

2 * * A

3 ( *( AB

4 B *( AB

5 + *(+ AB

6 C *(+ ABC

7 ) * ABC+

8 ABC+
*
4. A - B + C becomes A B - C +

current symbol operator stack postfix string

1 A A

2 - - A

3 B - AB
 4 + + AB-

5 C + AB-C

6 AB-C
+

5. A * B ^ C + D becomes A B C ^ * D +

current symbol operator stack postfix string

1 A A

2 * * A

3 B * AB

4 ^ *^ AB

5 C *^ ABC

6 + + ABC^
*

7 D + ABC^
*D

8 ABC^
*D+
6. A * (B + C * D) + E becomes A B C D * + * E +

current symbol operator stack postfix string

1 A A

2 * * A

3 ( *( A

4 B *( AB

5 + *(+ AB
 6 C *(+ ABC

7 * *(+* ABC

8 D *(+* ABCD

9 ) * ABCD*
+

10 + + ABCD*
+*

11 E + ABCD*
+*E

12 ABCD*
+*E+

7. A+ (B*C)

i/p symbol Contents of the stack Output

A A

+ A

+
( A

(
+
B AB

(
+
* AB
*
(
+
 C ABC
*
(
+
) ABC*

(
+
\0 ABC*+

8. A * B / (C-D) + E * (F-G)

i/p symbol Contents of the stack Output

A

* A

*
B AB

*
/ AB*

( AB*

C AB*C
 (

_ AB*C

D AB*CD

) AB*CD-

+ AB*CD-/

E AB*CD-/E

* AB*CD-/E

+
( AB*CD-/E

F AB*CD-/EF

_ AB*CD-/EF

G AB*CD-/EFG

) AB*CD-/EFG-

\0 AB*CD-/EFG- * +
A summary of the rules follows:

Print operands as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto
the stack.

3. If the incoming symbol is a left parenthesis, push it on the stack.

4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until
you see a left parenthesis. Discard the pair of parentheses.

5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.

6. If the incoming symbol has equal precedence with the top of the stack, use association. If
the association is left to right, pop and print the top of the stack and then push the incoming
operator. If the association is right to left, push the incoming operator.

7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop
the stack and print the top operator. Then test the incoming operator against the new top of
stack.

8. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)

Stack applications

 Expression conversions,
 Expression evaluation
 recursion implementation,
 Backtracking (game playing, finding paths, exhaustive searching)
 Parenthesis balance Checking
 Memory management, run-time environment for nested language features.

Infix, Prefix and postfix notations

The way to write arithmetic expression is known as a notation. An arithmetic expression can
be written in three different but equivalent notations, i.e., without changing the essence or
output of an expression. These notations are −

 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression. We shall learn the
same here in this chapter.

Infix Notation

We write expression in infix notation, e.g. a - b + c, where operators are used in-between
operands. It is easy for us humans to read, write, and speak in infix notation but the same
does not go well with computing devices. An algorithm to process infix notation could be
difficult and costly in terms of time and space consumption.

Prefix Notation

In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands.
For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known
as Polish Notation.

Postfix Notation

This notation style is known as Reversed Polish Notation. In this notation style, the
operator is postfixed to the operands i.e., the operator is written after the operands. For
example, ab+. This is equivalent to its infix notation a + b.

Infix to postfix conversion

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is
abc*+.
The algorithm for the conversion is as follows :

 Scan the Infix string from left to right.

 Initialize an empty stack.
 If the scanned character is an operand, add it to the Postfix string.
 If the scanned character is an operator and if the stack is empty Push the character
to stack.

 If the scanned character is an operator and the stack is not empty, compare the
precedence of the character with the element on top of the stack (topStack). If
topStack has higher precedence over the scanned character Pop the stack else Push
the scanned character to stack. Repeat this step as long as stack is not empty and
topStack has precedence over the character.

Repeat this step till all the characters are scanned.

 (After all characters are scanned, we have to add any character that the stack may
have to the Postfix string.) If stack is not empty add topStack to Postfix string and
Pop the stack. Repeat this step as long as stack is not empty.
  Return the Postfix string.

Example :

Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character
scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an
operator, it is pushed to the stack.

Postfix String

Stack

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*'
which is an operator. Now, the top element of the stack is '+' which has lower precedence
than '*', so '*' will be pushed to the stack.

Postfix String

Stack

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'.
The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will
be popped out from the stack and added to the Postfix string. Even now the stack is not
empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the
'+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.
 Postfix String

Stack

Next character is 'd' which is added to Postfix string. Now all characters have been scanned
so we must pop the remaining elements from the stack and add it to the Postfix string. At this
stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So,
after all characters are scanned, this is how the stack and Postfix string will be :

Postfix String

Stack

End result :

 Infix String : a+b*c-d

 Postfix String : abc*+d-

A summary of the rules follows:

1. Print operands as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the incoming operator
onto the stack.

3. If the incoming symbol is a left parenthesis, push it on the stack.

4. If the incoming symbol is a right parenthesis, pop the stack and print the operators
until you see a left parenthesis. Discard the pair of parentheses.

5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.

6. If the incoming symbol has equal precedence with the top of the stack, use
association. If the association is left to right, pop and print the top of the stack and then
push the incoming operator. If the association is right to left, push the incoming operator.
 7. If the incoming symbol has lower precedence than the symbol on the top of the stack,
pop the stack and print the top operator. Then test the incoming operator against the
new top of stack.

8. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)

Postfix expression evaluation

The Postfix notation is used to represent algebraic expressions. The expressions written in
postfix form are evaluated faster compared to infix notation as parenthesis are not required
in postfix.
algorithm for evaluation postfix expressions.
1) Create a stack to store operands (or values).
2) Scan the given expression and do following for every scanned element.
…..a) If the element is a number, push it into the stack
…..b) If the element is a operator, pop operands for the operator from stack. Evaluate the
operator and push the result back to the stack
3) When the expression is ended, the number in the stack is the final answer