What is Data Structure?
A data structure is a particular way of organising data in a computer so
that it can be used effectively. The idea is to reduce the space and time
complexities of different tasks.
A data structure is not only used for organising the data. It is also used
for processing, retrieving, and storing data.
Types of datastructure:
1. Array:An array is a collection of data items stored at contiguous
memory locations. The idea is to store multiple items of the same
type together.
2. Stack:
Stack is a linear data structure which follows a particular order in
which the operations are performed. The order may be LIFO(Last In
First Out) or FILO(First In Last Out). In stack, all insertion and
deletion are permitted at only one end of the list.
3. Queue:
Queue is a linear structure which follows a particular order in which
the operations are performed. The order is First In First Out (FIFO).
In the queue, items are inserted at one end and deleted from the
other end.
[Link] List:
Linked List is a linear data structure. Linked list are special list of some
data elements are linked to one another.
Each element is called node. It has two parts INFO part which stores
information, and the reference part which stores the address of the next
element.
Linked list can be of two types: Singly linked list, Doubly linked list
[Link]:
Trees are multi level data structures having a hierarchical relationship
among its elements called nodes. Top most node is called root of the tree.
Bottom most nodes are called leaves of the trees.
Nodes have reference point , pointing to the nodes below.
A Binary Tree is represented by a pointer to the topmost node in the tree.
If the tree is empty, then the value of root is NULL.
Data structure operations
Data structure operations are the methods used to manipulate the data in a
data structure. The most common data structure operations are:
Traversal
processing all the data elements one after the next
Insertion
Insertion operations add new data elements to a data structure.
Deletion
Deletion operations remove data elements from a data structure.
Search
Search operations are used to find a specific data element in a data
structure.
Sort
Sort operations are used to arrange the data elements in a data
structure in a specific order.
Merge
Merge operations are used to combine two data structures into one.
This operation is typically used when two data structures need to be
combined into a single structure of a same type.
Stack :
Stack is a linear data structure that follows a particular order in which
the operations are performed. The order may be LIFO(Last In First
Out).
Basic Operations of Stack Data Structures:
Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.
Term words used in Stack:
Peek: Returns the top element without removing it.
IsEmpty: Checks if the stack is empty.(underflow)
IsFull: Checks if the stack is full (in case of fixed-size arrays).
(overflow)
Push operation:
def push(stk, item):
[Link](item)
top=len(stk)-1
pop operation:
def pop(stk):
item=[Link]()
display operation:
def display(stk):
top=len(stk)-1
print(stk[top] )
for a in range(top-1,-1,-1):
print(stk[a])
1) program to insert student name and mark into the stack
whose mark is greater than 70 using dictionary
stk=[]
d={}
def pushitem ():
for i in range (5):
name=input("enter name :")
mark=int(input("enter mark :"))
d[name]=name
d[mark]=mark
if d[mark]>70:
[Link]([d[name],d[mark]])
def popitem():
print("popped element is:",[Link]())
def displayitem ():
top=len(stk)-1
for i in range (top,-1,-1):
print(stk[i])
pushitem()
displayitem ()
popitem()
displayitem()
output:
enter name :jai krishna
enter mark :78
enter name :ajai
enter mark :67
enter name :mithun
enter mark :89
enter name :arya
enter mark :90
enter name :sanjai
enter mark :88
['sanjai', 88]
['arya', 90]
['mithun', 89]
['jai krishna', 78]
popped element is: ['sanjai', 88]
['arya', 90]
['mithun', 89]
['jai krishna', 78]
2) Program to insert book name in to the stack whose name is
given below and display the inserted books name in the stack.
Stk=[ ]
def pushitem ():
ch='s'
while ch=='s':
bname=input("enter the book name:")
if bname in['cs',"sumita","sl","rd"]:
[Link](bname)
ch=input("do u want to countine s/n")
print(stk)
def displayitem ():
top=len(stk)-1
print("elements in the stack :")
for i in range(top,-1,-1):
print(stk[i])
pushitem()
displayitem()
output:
enter the book name:sl
do u want to countine s/ns
enter the book name:rd
do u want to countine s/ns
enter the book name:cs
do u want to countine s/ns
enter the book name:math
do u want to countine s/nn
['sl', 'rd', 'cs']
elements in the stack :
cs
rd
sl
3) Write a menu driven program to push,pop and display
elements from stack using list.
stk=[]
def pushitem ():
ch='s'
while ch=='s':
bname=input("enter the book name:")
if bname in['cs',"sumita","sl","rd"]:
[Link](bname)
ch=input("do u want to countine s/n")
print(stk)
def popitem ():
print("popped item is :",[Link]())
def displayitem ():
top=len(stk)-1
print("elements in the stack :")
for i in range(top,-1,-1):
print(stk[i])
ch='y'
while ch=='y':
print('''Stack operation:
[Link]
[Link]
[Link]''')
op=int(input("enter your choice:"))
if op==1:
pushitem()
elif op==2:
popitem()
elif op==3:
displayitem()
else:
print("enter the valid option which is listed above:")
ch=input("do you want to continue y/n:")
output:
Stack operation:
[Link]
[Link]
[Link]
enter your choice:1
enter the book name:sl
do u want to countine s/ns
enter the book name:math
do u want to countine s/ns
enter the book name:cs
do u want to countine s/nn
['sl', 'cs']
do you want to continue y/n:y
Stack operation:
[Link]
[Link]
[Link]
enter your choice:3
elements in the stack :
cs
sl
do you want to continue y/n:y
Stack operation:
[Link]
[Link]
[Link]
enter your choice:2
popped item is : cs
do you want to continue y/n:y
Stack operation:
[Link]
[Link]
[Link]
enter your choice:3
elements in the stack :
sl
do you want to continue y/n:n
4) write a program to insert doctor’s doctors dept id and name
whose dept id is only 205. In the stack .
stk=[ ]
def pushitem ():
for i in range (5):
name=input("enter name :")
id=int(input("enter mark :"))
if i==205:
[Link](name,id)
def popitem():
print("popped element is:",[Link]())
def displayitem ():
top=len(stk)-1
for i in range (top,-1,-1):
print(stk[i])
pushitem()
displayitem ()
popitem()