DATA STRUCTURES
A data structure is a named group of data of different
data types and can be processed as a single unit.
A data structure has well-defined operations, behavior
and properties.
Data Type vs. Data Structure:
A data type defines a set of value along with well-
defined operations stating its input-output behavior.
Eg: String, integer, float etc.,
A data structure is a physical implementation that
clearly defines a way of storing, accessing, manipulating
data stored in a data structure.
A data stored in a data structure has a specific work
pattern.
Eg: STACK – all insertions and deletions takes place at
one end only.
Types of Data Structures:
Data structures can be classified into two types.
1. Simple Data Structures:
These are normally built from primitive data type like
integers, characters, decimal, etc.,
Eg: Array or Linear Lists
2. Compound Data Structures:
Simple Data structures can be combined in various
ways to form more complex structures called
compound data structures.
Linear data structures:
These are single level data structures.
Its elements form a sequence.
Eg: STACK, QUEUE, LINKED LIST.
Non-Linear data structures:
These are multi-level data structures.
Eg: Tree.
Built-In Data Structures in Python:
List, Tuples, Dictionaries, Sets.
Operations on Data Structures:
The basic operation that are performed on data
structures are as follows:
1. Insertion – addition of a new element.
2. Deletion – removal of a data element.
3. Searching – searching an element.
4. Traversal – Processing all the elements one by one.
5. Sorting – Arranging data elements in an order.
6. Merging – Combining two or more similar data
structures.
STACKS:
A Stack is a linear structure implemented in LIFO (Last
In First Out) manner where insertions and deletions
are restricted to occur only at one end – TOP position.
The technical terms for insertion in a stack and
deletion from a stack are PUSH and POP respectively.
PEEK: It is just inspecting the value at the TOP
position of a Stack without removing it.
OVERFLOW: It will happen when one tries to push an
item into the stack that is already full.
UNDERFLOW: It will happen when one tries to pop an
item from an Empty Stack.
'''Write a function PushDiv5() to push all the elements
which are divisible by 5 from a list DATALIST
onto a stack NEWSTK. Also demonstrate Pop and
Peek operations respectively with the functions
PopSTK() and PeekSTK()
'''
NEWSTK=[]
def PushDiv5():
for i in DATALIST:
if i%5==0:
[Link](i)
def PopSTK():
if len(NEWSTK)==0:
print("Stack is Underflow! ")
else:
print("Deleted Element = ", [Link]())
def PeekSTK():
if len(NEWSTK)==0:
print("Stack is Underflow! ")
else:
print("Top Most Element = ",
NEWSTK[len(NEWSTK)-1])
def DisplaySTK():
for i in range(len(NEWSTK)-1,-1,-1):
print(NEWSTK[i])
DATALIST=[15,12,30,10,24,18,25]
while True:
print("STACK Menu")
print("**********")
print("1. Push")
print("2. Pop")
print("3. Peek")
print("4. Display")
print("*. Exit")
ch=int(input("Ur Choice? "))
if ch==1:
PushDiv5()
elif ch==2:
PopSTK()
elif ch==3:
PeekSTK()
elif ch==4:
DisplaySTK()
else:
print("Invalid Choice...")
break
Stack Applications:
1) Reversing a Line:
Step 1: Read a character and push it to the stack until
end of line.
Step 2: Pop each character and displays it from top
position of the stack.
Example:
Text = “FINANCE”
PUSH(“F”) PUSH(“I”) PUSH(“N”) PUSH(“A”)
PUSH(“N”) PUSH(“C”) PUSH(“E”)
POP() OUTPUT: E
POP() OUTPUT: EC
POP() OUTPUT: ECN
POP() OUTPUT: ECNA
POP() OUTPUT: ECNAN
POP() OUTPUT: ECNANI
POP() OUTPUT: ECNANIF
2) Polish String:
It helps in the conversion of arithmetic expressions
in high-level programming languages into machine
readable form.
Complex arithmetic operations can be converted
into polish strings using stacks which then can be
executed in two operands and an operator form.
Stack Applications on Polish Strings:
1. Infix to Postfix Conversion.
2. Evaluation of Postfix expression.
1. Infix to Postfix Conversion:
The given infix expression can be converted to postfix
expression using the following algorithm.
Algorithm:
Step 1: Parenthesis the given infix expression using the
priority of the operator.
() - parenthesis
** - exponentiation
* or / - multiplication of division
+ or - - addition or subtraction
Eg: (A + B) * C – D ** E / F
X = (((A + B) * C)-((D ** E) / F)))
Step 2: Scan the tokens left to right and repeat the Step
3 until end of the expression.
Step 3:
If token is operand, then write it to output Y.
If token is ‘(’ or operator – Push it to stack
If token is ‘)’ – pop required no. arguments and write it
to output Y.
Step 4: Write the output Y which is postfix form.
Example:
Push ‘(‘
Push ‘(‘
Push ‘(‘
Write ‘A’ Output Y = A
Push ‘+’
Write ‘B’ Output Y = AB
Pop ‘+ and Write ‘+’ Output Y = AB+
Push ‘*’
Write ‘C’ Output Y = AB+C
Pop ‘* and Write ‘*’ Output Y = AB+C*
Push ‘C’
Push ‘(‘
Push ‘(‘
Write ‘D’ Output Y=AB+C*D
Push ‘**’
Write ‘E’ Output Y=AB+C*DE
Pop ‘**’ and Write ‘**’ Output Y=AB+C*DE
Push ‘/’
Pop ‘/’ and Write ‘/’ Output Y=AB+C*DE/
Pop ‘-‘ and Write ‘-‘ Output Y=AB+C*DE/-
2. Evaluation of Postfix expression:
Any postfix expression can be evaluated using stack in
the following ways.
Step 1: Scan a postfix expression character by
character.
Repeat Step 2 until the end of the postfix
expression.
Step 2: If the operand encounters, push it to the stack
If operator encounters pop required no. of
arguments and push the result back to the stack.
For example:
What will the value of the following postfix expression?
If A=20 B=10 C=3 D=40
AB+C*D-
Push 20
Push 10
Pop 20 and 10, perform 20+10=30 Push 30
Push 3
Pop 30 and 3, perform 30*3=90 Push 90
Push 40
Pop 90 and 40, perform 90-40=50, Push 50
So, Final output=50