# Example 12.1, page no. 442¶

In [1]:
import numpy
arr = numpy.zeros((2, 2, 2))

print "Reading the elements of an array: "
for i in range(2):
for j in range(2):
for k in range(2):
arr[i][j][k] = int(raw_input())

print "Displaying the elements of an array: "
for i in range(2):
print "\n\t"
for j in range(2):
for k in range(2):
print "\t %3d " %(arr[i][j][k]),
print "\n\t"

Reading the elements of an array:
15
25
26
13
71
9
1
8
Displaying the elements of an array:

15  	  25

26  	  13

71  	   9

1  	   8



## Example 12.2, page no. 442¶

In [3]:
str1 = raw_input("Input the first string: ")
str2 = raw_input("Input the second string: ")
print "The concatenated string is ..."
print str1+str2

Input the first string: Tejaswi
Input the second string: Venugopal
The concatenated string is ...
Tejaswi Venugopal


## Example 12.3, page no. 443¶

In [17]:
class record:
name = ''
regno = ''
avg = 0.0
rank = 0
i = 0
students = []
while True:
print "Processing student %d record..." %(i+1)
print "Student name ?(END to terminate): "
stud = record()
stud.name = raw_input()
if stud.name == 'END':
break
else:
stud.regno = raw_input("Reg. no? ")
stud.avg = float(raw_input("Average marks? "))
students.append(stud)
i+=1
n = i
for i in range(n-1):
for j in range(i+1, n):
if students[i].avg < students[j].avg:
students[i], students[j] = students[j], students[i]
for i in range(n):
students[i].rank = i+1
print "Student records after assigning ranks: "
print "%s%20s%20s%20s" %("Name","REGISTER_NUMBER","AVERAGE","RANK")
print "------------------------------------------------------------------"
for i in range(n):
print students[i].name, "\t\t", students[i].regno, "\t\t\t", students[i].avg, "\t\t\t", students[i].rank

Processing student 1 record...
Student name ?(END to terminate):
Asha
Reg. no? ak001
Average marks? 67.00
Processing student 2 record...
Student name ?(END to terminate):
Bina
Reg. no? ak003
Average marks? 34.00
Processing student 3 record...
Student name ?(END to terminate):
Anand
Reg. no? ak004
Average marks? 67.00
Processing student 4 record...
Student name ?(END to terminate):
Sudeep
Reg. no? ak005
Average marks? 78.00
Processing student 5 record...
Student name ?(END to terminate):
Tejaswi
Reg. no? ak006
Average marks? 89.00
Processing student 6 record...
Student name ?(END to terminate):
Maya
Reg. no? ak007
Average marks? 89.00
Processing student 7 record...
Student name ?(END to terminate):
Prakash
Reg. no? ak008
Average marks? 89.00
Processing student 8 record...
Student name ?(END to terminate):
Raju
Reg. no? ak009
Average marks? 82.00
Processing student 9 record...
Student name ?(END to terminate):
Geetha
Reg. no? ak010
Average marks? 85.00
Processing student 10 record...
Student name ?(END to terminate):
Gopi
Reg. no? ak011
Average marks? 45.00
Processing student 11 record...
Student name ?(END to terminate):
Ganesh
Reg. no? ak012
Average marks? 89.00
Processing student 12 record...
Student name ?(END to terminate):
END
Student records after assigning ranks:
Name     REGISTER_NUMBER             AVERAGE                RANK
------------------------------------------------------------------
Tejaswi 		ak006 			89.0 			1
Maya 		ak007 			89.0 			2
Prakash 		ak008 			89.0 			3
Ganesh 		ak012 			89.0 			4
Geetha 		ak010 			85.0 			5
Raju 		ak009 			82.0 			6
Sudeep 		ak005 			78.0 			7
Anand 		ak004 			67.0 			8
Asha 		ak001 			67.0 			9
Gopi 		ak011 			45.0 			10
Bina 		ak003 			34.0 			11


## Example 12.4, page no. 446¶

In [21]:
import numpy
arr = numpy.zeros((3,3))
print "Reading the elements of 2-D array: "
for i in range(3):
for j in range(3):
arr[i][j] = int(raw_input())
print "Displaying the elements of 2-D array: "
p = arr
for i in range(3):
for j in range(3):
print "arr[%d][%d] = %d" %(i, j, p[i][j]),
print "\tAddress of arr[%d][%d] = %d" %(i, j, id(p[i][j]))

Reading the elements of 2-D array:
1
2
3
4
5
6
7
8
9
Displaying the elements of 2-D array:
arr[0][0] = 1 	Address of arr[0][0] = 52403744
arr[0][1] = 2 	Address of arr[0][1] = 57791200
arr[0][2] = 3 	Address of arr[0][2] = 55892528
arr[1][0] = 4 	Address of arr[1][0] = 55892528
arr[1][1] = 5 	Address of arr[1][1] = 55892528
arr[1][2] = 6 	Address of arr[1][2] = 51486976
arr[2][0] = 7 	Address of arr[2][0] = 58587952
arr[2][1] = 8 	Address of arr[2][1] = 50218032
arr[2][2] = 9 	Address of arr[2][2] = 50218032


## Example 12.5, page no. 449¶

In [22]:
import sys

class node:
def __init__(self, data=0, link=None):
self.data = data
self.link = link

start = None

def add_front(data):
global start
tmp = node(data)
if(start == None):
start = tmp
else:
tmp.link = start
start = tmp

def del_pos(pos):
global start
if (pos == 0):
tmp = start
start = start.link
return
q = start
count = 1
while(q.link != None):
if(count == pos):
tmp = q.link
q.link = tmp.link
return
count += 1
q = q.link
print "\n\nThere is no element at %d position" %pos

def del_elem(data):
global start
if (start.data == data):
tmp = start
start = start.link
return
q = start
while(q.link.link != None):
if(q.link.data == data):
tmp = q.link
q.link = tmp.link
return
q = q.link
if(q.link.data == data):
tmp = q.link;
q.link = None
return
print "\n\nThere is no element whose value is %d" %data

def display_list():
global start
if(start == None):
print "\n\nList empty"
return
q=start
print "\nThe List is..."
while(q != None):
print q.data,
q = q.link
print "\n"

def get_data():
data = int(raw_input("Enter the data: "))
return data

while(1):
print "\n1.Insert at the beginning of the list"
print "2.Delete an element at a give position"
print "3.Delete an element with a give value"
print "4.Quit"
print "Choice: ",
choice =int(raw_input())
if choice == 1:
data = get_data()
add_front(data)
elif choice == 2:
if (start == None):
print "\nList empty"
continue
print "\n\nEnter the position:"
pos = int(raw_input())
del_pos(pos)
elif choice == 3:
if (start == None):
print "\nList empty"
continue
data = get_data()
del_elem(data)
elif choice == 4:
break
display_list()

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 1
Enter the data: 0

The List is...
0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 1
Enter the data: 1

The List is...
1 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 1
Enter the data: 2

The List is...
2 1 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 1
Enter the data: 3

The List is...
3 2 1 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 1
Enter the data: 4

The List is...
4 3 2 1 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 2

Enter the position:
1

The List is...
4 2 1 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 3
Enter the data: 1

The List is...
4 2 0

1.Insert at the beginning of the list
2.Delete an element at a give position
3.Delete an element with a give value
4.Quit
Choice: 4



## Example 12.6, page no. 454¶

In [5]:
import sys

class node:
def __init__(self, info=None, link=None):
self.info = info
self.link = link

last = None
class Circular_Linked:
def create(self, num):
global last
q = node()
tmp = node()
tmp.info = num
if (last == None):
last = tmp
tmp.link = last
else:
tmp.link = last.link
last.link = tmp
last = tmp

def insert(self, num, pos):
global last
q = node()
tmp = node()
q = last.link
for i in range(0, pos-1):
q = q.link
if (q == last.link):
print "There are less than ", pos, " elements"
return
tmp.link = q.link
tmp.info = num
q.link = tmp
if(q==last):
last=tmp

def delete(self):
global last
if(last == None):
print "LIST EMPTY - CANNOT DELETE"
return
print "Data item to be deleted:"
num = int(raw_input())
q = node()
tmp = node()
if( last.link == last and last.info == num):
tmp = last
last = None
return
q = last.link
if(q.info == num):
tmp = q
last.link = q.link
return
while(q.link != last):
if(q.link.info == num):
tmp = q.link
q.link = tmp.link
print num, " deleted"
q = q.link
if(q.link.info == num):
tmp = q.link
q.link = last.link
last = q
return
print "Element not found"

def display(self):
global last
q = node()
if(last == None):
print "List is empty"
return
q = last.link
print "List is:"
while(q != last):
print q.info,
q = q.link
print last.info

co = Circular_Linked()
while(1):
print "\n1.Create Circular Linked List"
print "2.Insert an item"
print "3.Delete an item"
print "4.STOP"
print "Enter your choice:"
choice = int(raw_input())
if choice == 1:
print "How many nodes you want:",
n = int(raw_input())
for i in range(n):
print "\nEnter the element:",
m = int(raw_input())
co.create(m)
elif choice == 2:
print "\nEnter the element:",
m = int(raw_input())
print "\nEnter the position after which this element is inserted:",
po = int(raw_input())
co.insert(m,po)
elif choice == 3:
co.delete()
elif choice == 4:
break
else:
print "Error - Try again"
co.display()


1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
1
How many nodes you want:4

Enter the element:1

Enter the element:2

Enter the element:3

Enter the element:4
List is:
1 2 3 4

1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
1
How many nodes you want:1

Enter the element:5
List is:
1 2 3 4 5

1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
2

Enter the element:0

Enter the position after which this element is inserted:1
List is:
1 0 2 3 4 5

1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
3
Data item to be deleted:
0
0  deleted
Element not found
List is:
1 2 3 4 5

1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
3
Data item to be deleted:
7
Element not found
List is:
1 2 3 4 5

1.Create Circular Linked List
2.Insert an item
3.Delete an item
4.STOP
Enter your choice:
4


## Example 12.7, page no. 461¶

In [10]:
MAXSIZE = 100

class stack:
def __init__(self):
self.stack = []
self.top = -1

def push(pu):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
print "Enter the element to be inserted: "
item = int(raw_input())
pu.stack.append(item)
pu.top += 1

def pop(po):
if(po.top == -1):
print "Stack is empty"
else:
item = po.stack[po.top]
po.top-=1
print "The popped element is: %d" %item

def display(pt):
if(pt.top == -1):
print "Stack is empty"
else:
print "The element(s) of the stack are: "
i = pt.top
while(i>=0):
print "%d" %pt.stack[i],
i-=1

ps = stack()
ch = 'y'

while(1):
print "\n1. Push into the stack"
print "2. POP"
print "3. View elements of the stack"
print "4. Exit"
print "Enter your choice: "
choice = int(raw_input())
if(choice == 1):
push(ps)
elif(choice == 2):
pop(ps)
elif(choice == 3):
display(ps)
elif(choice == 4):
break
else:
print "Invalid Choice"

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
1
Enter the element to be inserted:
12

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
1
Enter the element to be inserted:
23

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
1
Enter the element to be inserted:
67

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
2
The popped element is: 67

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
1
Enter the element to be inserted:
88

1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
3
The element(s) of the stack are:
67 23 12
1. Push into the stack
2. POP
3. View elements of the stack
4. Exit
Enter your choice:
4


## Example 12.8, page no. 463¶

In [2]:
class node:
def __init__(self, link=None):
self.data = None
self.link = link

start = None

def push(top):
new = node()
print "Enter element to be pushed: ",
pushed_item = int(raw_input())
new.data = pushed_item
new.link = top
top = new
return top

def pop(top):
tmp = node()
if(top == None):
print "Stack is empty..."
else:
tmp = top
print "Popped item is: ", tmp.data
top = top.link
tmp.link = None
return top

def display(top):
if(top == None):
print "Stack is empty..."
else:
while(top.link != None):
print top.data,
top = top.link

Top = node()
while(1):
print "\n1.PUSH"
print "2.POP"
print "3.END"
print "Enter your choice: ",
choice = int(raw_input())
if choice == 1:
Top = push(Top)
print "STACK after pushing: "
display(Top)
elif choice == 2:
Top=pop(Top)
print "STACK after popping: "
display(Top)
elif choice == 3:
print "End of comutation"
break
else:
print "Invalid Choice"

1.PUSH
2.POP
3.END
Enter your choice: 1
Enter element to be pushed: 23
STACK after pushing:
23
1.PUSH
2.POP
3.END
Enter your choice: 1
Enter element to be pushed: 12
STACK after pushing:
12 23
1.PUSH
2.POP
3.END
Enter your choice: 1
Enter element to be pushed: 67
STACK after pushing:
67 12 23
1.PUSH
2.POP
3.END
Enter your choice: 2
Popped item is:  67
STACK after popping:
12 23
1.PUSH
2.POP
3.END
Enter your choice: 2
Popped item is:  12
STACK after popping:
23
1.PUSH
2.POP
3.END
Enter your choice: 1
Enter element to be pushed: 88
STACK after pushing:
88 23
1.PUSH
2.POP
3.END
Enter your choice: 2
Popped item is:  88
STACK after popping:
23
1.PUSH
2.POP
3.END
Enter your choice: 2
Popped item is:  23
STACK after popping:

1.PUSH
2.POP
3.END
Enter your choice: 2
Popped item is:  None
STACK after popping:
Stack is empty...

1.PUSH
2.POP
3.END
Enter your choice: 3
End of comutation


## Example 12.9, page no. 467¶

In [2]:
stck = []

def push(sp,ch):
if sp==100:
print "Error : Stack overflow"
else:
sp += 1
stck.append(ch)

def pop(sp):
if sp < 0:
print "Error : Stack underflow"
return 0
else:
sp -= 1
return stck[sp+1]

def alpha(ch):
if (ch>='A' and ch<="Z") or (ch>='a' and ch<="z"):
return True
else:
return False

def num(ch):
if ch>='0' and ch<="9":
return True
else:
return False

def oper(ch):
oparray = ['+','-','*','/','^']
if ch in oparray:
return True
else:
return False

def precedence(ch):
if ch=='(':
i = 0
elif ch=='+' or ch=='-':
i = 1
elif ch=='*' or ch=='/':
i = 2
elif ch=='^':
i = 3
return i

def printerror(n,ifp):
if n==1:
print "Error_1_: Missing operator",
elif n==2:
print "Error_2_: Missing Operand",
elif n==3:
print "Error_3_: Mismatched parentehses",
elif n==4:
print "Error_4_: Illegal character in expression",
elif n==5:
print "Error_5_: Multiletter variable",
print "Column %2d"%ifp

def parse (infix,suffix,error):
ch =''
last = '('
i = 0
sp=-1
bracket = 1
ifp = 0
sfp = 0

push(sp,'(')

while True:
while infix[i] == " ":
i += 1
ifp = i
ch = infix[ifp]

if ch == "(":
if alpha(last) or num(last) or last==')':
error = 1
printerror(1,ifp+1)
bracket +=1
push(sp,ch)
elif ch=="+" or ch=="-" or ch=="*" or ch=="/" or ch=="^":
if oper(last) or (not alpha(last) and not num(last) and last!=")"):
error=1
printerror(2,ifp+1)
while precedence(stck[sp]) >= precedence(ch):
suffix.append(pop(sp))
sfp+=1
push(sp,ch)
elif ch==")":
if oper(last):
error=1
printerror(2,ifp+1)
if last=="(":
error=1
printerror(2,ifp+1)
printerror(1,ifp+1)
while stck[sp] != "(" and sp > 0:
suffix.append(pop(sp))
sfp += 1
sp -= 1
bracket -= 1
elif ch == ' ':
while infix[ifp+1] == " " and not infix[ifp] :
ifp += 1
else:
if alpha(last) or num(last):
error = 1
printerror(1,ifp+1)
printerror(5,ifp+1)
if alpha(ch):
print ch,
suffix.append(infix[ifp])
sfp += 1
elif num(ch):
while num(infix[ifp]):
suffix.append(infix[ifp])
ifp += 1
sfp += 1
ifp -= 1
else:
printerror(4,ifp+1)
last = infix[ifp]
ifp += 1
i = ifp
print ifp,
try:
if not infix[ifp]:
break;
except:
break

if bracket:
error = 1
printerror(3,ifp-1)
return infix,suffix,error
def readexpression():
i = 0
print "The given infix expression is"
infix = list(raw_input())
infix.append(")")

return infix

suffix = []
error = 0
infix = readexpression()
infix,suffix,error = parse(infix,suffix,error)
if not error:
print "The suffix form of the given expression is "
print suffix

The given infix expression is
(a+b)
1 Error_3_: Mismatched parentehses Column  0
a 2 Error_3_: Mismatched parentehses Column  1
3 Error_3_: Mismatched parentehses Column  2
b 4 Error_3_: Mismatched parentehses Column  3
5 Error_3_: Mismatched parentehses Column  4
6


## Example 12.10, page no. 472¶

In [3]:
MAX = 50
queue_arr = []
rear = [-1]
front = [-1]

def add_element():
if (rear[0] == MAX-1):
print "Queue is full..."
return
else:
if(front[0] == -1):
front[0] = 0
print "Enter the new element: "
added_item = int(raw_input())
rear[0] = rear[0]+1
queue_arr.append(added_item)

def remove_element():
if(front[0] == -1 or front[0]>rear[0]):
print "Queue is empty..."
return
else:
dell = front[0]
print queue_arr[dell], " is removed from the Queue"
front[0] = front[0]+1

def display():
if(front[0] == -1 or front[0]>rear[0]):
print "Queue is empty..."
return
else:
print "Queue is: "
for i in range(front[0],rear[0]+1):
print queue_arr[i],

while(1):
print "\n1. Insert an element"
print "2. Display all the elements of the queue"
print "3. Remove elements from the queue"
print "4. Exit from the program"
print "Enter your choice: "
choice = raw_input()
if choice == '1':
add_element()
elif choice == '2':
display()
elif choice == '3':
remove_element()
elif choice == '4':
break
else:
print "Reenter the choice"

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
1
Enter the new element:
23

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
1
Enter the new element:
34

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
1
Enter the new element:
45

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
3
23  is removed from the Queue

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
3
34  is removed from the Queue

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
1
Enter the new element:
45

1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
2
Queue is:
45 45
1. Insert an element
2. Display all the elements of the queue
3. Remove elements from the queue
4. Exit from the program
Enter your choice:
4


## Example 12.11, page no. 477¶

In [6]:
class node:
def __init__(self, link=None):
self.info = None
self.link = link

def enqueue(rear):
new_node = node()
print "Enter the new element: ",
new_node.info = int(raw_input())
new_node.link = None
if (rear != None):
rear.link = new_node
rear = new_node
return rear

def del_queue(f, r):
if f == None:
print "The Queue is empty"
else:
print "The element removed is: ", f.info
if f != r:
f = f.link
else:
f = None
return f

def display(fr, re):
if fr == None:
print "The Queue is empty"
else:
print "The queue is: "
while fr != re:
print fr.info,
fr = fr.link
print fr.info,

rear = None
front = None
while(1):
print "\n1.Insert"
print "2.Delete"
print "3.Quit"
print "Enter choice: ",
choice = int(raw_input())
if choice == 1:
rear = enqueue(rear)
if front == None:
front = rear
elif choice == 2:
front = del_queue(front, rear)
if front == None:
rear = None
elif choice == 3:
break
display(front, rear)


1.Insert
2.Delete
3.Quit
Enter choice: 1
Enter the new element: 23
The queue is:
23
1.Insert
2.Delete
3.Quit
Enter choice: 1
Enter the new element: 34
The queue is:
23 34
1.Insert
2.Delete
3.Quit
Enter choice: 1
Enter the new element: 45
The queue is:
23 34 45
1.Insert
2.Delete
3.Quit
Enter choice: 2
The element removed is:  23
The queue is:
34 45
1.Insert
2.Delete
3.Quit
Enter choice: 2
The element removed is:  34
The queue is:
45
1.Insert
2.Delete
3.Quit
Enter choice: 2
The element removed is:  45
The Queue is empty

1.Insert
2.Delete
3.Quit
Enter choice: 2
The Queue is empty
The Queue is empty

1.Insert
2.Delete
3.Quit
Enter choice: 3



## Example 12.12, page no. 480¶

In [22]:
import numpy

qsize = 50
rear = 0
front = 0
qu = numpy.zeros(50, dtype=numpy.int)
def insert():
global rear
global front
global qsize
if rear == qsize:
rear = 1
else:
rear += 1
if front != rear:
item = int(raw_input("Enter item to be inserted: "))
qu[rear] = item
if front == 0:
front += 1
else:
print "Overflow"
def delete():
global front
global rear
global qsize
if front != 0:
item = qu[front]
if front == rear:
front = 0
rear = 0
return item
if front == qsize:
front = 1
else:
front += 1
return item
else:
print "Underflow"
def display():
global front
global rear
for i in range(front, rear+1):
print qu[i],

choice = 0
while(choice != 3):
print "\n1 - Insert an element into Cqueue"
print "2 - Delete an element into Cqueue"
print "3 - Quit"
choice = int(raw_input())
if choice == 1:
insert()
print "\nCqueue after insertion is: "
display()
elif choice == 2:
item = delete()
print "Item deleted id: ", item
print "\nCqueue after deletion is: "
display()
else:
break


1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
1
Enter item to be inserted: 23

Cqueue after insertion is:
23
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
1
Enter item to be inserted: 34

Cqueue after insertion is:
23 34
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
1
Enter item to be inserted: 45

Cqueue after insertion is:
23 34 45
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
2
Item deleted id:  23

Cqueue after deletion is:
34 45
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
2
Item deleted id:  34

Cqueue after deletion is:
45
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
2
Item deleted id:  45

Cqueue after deletion is:
0
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
2
Underflow
Item deleted id:  None

Cqueue after deletion is:
0
1 - Insert an element into Cqueue
2 - Delete an element into Cqueue
3 - Quit
3


## Exmaple 9.13, page no. 484¶

In [5]:
class node:
data = ''
next = None
class queue:
front = None
nremovals = 0

class prique:
queues = []
nqueues = 0
npromote = 0

def add(que, new_node):
new_node.next = 0
if not que.front:
que.front = new_node
else:
cur = que.front
while(cur.next):
cur = cur.next
cur.next = new_node
return que

def remove_node(que):
removed_node = que.front
if que.front:
que.front = que.front.next
return removed_node

def priq_add(priq, priority, data):
if priority >= priq.nqueues:
print "Error: priority number given is invalid!"
return priq
new_node = node()
new_node.data = data
priq.queues[priority] = add(priq.queues[priority], new_node)
return priq

def priq_remove(priq, priority):
removed_char = ''
if priority >= priq.nqueues:
print "Error: priority number given is invalid!"
return
removed = remove_node(priq.queues[priority])
if not removed:
if priority < priq.nqueues-1:
return priq_remove(priq, priority+1)
else:
return priq, 0
else:
lower_elm = ''
priq.queues[priority].nremovals += 1
if priq.queues[priority].nremovals == priq.npromote:
lower_elm = priq_remove(priq, priority+1)
if lower_elm:
priq_add(priq, priority, lower_elm)
priq.queues[priority].nremovals = 0
removed_char = removed.data
return priq, removed_char

def create_priq(nqueues, npromote):
priq = prique()
priq.nqueues = nqueues
for i in range(nqueues):
priq.queues.append(queue())
priq.npromote = npromote
return priq

def get_option():
print "\n1: Insert an element"
print "2: Remove an element"
print "3: Quit"
print "Choose: "
option = int(raw_input())
return option

def get_data():
data = raw_input("Enter the data: ")
return data

def get_priority():
priority = int(raw_input("Enter the priority: "))
return priority

def display_prique(priq):
print "The priority queue is ..."
for i in range(priq.nqueues):
que = priq.queues[i]
cur = que.front
print i,
while cur:
print cur.data,
if cur.next:
print "->",
cur = cur.next
print ""
print ""

print "No of priority levels: "
nlevels = int(raw_input())
print "No of consecutive removls for proirity promotion: "
nremovals = int(raw_input())
priq = create_priq(nlevels, nremovals)
while True:
option = get_option()
if option == 1:
data = get_data()
priority = get_priority()
priq = priq_add(priq, priority, data)
elif option == 2:
priority = get_priority()
priq, data = priq_remove(priq, priority)
if data == 0:
print "No elements to remove"
else:
print data, " was removed"
elif option == 3:
break
else:
print "BYE"
break
display_prique(priq)

No of priority levels:
4
No of consecutive removls for proirity promotion:
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
1
Enter the data: q
Enter the priority: 0
The priority queue is ...
0 q
1
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
1
Enter the data: w
Enter the priority: 0
The priority queue is ...
0 q -> w
1
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
1
Enter the data: e
Enter the priority: 0
The priority queue is ...
0 q -> w -> e
1
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
1
Enter the data: r
Enter the priority: 0
The priority queue is ...
0 q -> w -> e -> r
1
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
1
Enter the data: z
Enter the priority: 1
The priority queue is ...
0 q -> w -> e -> r
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
2
Enter the priority: 0
q  was removed
The priority queue is ...
0 w -> e -> r
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
2
Enter the priority: 0
w  was removed
The priority queue is ...
0 e -> r
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
2
Enter the priority: 2
No elements to remove
The priority queue is ...
0 e -> r
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
2
Enter the priority: 0
e  was removed
The priority queue is ...
0 r
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
2
Enter the priority: 0
r  was removed
The priority queue is ...
0
1 z
2
3

1: Insert an element
2: Remove an element
3: Quit
Choose:
3


## Example 9.14, page no. 495¶

In [11]:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def insert(self, data):
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)

def inorder(self, tree):
solution = []
def recurse(node):
if not node:
return
recurse(node.left)
solution.append(node.data)
recurse(node.right)
recurse(tree)
return solution
def preorder(self, tree):
solution = []
def recurse(node):
if not node:
return
solution.append(node.data)
recurse(node.left)
recurse(node.right)
recurse(tree)
return solution
def postorder(self, tree):
solution = []
def recurse(node):
if not node:
return
recurse(node.left)
recurse(node.right)
solution.append(node.data)

recurse(tree)
return solution

print "Type numbers, one per line"
print "-999 for terminating"
num = int(raw_input())
tree = Node(num)
while num != -999:
num = int(raw_input())
if num == -999:
break
tree.insert(num)
choice = 0
while choice != 4:
print "\nType of TRAVERSAL ?"
print "1 - Inorder"
print "2 - Preorder"
print "3 - Postorder"
print "4 - STOP"
choice = int(raw_input())
if choice == 1:
print "INORDER traversal: "
sol = tree.inorder(tree)
for ele in sol:
print ele,
elif choice == 2:
print "PREORDER traversal: "
sol = tree.preorder(tree)
for ele in sol:
print ele,
elif choice == 3:
print "POSTORDER traversal: "
sol = tree.postorder(tree)
for ele in sol:
print ele,
else:
print "BYE"

Type numbers, one per line
-999 for terminating
4
1
10
9
3
6
8
5
2
4
-999

Type of TRAVERSAL ?
1 - Inorder
2 - Preorder
3 - Postorder
4 - STOP
1
INORDER traversal:
1 2 3 4 5 6 8 9 10
Type of TRAVERSAL ?
1 - Inorder
2 - Preorder
3 - Postorder
4 - STOP
2
PREORDER traversal:
4 1 3 2 10 9 6 5 8
Type of TRAVERSAL ?
1 - Inorder
2 - Preorder
3 - Postorder
4 - STOP
4
BYE