DATA STRUCTURE

INTRODUCTION TO DATA STRUCTURES

The term data structure is defined as a way of organizing and storing data such that we
can access and modify it efficiently.

We can categorize the data structures as primitive and non-primitive.

INTRODUCTION TO STACKS

A stack is a data structure that provides temporary storage of data

The element stored last will be retrieved first. This method is also called LIFO – Last In
First Out .

In real life we can think of stack as a stack of copies,

stack of plates
, stack of rotis etc.

The first plate put in the stack is the last one to be removed.

Similarly, last plate to put in the stack is the first one to be removed.

OPERATIONS ON STACK

A stack is a linear data structure.

It is controlled by two operations: PUSH and POP .

Both the operations take place from one end of the stack, usually called top.
Push operation adds an element to the top of the stack.

Pop operation removes an element from the top of the stack.

These two operations implement the LIFO method.

.IMPLEMENTATION OF STACK AS A LIST

Stack can be easily implemented in Python using methods of list.

The basic operations that are performed on stack are:

Creation Of Stack
Stack can be created using list with the help of statement

st=[]

this statement creates an empty stack.

Push(Insertion) In The Stack

The push operation takes place with the help of append() function.

The append() functions adds the new element at the end i.e. at the top of the list.

a=int(input("Enter any number :")) st.append(a)

Pop(Deletion) From The Stack

The pop operation takes place with the help of pop() function that removes the last(top
most) element from the stack.

Before removing an element from the stack it is necessary to check whether the stack is
empty or not.

To check whether the stack is empty or not we can use the statement.

if(st= = []):
 print(“Stack is Empty”)
else:
print ("Deleted element is : ",st.pop())

Display(Traversal) Of Stack

Display/traversal implies visiting each and every element of the stack and displaying
them.

The display operation starts from the top position of the stack.

Thus to perform the display operation we first calculate the length of the stack .

and using a looping statement display each element of the stack as follows:

length=len(st)
for i in range(length-1,-1,-1):
print (st[i])

Here len() function calculates the length of the stack.

After this the for loop is used to visit each element from length-1 to 0 and display it
using print statement.

Remember:
To visit or access elements of stack, index values are used.
The first element of the stack is at index 0 i.e. st[0].
the second will be at index 1 i.e. st[1] and so on.

PROGRAM TO IMPLEMENT STACK AS A LIST

st=[]
ans="y"
while(ans=="y"):
print ("1. PUSH")
print ("2. POP ")
print ("3. Display")
choice=eval(input("Enter your choice: "))
if (choice==1):
a=int(input("Enter any number :"))
st.append(a)
elif (choice==2) :
if (st==[]):
print ("Stack Empty" )
else:
print ("Deleted element is : ",st.pop())
elif (choice==3):
length=len(st)
for i in range(length-1,-1,-1):
print (st[i])
else:
print("Invalid Input")
ans= input("Do you want to continue? y or n"

OUTPUT

1.PUSH
2.POP
3.Display
Enter your choice: 1

Enter any number :12

Do you want to continue? y or n y

1.PUSH
2.POP
3.Display
Enter your choice: 1

Enter any number :23

Do you want to continue? y or n y

1.PUSH
2.POP
3.Display
Enter your choice: 1

Enter any number :45

Do you want to continue? y or n y

PUSH
POP
Display
Enter your choice: 3

45

23

12

Do you want to continue? y or n y

PUSH
POP
Display
Enter your choice: 2

Deleted element is : 45
Do you want to continue? y or n y

PUSH
POP
Display
Enter your choice: 2

Deleted element is : 23

Do you want to continue? y or n y

PUSH
POP
Display
Enter your choice: 3

12

Do you want to continue? y or n n

Program 07 – Stack Operations

Aim: To write a menu driven program to implement stack using a list data structure.
Each node should be having a book number, book name and price.

Program:
s = []

def push():
b_ID=int(input('enter book no.'))
b_NAME=input('enter book name')
b_PRICE=float(input('enter price'))
data=b_ID,b_NAME,b_PRICE
s.append(data)
print("Book added to stack")

def pop():

if len(s)==0:
print('Stack is empty')
 else:
dn = s.pop()
print(dn)
def disp():
if len(s)==0:
print('empty stack')
else:
for i in range(len(s)):
print("Book Id :",s[i][0])
print("Book Name :",s[i][1])
print("Book Price :",s[i][2])
while(1):
print('''menu
1. Push
2. Pop
3. Display
4. Exit''')
ch=int(input('enter choice'))
if (ch==1):
push()
elif (ch==2):
pop()
elif(ch==3):
disp()

elif (ch==4):
break
else:
print('invalid input')

Sample Input and Output

menu
1. Push
2. Pop
 3. Display
4. Exit
enter choice1
enter book no.100

enter book nameComputer Science with Python XII

enter price365
Book added to stack

menu
1. Push
2. Pop
3. Display
4. Exit
enter choice1
enter book no.101

enter book nameMove fast with Python XII

enter price325
Book added to stack

menu
1. Push
2. Pop
3. Display
4. Exit
enter choice3
Book Id : 100
Book Name : Computer Science with Python XII

Book Price : 365.0

Book Id : 101
Book Name : Move fast with Python XII
Book Price : 325.0

menu
1. Push
2. Pop
3. Display
4. Exit
enter choice2
(101, 'Move fast with Python XII', 325.0)

menu
1. Push
2. Pop
3. Display
4. Exit
enter choice3
Book Id : 100
Book Name : Computer Science with Python XII

Book Price : 365.0

enter choice2
(100, 'Computer Science with Python XII', 365.0)

menu
1. Push
2. Pop
3. Display
4. Exit
enter choice3
empty stack
menu
1. Push
2. Pop
3. Display
4. Exit
enter choice4
14.APPLICATIONS OF STACK
When a program executes, stack is used to store the return address at time of function
call.

After the execution of the function is over, return address is popped from stack and
control is returned back to the calling function.

Converting an infix expression to postfix operation and to evaluate the postfix

expression.
Reversing an array,
converting decimal number into binary number etc.

14.8 INTRODUCTION TO QUEUES

A queue is a data structure that provides temporary storage of data in such a way that
the element stored first will be retrieved first.

This method is also called FIFO – First In First Out.

In real life we can think of queue as a queue of vehicles waiting at the petrol pump,

people waiting at the bus stop for the bus etc.

The first person to enter the queue is the first one to leave the queue.

Similarly, last person to join the queue is the last person to leave the queue.

14.9 OPERATIONS ON QUEUE

A queue is a linear data structure.
It is controlled by two operations: insertion and deletion.
Insertion operation takes place from the rear end of the queue and

deletion operation takes place from the front end of the queue.

Insertion operation adds an element to the queue.

Deletion operation removes an element from the queue.

There are two ends FRONT and REAR of a queue.

FRONT points to the beginning of the filled queue and takes care of deletion operation.

REAR points to the end of the queue and takes care of insertion operation.

These two operations implement the FIFO method.

14.10 IMPLEMENTATION OF QUEUE AS A LIST

Queue can be easily implemented in Python using methods of list.

The basic operations that are performed on queue are:

Creation Of queue

: Queue can be created using list with the help of statement:

queue=[]

this statement creates an empty queue.

Insertion In The Queue

:
The insertion operation takes place with the help of append() function.

The append() functions adds the new element at the end of the list.

Initially the queue is empty.

When the first element, 10 is added to the queue it is both the first and last element.

Thus, both front and rear point to this element. When the next element is added is
added to the queue only the rear changes and front remains the same.

This process continues for all further additions in the queue.

Deletion From The Queue

: The deletion operation takes place with the help of pop() function. The pop() function
removes the last element.

To delete the first element from the queue implemented as a list we use pop(0). This
will delete the first element from the list and shifts all elements one position towards
the left to fill the gap created due to deletion of element from the queue.

Before removing an element from the queue it is necessary to check whether the queue
is empty or not.

To check whether the queue is empty or not we can use the statement:
if( queue= = [])

print(“Queue is Empty”)

Display(Traversal) Of Queue
: Display/traversal implies visiting each and every element of the queue and displaying
them.

The display operation starts from the top position of the queue.

Thus to perform the display operation we first calculate the length of the queue and
using a looping statement display each element of the queue as follows:

length=len(queue)

for i in range(0,length,1):
 print (queue[i])

Here len() function calculates the length of the queue which is stored in the variable
length.

After this the for loop is used to visit each element from 0 to length-1 and display it
using print statement.

Remember:
To visit or access elements of queue, index values are used

. The first element of the queue is at index 0 i.e. queue[0]. the second will be at index 1
i.e. queue[1] and so on.

1 PROGRAM TO IMPLEMENT QUEUE AS LIST

queue=[]

while (1(1):

print( "1. Insertion")

print ("2. Deletion")

print ("3. Display")

choice=eval(input("Enter your choice: "))

if (choice==1):

a=int(inputint(input("Enter any number :")))

queue.append(a)
elif (choice==2):

if (queue==[]):

print ("Queue Empty" )

else:

print ("Deleted element is : ",queue.pop(0))

elif (choice==3):

length=len(queue)

for i in range(0, length,1):

print (queue[i])

elif (choice==4):
breakelif (choice==4):
break
else:

print("Invalid lid

Insertion
DelenpnpDisplay
Entr choiechoieicedd: 1

Enter any number :10

Do you want to continue? y or n y

Insertion
Deletion
Display
Enter your choice: 1

Enter any number :20

Do you want to continue? y or n y

Insertion
Deletion
Display
Enter your choice: 1

Enter any number :30

Do you want to continue? y or n y

Insertion
Deletion
Display
Enter your choice: 3

10

20

30

Do you want to continue? y or n y

Insertion
Deletion
Display
Enter your choice: 2

Deleted element is : 10

Do you want to continue? y or n y

Insertion
Deletion
Display
Enter your choice: 3

20

30

Do you want to continue? y or n n

Program 8 – Queue Operations

Aim: To write a menu driven program to implement queue operations. Each node should
have item no, item name and price.

Program:
q = []

def insert():
it_ID=int(input('Enter item no.'))
it_NAME=input('Enter item name')
it_PRICE=float(input('Enter item price'))
data=it_ID,it_NAME,it_PRICE
q.append(data)
print("Item added to queue")

def delete():

if len(q)==0:
print('Queue is empty')
else:
dn = q.pop(0)
print(dn)

def disp():
if len(q)==0:
 print('empty stack')
else:
for i in range(len(q)):
print("Item Id :",q[i][0])
print("Item Name :",q[i][1])
print("Item Price :",q[i][2])
while(1):
print('''menu
1. Insert
2. Delete
3. Display
4. Exit''')
ch=int(input('enter choice'))
if (ch==1):
insert()
elif (ch==2):
delete()
elif(ch==3):
disp()

elif (ch==4):
break
else:
print('invalid input')

Sample Input and Output

menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice1
Enter item no.100
Enter item nameChilly Chicken

Enter item price250

Item added to queue

menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice1
Enter item no.101

Enter item nameMutton Sukka Varuval

Enter item price300

Item added to queue

menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice3
Item Id : 100
Item Name : Chilly Chicken

Item Price : 250.0

Item Id : 101
Item Name : Mutton Sukka Varuval

Item Price : 300.0

menu
1. Insert
2. Delete
 3. Display
4. Exit
enter choice2
(100, 'Chilly Chicken', 250.0)

menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice3
Item Id : 101
Item Name : Mutton Sukka Varuval

Item Price : 300.0

menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice3
empty stack
menu
1. Insert
2. Delete
3. Display
4. Exit
enter choice4

14.12 APPLICATIONS OF QUEUE

A queue is an appropriate data structure on which information is stored and then
retrieved in FIFO order.

The applications of queue are as follows:

Queues find their use in CPU scheduling,

 printer spooling,
message queuing, computer networks etc.
In time sharing system queues help in scheduling of jobs.