CH 9.

Data Structure – I
Linear List
CBSE – CLASS – XII
COMPUTER SCIENCE WITH PYTHON (NEW)
(SUBJECT CODE : 083)
Objectives 2

 To understand about data structure. – STACK

 Operations on Stack
 Searching
 Adding
 Deleting
 Merging
 Applications of Stack
 Problems based on stack
Introduction 3

 What is data structure?

 Is a named group of data of different data types which is stored in a

specific way and can be processed as a single unit.

 A data structure has well-defined operations, behavior and

properties.
Data Type Vs Data Structure 4

DATA TYPE defines the type of values we DATA STRUCTURE is physical implementation
can store and operations we can perform. that clearly defines a way of storing, accessing
and manipulation of data stored in data
For example in ‘int’ data type we cannot
structure.
store decimal / float values, we cannot
multiply two string type values. It also Every data structure has a specific way of
specifies amount of memory it will take insertion and deletion like STACK work on LIFO
where as QUEUE works on FIFO.

In python we will use LIST as a data structure

Types Of Data Structure 5

Data
Structure

Complex
Simple Data
Data
Structure
Structure

Integer Float String Linear Non Linear

Stack Queue Linked List Tree Graph

Types Of Data Structure 6

 Data structure can be classified into following two types:

 Simple Data structure : these are built from primitive data types like
integer, float, string or Boolean.
 Example: Linear List or Array

 Complex Data structure : simple data structure can be combined in

various way to form more complex data structure. It is of two types.
 Linear : are single level data structure i.e. in linear fashion to form a
sequence. Example : STACK, QUEUE, LINKED LIST
 Non-Linear: are multilevel data structure. Example: TREE and GRAPH
Linear List Arrays 7

 Refers to named list of finite number of n similar data elements. Each of the data
elements can be accessed by its unique index/subscript position usually 0,1,2,3,…

 For example if the list mylist contains 10 elements then first element will be
mylist[0], second will be mylist[1] and so on.

 Array can be Single Dimensional or Multidimensional. In Python arrays are

implemented through List data types as Linear List or through NumPy arrays.

 Note: Its open source python Module that offers functions and routines for fast
mathematical computation on arrays & matrices. You must import numpy
module before use ie: import numpy
Stack 8

 Allow to insert and delete items from one end only called TOP.

 Stack works on LIFO principle. It means items added in list will be removed first.

 Real life Example: Stack of Plates, Books, Bangles

 Computer based examples: Undo Operation, Function Call etc

Operations On Data Structure 9

OPERATIONS DESCRIPTION

INSERTION Addition of new datato data structure

DELETION Removal of data element from data structure

SEARCHING Finding specific data element in data structure

TRAVERSAL Processing all data elements one by one

Arranging data elements in ascending or

SORTING
descending order

Combining elements of two similar data structure to

MERGING
form a new data structure.
Linear List 10

 A linear data structure forms a sequence.

 When elements of linear structure are homogenous and are represented

in memory means of sequential memory location are called arrays.

 An Array stores a list of finite number(s) of homogenous data elements.

 When upper bound and lower bound of linear list are given, its size can be
calculated as :
Size of the list is = (6 – 0) + 1 = 7
 Size of List = (Upper Bound - Lower Bound) + 1
Index 0 1 2 3 4 5 6
values 10 20 30 40 55 70 45
Stack - Operations 20

 Searching : linear_search1.py linear_search2.py

 Push / Insert : push.py
 Pop / Delete : push.py
 Traversal : iteration.py
 Is_Empty() :
 Is_Full() :
 Sorting :
 Merging :
 Stack 21

 A stack is a collection of data items that can be accessed at only one end, called top.

 Items can be inserted and deleted in a stack only at the top.

 The last item inserted in a stack is the first one to be deleted.

 Therefore, a stack is called a Last-In-First-Out (LIFO) data structure.

 2 mains operations on Stack is PUSH & POP

 PUSH means inserting new item at top and POP means deleting item from top.
Other Stack Term 22

 Peek : getting the most recent value of stack i.e : value at TOP

 OverFlow : a situation when we are Pushing item in Stack that is full.

 Underflow : a situation when we are Popping item from empty stack

 Append (), pop (),

 Push & Pop 23

 Is_Empty () :
 Is_Full () :
 Push () :
 Pop () :
24
25
 2 30
1 20 26
0 10 0 10

1 20
0 10

2 30
1 20
0 10
CBSE_March_2025 27
CBSE_March_2025 28

ANS(i):

def push_Clr(ClrStack, new_Clr):

ClrStack.append(new_Clr)
CBSE_March_2025 29

ANS(ii):

def pop_Clr(ClrStack):
if len(ClrStack) == 0:
# OR if not ClrStack:
# OR if ClrStack == []:
print("Underflow")
else:
return(ClrStack.pop())
 CBSE_March_2025 30

ANS(iii):

def isEmpty(ClrStack): (i)

(1 Mark for correct definition of push_Clr(ClrStack, new_Clr))
if len(ClrStack) == 0:
(ii)
# OR if not ClrStack: (½ Mark for correctly checking and displaying “Underflow”)
(½ Mark for correctly popping and returning popped tuple/data)
# OR if ClrStack == []:
(iii)
return True (½ Mark for correctly checking whether the Stack is Empty or not)
(½ Mark for correctly returning/printing the required values)
else:
return False
CBSE_March_2025 31
CBSE_March_2025 32
ANS(i):

def push_trail(N,myStack):
for i in range(-5,0,1):
# Any other correct loop
myStack.append(N[i])
CBSE_March_2025 33
ANS(ii):

def pop_one(myStack):
if not myStack:
#OR if myStack==[]:
#OR if len(myStack)==0:
print('Stack Underflow')
else:
return myStack.pop()
CBSE_March_2025 34
ANS (iii):

def display_all(myStack):
if not myStack:
#OR if myStack==[]:
#OR if len(myStack)==0:
print("Empty Stack")
else:
for i in myStack[::–1]:
#print(myStack[::-1])
print(i,end=' ')
CBSE_SQP_2024-25 35
 CBSE_SQP_2024-25 36
(B)
Write the definition of a user-defined function `push_even(N)` which
accepts a list of integers in a parameter `N` and pushes all those
integers which are even from the list `N` into a Stack named
`EvenNumbers`.

Write function pop_even() to pop the topmost number from the stack
and returns it. If the stack is already empty, the function should display
"Empty".

Write function Disp_even() to display all element of the stack without

deleting them. If the stack is empty, the function should display 'None'.

For example: If the integers input into the list `VALUES` are: [10, 5, 8, 3, 12]
Then the stack `EvenNumbers` should store: [10, 8, 12]
CBSE_March Reexam_2024 37
CBSE_March _2023 38
CBSE_March _2023 39
CBSE_March _2023 40
SQP1 _2023 41
SQP2 _2023 42
SQP3&4 _2023 43
 44

Type II Questions
Infix , prefix and postfix notation 45
Infix Notation: The operator is placed between the operands.

Example : A + B

Prefix Notation (Polish Notation): The operator comes before the operands.

Example: +AB

Postfix Notation (Reverse Polish Notation, RPN): The operator comes after the operands.

Example: AB+
Type II-T1 Question 46
Evaluate the following postfix notation of expression:

Q1. False, True, NOT, OR, True, False, AND, OR

Type II-T2 Question 47
Evaluate the following postfix expression, showing the stack elements.

Q1. 250, 45, 9,/, 5,+, 20, *, - Ans: 50

Q2. 10,40, 25, -, *, 15, 4, *, + Ans: 210

Q3. 12, 2, /, 34, 20, -, +, 5, + Ans: 25

Ans: 20
Q4. 12, 2, *, 24, 20, -, +, 8, -
Type II-T3 Question 48
Convert the following infix expression into equivalent postfix notation,
showing the stack content for each step of conversion.
Ans: A B C D ^ * + E -
Q1. A + B * C ^ D - E

Ans:
Q2.

Q3. Ans:

Q4.
Ans:
 57

Thank You
Dept Of Computer Science