## -:Data-Structures:-

• The logical or mathematical model of a particular organization of data is called data structure. It is a way of storing, accessing, manipulating data.

• Types of data structure:

Data Structures
|
|-Linear
|   |-Arrays
|   |-Stacks
|   |-Queues
|
|-Non-Linear
|- Trees
|- Graphs
|- Tables
|- Sets

• Operation on data structure:

Traversing: - Accessing each record exactly once.
Insertion: - Adding a new element to the structure.
Deletion: - Removing element from the structure.
Searching: - Search the element in a structure.
Sorting: - Arrange the elements in ascending and descending order.
Merging: - Joining two data structures of same type.

List: - An array or list is the collection of elements in ordered way.

There are two types of arrays:
- One dimensional list (1-D Lists)
- Multi-dimensional list (Nested Lists)

Traversing 1-D array (List):

L = [10, 20, 30, 40, 50]
for i in L:
print (i)

Output:

10
20
30
40
50
>>>

Inserting Element in a list: There are two ways to insert an element in a list.
- If the array is not sorted
- If the array is sorted

If the array is not sorted: In this case, enter the element at any position using insert() function or add the element in the last of the array using append() function.

Example:

L = [15, 8, 25, 45, 13, 19]
L.insert(3,88) # insert element at the index 3
print(L)

Output:
[15, 8, 25, 88, 45, 13, 19]

If the array is sorted: In this case, import bisect module and use the functions bisect() and insort(). bisect(): identifies the correct index for the element and returns the index. insort(): Inserts the element in the list in its correct order.

Deletion of an element from a List: To delete an element from a list we can use remove() or pop() method.

Example:

`L= [10, 15, 35, 12, 38, 74, 12]val=int(input("Enter the element that you want to delete: "))print ("List Before deletion of element: ", L)L.remove(val)print("After deletion the element ", val," the list is: ", L)`

Output:

Enter the element that you want to delete: 12
List Before deletion of element:  [10, 15, 35, 12, 38, 74, 12]
After deletion the element 12 the list is:  [10, 15, 35, 38, 74, 12]
>>>

Searching in a List: There are two types of searching techniques we can use to search an element in a list. These are:
- Linear Search
-Binary Search

(i) Linear Search: It is a simple searching technique.

Program:

`L = eval(input("Enter the elements: "))n = len(L)item = eval(input("Enter the element that you want to search: "))count = 0for i in range(n):    if L[i]==item:        print("Element found at the position :", i+1)        count += 1        breakif count == 0:    print("Element not Found")`

Output:

Enter the elements: 5,3,9,6,8,7,1
Enter the element that you want to search: 6
Element found at the position: 4
>>>

(ii) Binary Search:

Binary search can work for only sorted arrays whereas linear search can work for both sorted as well as unsorted arrays.

You can understand binary search method by following program: -

`def bisearch (ar, key):    low = 0    high = len(ar)-1    while low <= high :        mid = int ((low+high)/2)        if key == ar[mid]:            return mid        elif key < ar [mid]:            high = mid - 1        else :            low = mid +1    else :    # loop else         return -999ar = [12,16,19,21,26,59,86,92,97]item = int (input("Enter search item : " ))res = bisearch(ar , item)if res >= 0:    print (item , "FOUND at index ", res+1)else :    print ("Sorry ! ",item ,"Not FOUND in array")`

Output:

Enter search item: 19
19 FOUND at index 2
>>>

Linear Search
- Access of elements sequentially.
- Elements may or may not be in sorted order.
- Takes more time to search an element.
- Easy
- Efficient for small array.

Binary Search

- Access of elements randomly.
- Elements must be in sorted order i.e. ascending or descending order
- Takes less time to search an element.
- Tricky
- Efficient for larger array

Sorting: To arrange the elements in ascending or descending order. There are many sorting techniques.

Program:

`L = eval(input("Enter the elements:"))n=len(L)for p in range(0, n-1):    for i in range(0, n-1):        if L[i] > L[i+1]:            L[i], L[i+1] = L[i+1], L[i]print("The sorted list is : ", L)`

Output:

Enter the elements:[5,3,26,4,9]
The sorted list is:  [3, 4, 5, 9, 26]
>>>

Stack: It is a linear data structure. 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. It follows the principle Last in First out (LIFO).

There are two basic operations associated with stack: -
- Push: Insert the element in stack
- Pop: Delete the element from stack

`S= []from os import system#menu displaydef menu():    ch = 0    while(ch<1 or ch>4):        #print("\n" 100)        anyvar = system("cls")        print("\n\n\n\n\n")        print ("\t\t\t1: PUSH")        print ("\t\t\t2: POP")        print ("\t\t\t3: DISPLAY")        print("\t\t\t4: EXIT")        ch = int(input("\n\t\tEnter a choise (1- 4):"))    return chdef push():    #code to push an item    item = int(input("\t\t\tEnter an item to push: "))    S.append(item)    print("\t\t\t ITEM", item," PUSHESD IN THE STACK")def pop():    #code to pop from stack    if (S ==  []):        prÃ­nt ("\t\t\t NO ITEM TO POP")    else:        item = S.pop()        print ("\t\t\t ITEM ", item," POPPED FROM THE STACK") def display():    #code to display stack    if (S== []):        print ("\t\t\tEMPTY STACK")    else:        print ("\t\t\t",)        for i in S:            print( i, '', end="")#code to call all functionsimport sysch = 0while(ch != 4):    ch=menu()    if(ch == 1):        push()    elif(ch == 2):        pop()    elif(ch == 3):        display()    elif(ch == 4):        print ("\t\t\t ABORTING PROGRAM.")        sys.exit()        anyvar = input("\n\t\t\tPress any key to continue... \n")`

QUEUE: Queue is a linear data structure. Queue is a list of elements in which insertion takes place at one end called REAR and deletion takes place only at the other end, called the FRONT. It follows the principle First In First Out (FIFO).

There are two basic operations associated with stack:
- Enqueue: Insert the element in queue
- Dequeue : Delete the element from queue.

`Q = []from os import system#menu displaydef menu():    ch = 0    while(ch<1 or ch>4):        #print ("\n"*100)        anyvar = system("cls")        print ("\n\n\n\n\n")        print ("\t\t\t1: INSERT")        print ("\t\t\t2: DELETE")        print ("\t\t\t3: DISPLAY")        print ("\t\t\t4: EXIT")        ch = int(input("\n\t\t\tEnter a choise (1-4): "))    return chdef insert():    #code to insert an item    item = int(input("\t\t\tEnter an item to insert: "))    Q.append(item)    print("\t\t\tITEM", item," INSERTED IN THE QUEUE")def delete():    #code to delete from queue    if (Q == []):        print ("\t\t\tNO ITEM TO DELETE")    else:        item = Q.pop(0)        print ("\t\t\t ITEM", item," DELETED FROM THE QUEUE")def display():    #code to display stack    if (Q == [] ):        print ("\t\t EMPTY QUEUE")    else:        print ("\t\t\t",)        for i in Q:            print (i, '', end = " ")#code to call all functionsimport sysch = 0while(ch != 4):    ch = menu()    if(ch == 1):        insert()    elif (ch == 2):        delete()    elif(ch == 3):        display()    elif(ch == 4):        print("\t\t\tABORTING PROGRAM.")        sys.exit()        anyvar = input("\n\t\t\tPress any key to continue... \n")`

### Some important Questions

Q1. What do you mean by Data Structure?

Answer = Data Structure means organization of data. A data structure has well defined operations or behavior.

Q2. FIFO data structure is?

Q3. LIFO data structure is?

Q4. Can we have nested list?

Q5. Name one linear data structure.

Q6. Name one non-linear data structure.

Q7. Name the operation for insertion in a stack.

Q8. Name the operation for deletion from a stack.

Q9. Name the function to find length of a list.

Q10. Indexing in list starts from?

Q11. How is Data Structure different from Data Type?

Answer = Data Structure provides information regarding organization of data whereas Data Type provides information regarding the domain of values and operations that can be perform on data.

Q12. Define Stack and Queue.

Stack: - A stack is a linear list also known as LIFO list with the special property that items can be added or removed from only one end called the top.
Queue: - A queue is a linear list also known as FIFO list with the special property that items can be added at one end and removed from the other.

Q13. Name some operations commonly performed on data structures?

Answer = Traversal, Insertion, Deletion, Searching, Sorting, Merging etc.

Q14. What is a list?

Answer = A list is a mutable sequence of data elements indexed by their position. A list is represented using [ ]. E.g. L= [10, 20, 30]

Q15. What is traversing? Write python code to traverse a list.

Answer = Traversing means accessing or visiting or processing each element of any data structure.

L = [10, 20, 30, 40, 50]
for i in L:
print (i)

Q16. Name the methods used for inserting and deleting elements from a list.

Answer = Various methods for inserting elements in a list are - insert(), append(), extend() and methods used for deleting items from a list are – pop() , remove(), clear()

Q17. Write some applications of stack.

Answer = Reversing a string, compilers uses stack to store previous state of program, undo mechanism in text editors and backtracking.

Q18. Write some applications of queue.

Answer = Sharing of resources, CPU uses queue, Airport authorities uses queue for runways and many computer algorithms uses queue.

Q19. Describe similarities between stack and queue.

(i)Both are special cases of linear list.
(ii) Both can be implemented as list.

Q20. Describe differences between stack and queue.

(i) A Stack is LIFO and Queue is FIFO
(ii) Queue can be circular whereas Stack cannot.

Q21. Write a program to implement a stack for the students(studentno, name). Just implement Push.

Answer = Program for push operation in a stack

`  stk = []top = -1def PUSH(stk, student):    stk.append(student)    top = len(stk) - 1sno = int(input("Enter student No:"))sn = input("Enter student Name:")data = [sno,sn]PUSH(stk,data)  `

Q22. Evaluate the following Postfix expression: 4, 10, 5, +, *, 15, 3, /, -

Q23. What is the difference between pop() and pop(0)?

pop() will delete the last element of a list whereas pop(0) will delete element at index zero of a list.

Thankyou!!!!!

For Solution of ‘Sumita Arora’ visit on Path Walla