1. Aim: To write a program to implement the Linked List operations.

Algorithm:
Algorithm create( )
1. Start
2. head = null
3. size = 0
4. print "List created successfully"
5. return

Algorithm isEmpty()
1. Start
2. if size == 0 then
2.1 return true
3. else
3.1 return false

Algorithm count()
1. Start
2. print “Number of elements in the list are :” , size
3. return

Algorithm insert(int index, Object data)

1. start
2. if index < 0 or index >size
2.1 Print "Given position is invalid and data cannot be inserted"
3. else
3.1 node = new Node()
3.2 [Link] = data
3.3 if index == 0 then
3.3.1 [Link] = head
3.3.2 head = node
3.4 else
3.4.1 p = head
3.4.2 for(int i=0; i<=index-2;i++)
[Link] p = [Link]
3.4.3 q = [Link]
3.4.4 [Link] = node
3.4.5 [Link] = q
3.5 size = size+1
3.6 print data “ inserted into the list successfully”
4. return

Algorithm delete(int index)

1. Start
2. if size == 0 then
2.1 print "List is empty"
3. else if index < 0 or index >= size
3.1 print "Given index is invalid"
1
4. else
4.1 if index == 0 then
4.1.1 temp = head
4.1.2 head = [Link]
4.2 else
4.2.1 p = head
4.2.2 for ( int i=0; i<=index-2; i++)
[Link] p = [Link]
4.2.3 q = [Link]
4.2.4 temp = [Link]
4.2.5 [Link] = q
4.3 size = size -1
4.4 return [Link]
5. return

Algorithm traverse( )
1. start
2. if size == 0 then
2.1 print "List is empty, hence no elements to traverse"
3. else
3.1 print "The elements in the list are:"
3.2 p= head
3.3 while (p != null)
3.3.1 print [Link]
3.3.2 p = [Link]
4. return

Program:
import [Link].*;
interface LinearList
{ void create();
boolean isEmpty();
int count();
void insert(int index,Object data);
Object delete(int index);
void traverse();
}

class Node
{ Object info;
Node link;
}

class SLL implements LinearList

{ Node temp,node,head,p,q ;
int size;
public void create()
{ head = null;
size = 0;
2
[Link]("List created successfully");
}
public boolean isEmpty()
{ if( size == 0)
return true;
else
return false;
}
public int count()
{ return size;
}
public void insert(int index, Object data)
{ if (index < 0 || index >size)
[Link]("Given position is invalid and data cannot be inserted");
else
{ node = new Node();
[Link] = data;
if ( index == 0)
{ [Link] = head;
head = node;
}
else
{ p = head;
for(int i=0; i<=index-2;i++)
p = [Link];
q = [Link];
[Link] = node;
[Link] = q;
}
size = size+1;
[Link](data + “ inserted into the list successfully”);
}
}
public Object delete(int index)
{ if (size == 0)
[Link]("List is empty");
else if (index < 0 || index >= size)
[Link]("Given index is invalid");
else
{
if (index == 0)
{ temp = head;
head = [Link];
}
else
{ p = head;
for(int i=0; i<=index-2;i++)
p = [Link];
q = [Link];
3
temp = [Link];
[Link] = q;
}
size = size -1;
}
return [Link];
}
public void traverse()
{ if (size == 0)
[Link]("List is empty");
else
{ [Link]("The elements in the list are:");
p= head;
while(p != null)
{ [Link]("\t" + [Link]);
p = [Link];
}
}
}
}

class SLLDemo
{ public static void main(String args[])
{ SLL ob = new SLL();
[Link]();
[Link]("No. of elements in the list is :"+ [Link]());
[Link]("List is empty : " + [Link]());
[Link](0,10);
[Link](1,20);
[Link](2,30);
[Link]("No. of elements in the list is :"+ [Link]());
[Link]("List is empty : " + [Link]());
[Link]("The deleted element is : " + [Link](2) );
[Link]();
}
}

Output:
List created successfully
No. of elements in the list is : 0
List is empty: true
10 inserted into the list successfully
20 inserted into the list successfully
30 inserted into the list successfully
No. of elements in the list is: 3
List is empty: false
The deleted element is: 30
The elements in the list are:
10 20
4
2. Aim: To write a program to implement stack operations using an array.

Algorithm:
Algorithm create( )
1. Start
2. top = -1
3. stack = new Object[capacity]
4. print "Stack is Created”
5. return

A1lgorithm isEmpty()
1. Start
2. if top == -1 then
2.1 return true
3. else
3.1 return false

Algorithm count( )
1. Start
2. return top+1

Algorithm push( Object data)

1. Start
2. if top == capacity-1 then
2.1 print “The stack is already full"
3. else
3.1 top++
3.2 stack[top] = data
3.3 print data + " inserted successfully into the stack"
4. return

Algorithm pop( )
1. Start
2. if top == -1 then
2.1 print “The stack is empty"
3. else
3.1 removedElement = stack[top]
3.2 top--
4. return removedElement

Algorithm peek( )
1. Start
2. if top == -1 then
2.1 print “Stack is empty"
3. else
3.1 print "Element at top of the stack is : " + stack[top]
4. return

Algorithm traverse( )
5
1. start
2. if top==-1 then
2.1 print "The stack is empty"
3. else
3.1 print "Elements in the stack are: "
3.2 for (int i=top; i>=0; i--)
print stack[i]
4. return.

Program:
import [Link].*;
interface StackADT
{
void create();
boolean isEmpty();
int count();
void push(Object data);
Object pop();
void peek();
void traverse();
}

class StackArray implements StackADT

{
int top = -1;
Object stack[];
int capacity = 10;
public void create()
{ top = -1;
stack = new Object[capacity];
[Link]("\nStack is Created....");
}
public boolean isEmpty()
{
if(top == -1)
return true;
else
return false;
}
public int count()
{
return top+1;
}
public void push(Object data)
{ if(top == capacity-1)
[Link]("The stack is already full");
else
{
top++;
6
stack[top]=data;
[Link](data + " inserted successfully into the stack");
}
}
public Object pop()
{ Object removedElement = null;
if(top == -1)
[Link]("The stack is empty");
else
{
removedElement = stack[top];
top--;
}
return removedElement;
}
public void peek()
{ if(top == -1)
[Link]("Stack is empty");
else
[Link]("Element at top of the stack is : "+ stack[top]);
}
public void traverse()
{ if(top==-1)
[Link]("The stack is empty");
else
{
[Link]("Elements in the stack are: ");
for(int i=top;i>=0;i--)
[Link](stack[i]);
}
}
}

class StackDemo
{
public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
int ch;
StackArray ob = new StackArray();
do
{
[Link]("[Link] an empty stack");
[Link]("[Link] whether stack is empty or not");
[Link]("[Link] number of elements in the stack");
[Link]("[Link] an element into the stack");
[Link]("[Link] an element from the stack");
[Link]("[Link] element at top of the stack");
[Link]("[Link] elements in a stack");
[Link]("[Link]");
7
[Link]("\nEnter your choice:");
ch = [Link]();
switch(ch)
{ case 1 :[Link]();
break;
case 2 :[Link]("Stack is empty : " + [Link]());
break;
case 3 :[Link]("Number of elements in the stack are: "
+ [Link]() );
break;
case 4 :
[Link]("Enter the Element to insert into the
stack:");
int element = [Link]();
[Link](element);
break;
case 5 :[Link]("The element popped from stack is : " +
[Link]());
break;
case 6 :[Link]();
break;
case 7 :[Link]();
break;
}
}while(ch>=1 && ch<=7);
}
}

Output:
F:\>javac [Link]
F:\>java StackDemo
[Link] an empty stack
[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:1
Stack is Created....

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
8
[Link]
Enter your choice:4
Enter the Element to insert into the stack:
10
10 inserted successfully into the stack

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:4
Enter the Element to insert into the stack:
20
20 inserted successfully into the stack

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:7
Elements in the stack are:
20
10

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:8
F:\>

9
3. Aim: To write a program to implement stack operations using a single linked list.

Algorithm:
Algorithm create( )
1. Start
2. top = null
3. size = 0
4. print "Stack is Created”
5. return

A1lgorithm isEmpty()
1. Start
2. if size == 0 then
2.1 return true
3. else
3.1 return false

Algorithm count( )
1. Start
2. return size

Algorithm push( Object data)

1. Start
2. node = new Node( )
3. [Link] = data
4. [Link] = top
5. top = node
6. size++
7. print data + " inserted successfully into the stack"
8. return

Algorithm pop( )
1. Start
2. if size == 0 then
2.1 print “The stack is empty"
3. else
3.1 temp = top
3.2 top = [Link]
3.3 size--
4. return [Link]

Algorithm peek( )
1. Start
2. if size == 0 then
2.1 print “Stack is empty"
3. else
3.1 print "Element at top of the stack is : " + [Link]
4. return

10
Algorithm traverse( )
1. start
2. if size == 0 then
2.1 print "The stack is empty"
3. else
3.1 p = top
3.2 print "Elements in the stack are: "
3.3 while (p != null )
3.3.1 print [Link]
3.3.2 p = [Link]
4. return.

Program:
import [Link].*;
interface StackADT
{
void create();
boolean isEmpty();
int count();
void push(Object data);
Object pop();
void peek();
void traverse();
}
class Node
{
Object info;
Node link;
}
class StackSLL implements StackADT
{
Node top,node,temp,p;
int size=0;
public void create()
{ top = null;
size = 0;
[Link]("Stack is Created....");
}
public boolean isEmpty()
{
if(size == 0)
return true;
else
return false;
}
public int count()
{
return size;
}
11
public void push(Object data)
{ node = new Node();
[Link] = data;
[Link] = top;
top = node;
size++;
[Link](data + " inserted successfully into the stack");
}
public Object pop()
{
if(size == 0)
[Link]("The stack is empty");
else
{
temp = top;
top = [Link];
size--;
}
return [Link];
}
public void peek()
{ if(size == 0)
[Link]("Stack is empty");
else
[Link]("Element at top of the stack is : "+ [Link]);
}
public void traverse()
{ if(size==0)
[Link]("The stack is empty");
else
{
p = top;
[Link]("Elements in the stack are: ");
while ( p!= null)
{
[Link]([Link]);
p = [Link];
}
}
}
}

class StackDemo1
{
public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
int ch;
StackSLL ob = new StackSLL();
do
12
{
[Link]("[Link] an empty stack");
[Link]("[Link] whether stack is empty or not");
[Link]("[Link] number of elements in the stack");
[Link]("[Link] an element into the stack");
[Link]("[Link] an element from the stack");
[Link]("[Link] element at top of the stack");
[Link]("[Link] elements in a stack");
[Link]("[Link]");
[Link]("\nEnter your choice:");
ch = [Link]();
switch(ch)
{ case 1 :[Link]();
break;
case 2 :[Link]("Stack is empty : " + [Link]());
break;
case 3 :[Link]("Number of elements in the stack are: "
+ [Link]() );
break;
case 4 :
[Link]("Enter the Element to insert into the
stack:");
int element = [Link]();
[Link](element);
break;
case 5 :[Link]("The element popped from stack is : " +
[Link]());
break;
case 6 :[Link]();
break;
case 7 :[Link]();
break;
}
}while(ch>=1 && ch<=7);
}
}

Output:
F:\>javac [Link]
F:\>java StackDemo1
[Link] an empty stack
[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:1
13
Stack is Created....

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:4
Enter the Element to insert into the stack:
10
10 inserted successfully into the stack

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:4
Enter the Element to insert into the stack:
20
20 inserted successfully into the stack

[Link] an empty stack

[Link] whether stack is empty or not
[Link] number of elements in the stack
[Link] an element into the stack
[Link] an element from the stack
[Link] element at top of the stack
[Link] elements in a stack
[Link]
Enter your choice:7
Elements in the stack are:
20
10

14
4. Aim: To write a program to implement the Queue operations using an array.
Algorithm:
Algorithm create()
1. Start
2. rear = -1
3. front = 0
4. queue = new Object[capacity]
5. print "Linear Queue Created Successfully"
6. return

Algorithm isEmpty()
1. start
2. if rear == -1 then
2.1 return true
3. else
3.1 return false

Algorithm count()
1. start
2. return size

Algorithm insert(Object data)

1. start
2. if size == capacity-1 then
2.1 print "The linear queue is already full"
3. else
3.1 rear++
3.2 queue[rear]=data
3.3 print data , " inserted successfully into the linear queue"
4. return

Algorithm delete()
1. start
2. if rear == -1 then
2.1 print "The linear queue is empty"
3. else
3.1 removedElement = queue[front]
3.2 (for i= front; i<rear; i++)
3.2.1 queue[i] =queue[i+1];
3.3 rear--;
4. return removedElement;

Algorithm frontQueue()
1. start
2. if rear == -1 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Element at front of the queue is : ", queue[front]
4. return
15
Algorithm rearQueue()
1. start
2. if rear == -1 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Element at front of the queue is : ", queue[rear]
4. return

Algorithm traverse()
1. start
2. if rear == -1 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Elements in the linear queue are: "
3.2 for(int i=front;i<=rear;i++)
3.2.1 print queue[i]
4. return

Program:
import [Link].*;
interface QueueADT
{ void create();
boolean isEmpty();
int count();
void insert(Object data);
Object delete();
void frontQueue();
void rearQueue();
void traverse();
}

class QueueArray implements QueueADT

{ int rear = -1, front = 0;
Object queue[];
int capacity = 10;
public void create()
{ rear = -1;
front = 0;
queue = new Object[capacity];
[Link]("\nLinear Queue Created Successfully");
}
public boolean isEmpty()
{ if(rear == -1)
return true;
else
return false;
}
public int count()
{ return rear+1;
16
}
public void insert(Object data)
{ if(rear == capacity-1)
[Link]("The linear queue is already full");
else
{ rear++;
queue[rear]=data;
[Link](data + " inserted successfully into the linear queue");
}
}
public Object delete()
{ Object removedElement = null;
if(rear == -1)
[Link]("The linear queue is empty");
else
{ removedElement = queue[front];
for(int i=front;i<rear;i++)
queue[i] = queue[i+1];
rear--;
}
return removedElement;
}
public void frontQueue()
{ if(rear == -1)
[Link]("Linear Queue is empty");
else
[Link]("Element at front of the queue is : "+ queue[front]);
}
public void rearQueue()
{ if(rear == -1)
[Link]("Linear Queue is empty");
else
[Link]("Element at rear of the queue is : "+ queue[rear]);
}
public void traverse()
{ if(rear==-1)
[Link]("The Linear queue is empty");
else
{
[Link]("Elements in the linear queue are: ");
for(int i=front;i<=rear;i++)
[Link](queue[i]);
}
}
}

class QueueDemo
{ public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
17
int ch;
QueueArray ob = new QueueArray();
do
{ [Link]("[Link] an empty linear queue");
[Link]("[Link] whether linear queue is empty or not");
[Link]("[Link] number of elements in the linear
queue");
[Link]("[Link] an element into the linear queue");
[Link]("[Link] an element from the linear queue");
[Link]("[Link] element at front of the queue");
[Link]("[Link] element at rear of the queue");
[Link]("[Link] elements in a linear queue");
[Link]("[Link]");
[Link]("\nEnter your choice:");
ch = [Link]();
switch(ch)
{ case 1 :[Link]();
break;
case 2 :[Link]("Linear queue is empty : " +
[Link]());
break;
case 3 :[Link]("Number of elements in the Linear
queue are: " + [Link]() );
break;
case 4 :
[Link]("Enter the Element to insert into the
linear queue:");
int element = [Link]();
[Link](element);
break;
case 5 :[Link]("The element deleted from linear queue
is : " + [Link]());
break;
case 6 :[Link]();
break;
case 7: [Link]();
break;
case 8 :[Link]();
break;
}
}while(ch>=1 && ch<=8);
}
}

18
5. Aim: To write a program to implement the Queue operations using singly linked list.

Algorithm:
Algorithm create()
1. Start
2. rear = null
3. front = null
4. size = 0
5. print "Linear Queue Created Successfully"
6. return

Algorithm isEmpty()
1. start
2. if size == 0 then
2.1 return true
3. else
3.1 return false
Algorithm count()
1. start
2. return size

Algorithm insert(Object data)

1. start
2. node = new Node()
3. [Link] = data
4. [Link] = null
5. if size == 0 then
5.1 front = node
5.2 rear = node
6. else
6.1 [Link] = node
6.2 rear = node
7. size++;
8. print data, " inserted successfully into the linear queue"

Algorithm delete()
1. start
2. if size == 0 then
2.1 print "The linear queue is empty"
3. else
3.1 temp = front
3.2 if size == 1 then
3.2.1 front = null
3.2.2 rear = null
3.3 else
3.3.1 front = [Link];
4. size--;
5. return [Link]

19
Algorithm frontQueue()
1. start
2. if size == 0 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Element at front of the queue is : ", [Link]
4. return

Algorithm rearQueue()
1. start
2. if size == 0 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Element at rear of the queue is : ", [Link]
4. return

Algorithm traverse()
1. start
2. if size == 0 then
2.1 print "Linear Queue is empty"
3. else
3.1 print "Elements in the linear queue are: "
3.2 p = front
3.3 while p!= null
3.3.1 print [Link]
3.3.2 p = [Link]
4. return

Program:
import [Link].*;
interface QueueADT
{ void create();
boolean isEmpty();
int count();
void insert(Object data);
Object delete();
void frontQueue();
void rearQueue();
void traverse();
}
class Node
{ Object info;
Node link;
}
class QueueSLL implements QueueADT
{ Node node, temp, p, rear, front;
int size = 0;
public void create()
{ rear = null;
20
front = null;
size = 0;
[Link]("\nLinear Queue Created Successfully");
}
public boolean isEmpty()
{ if(size == 0)
return true;
else
return false;
}
public int count()
{ return size;
}
public void insert(Object data)
{ node = new Node();
[Link] = data;
[Link] = null;
if (size == 0)
{ front = node;
rear = node;
}
else
{
[Link] = node;
rear = node;
}
size++;
[Link](data + " inserted successfully into the linear queue");
}
}
public Object delete()
{ if(size == 0)
[Link]("The linear queue is empty");
else
{ temp = front;
if( size == 1)
{ front = null;
rear = null;
}
else
{ front = [Link];
}
size--;
}
return [Link];
}
public void front_queue()
{ if(size == 0)
[Link]("Linear Queue is empty");
21
else
[Link]("Element at front of the queue is : "+ [Link]);
}
public void rear_queue()
{ if(size == 0)
[Link]("Linear Queue is empty");
else
[Link]("Element at rear of the queue is : "+ [Link]);
}
public void traverse()
{ if(size == 0)
[Link]("The Linear queue is empty");
else
{ p = front;
[Link]("Elements in the linear queue are: ");
while ( p!= null)
{
[Link]([Link]);
p = [Link];
}
}
}
}

class QueueDemo1
{
public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
int ch;
QueueSLL ob = new QueueSLL();
do
{ [Link]("[Link] an empty linear queue");
[Link]("[Link] whether linear queue is empty or not");
[Link]("[Link] number of elements in the linear
queue");
[Link]("[Link] an element into the linear queue");
[Link]("[Link] an element from the linear queue");
[Link]("[Link] element at front of the queue");
[Link]("[Link] element at rear of the queue");
[Link]("[Link] elements in a linear queue");
[Link]("[Link]");
[Link]("\nEnter your choice:");
ch = [Link]();
switch(ch)
{ case 1 :[Link]();
break;
case 2 :[Link]("Linear queue is empty : " +
[Link]());
break;
22
case 3 :[Link]("Number of elements in the Linear
queue are: " + [Link]() );
break;
case 4 :
[Link]("Enter the Element to insert into the
linear queue:");
int element = [Link]();
[Link](element);
break;
case 5 :[Link]("The element deleted from linear queue
is : " + [Link]());
break;
case 6 :ob.front_queue();
break;
case 7: ob.rear_queue();
break;
case 8 :[Link]();
break;
}
}while(ch>=1 && ch<=8);
}
}

23
6. Aim: To write a program to implement Double Ended Queue operations using a doubly
linked list.

Algorithm:
Algorithm create()
1. Start
2. rear = null
3. front = null
4. size = 0
5. print "Deque Created Successfully"
6. return

Algorithm isEmpty()
1. start
2. if size == 0 then
2.1 return true
3. else
3.1return false

Algorithm count()
1. start
2. return size

Algorithm frontInsert(Object data)

1. start
2. node = new Node()
3. [Link] = data
4. [Link] = null
5. [Link] = null
6. if size == 0 then
6.1 front = node
6.2 rear = node
7. else
7.1 [Link] = front
7.2 [Link] = node
7.3 front = node
8. size++
9. print data + " inserted successfully into the deque"
10. return

Algorithm rearInsert(Object data)

1. start
2. node = new Node()
3. [Link] = data
4. [Link] = null
5. [Link] = null
6. if size == 0 then
6.1 front = node
6.2 rear = node
24
7. else
7.1 [Link] = node
7.2 [Link] = rear
7.3 rear = node
8. size++
9. print data + " inserted successfully into the deque"
10. return

Algorithm frontDelete( )
1. start
2. if size == 0 then
2.1 print "The deque is empty"
3. else
3.1 temp = front
3.2 if size == 1 then
3.2.1 front = null
3.2.2 rear = null
3.3 else
3.3.1 front = [Link]
3.3.2 [Link] = null
3.4 size--;
4. return [Link]

Algorithm rearDelete( )
1. start
2. if size == 0 then
2.1 print "The deque is empty"
3. else
3.1 temp = front
3.2 if size == 1 then
3.2.1 front = null
3.2.2 rear = null
3.3 else
3.3.1 rear = [Link]
3.3.2 [Link] = null
3.4 size--;
4. return [Link]

Algorithm frontQueue()
1. start
2. if size == 0 then
2.1 print "Deque is empty"
3. else
3.1 print "Element at front of the queue is : ", [Link]
4. return

Algorithm rearQueue()
1. start
2. if size == 0 then
25
2.1 print "Deque is empty"
3. else
3.1 print "Element at rear of the queue is : ", [Link]
4. return

Algorithm traverse()
1. start
2. if size == 0 then
2.1 print "Deque is empty"
3. else
3.1 print "Elements in the Deque are: "
3.2 p = front
3.3 while p!= null do
3.3.1 print [Link]
3.3.2 p = [Link]
4. return

Program:
import [Link].*;
interface DequeADT
{ void create( );
boolean isEmpty( );
int count( );
void frontInsert(Object data);
void rearInsert(Object data);
Object frontDelete( );
Object rearDelete( );
void frontDeque( );
void rearDeque();
void traverse( );
}
class Node
{ Object info;
Node left, right;
}
class DequeDLL implements DequeADT
{ Node node, temp, p, rear, front;
int size = 0;
public void create()
{ rear = null;
front = null;
size = 0;
[Link]("\nDeque Created Successfully");
}
public boolean isEmpty()
{ if(size == 0)
return true;
else
26
return false;
}
public int count()
{ return size;
}
public void frontInsert(Object data)
{ node = new Node();
[Link] = data;
[Link] = null;
[Link] = null;
if (size == 0)
{ front = node;
rear = node;
}
else
{
[Link] = front;
[Link] = node;
front = node;
}
size++;
[Link](data + " inserted successfully into the deque");
}
public void rearInsert(Object data)
{ node = new Node();
[Link] = data;
[Link] = null;
[Link] = null;
if (size == 0)
{ front = node;
rear = node;
}
else
{
[Link] = node;
[Link] = rear;
rear = node;
}
size++;
[Link](data + " inserted successfully into the deque");
}
public Object frontDelete()
{ if(size == 0)
[Link]("The deque is empty");
else
{ temp = front;
if( size == 1)
{ front = null;
rear = null;
27
}
else
{ front = [Link];
[Link] = null;
}
size--;
}
return [Link];
}
public Object rearDelete()
{ if(size == 0)
[Link]("The deque is empty");
else
{ temp = rear;
if( size == 1)
{ front = null;
rear = null;
}
else
{ rear = [Link];
[Link] = null;
}
size--;
}
return [Link];
}
public void frontDeque()
{ if(size == 0)
[Link]("Deque is empty");
else
[Link]("Element at front of the queue is : "+ [Link]);
}
public void rearDeque()
{ if(size == 0)
[Link]("Deque is empty");
else
[Link]("Element at rear of the queue is : "+ [Link]);
}
public void traverse()
{ if(size == 0)
[Link]("The Deque is empty");
else
{ p = front;
[Link]("Elements in the deque are: ");
while ( p!= null)
{
[Link]([Link]);
p = [Link];
}
28
}
}
}
class DequeDemo2
{
public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
int ch;
DequeDLL ob = new DequeDLL( );
do
{ [Link]("[Link] an empty deque");
[Link]("[Link] whether deque is empty or not");
[Link]("[Link] number of elements in the deque");
[Link]("[Link] an element at front of the deque");
[Link]("[Link] an element at rear of the deque");
[Link]("[Link] an element at front of the deque");
[Link]("[Link] an element at rear of the deque");
[Link]("[Link] element at front of the deque");
[Link]("[Link] element at rear of the deque");
[Link]("[Link] elements in a deque");
[Link]("[Link]");
[Link]("\nEnter your choice:");
ch = [Link]();
switch(ch)
{ case 1 :[Link]();
break;
case 2 :[Link]("Deque is empty : " +
[Link]());
break;
case 3 :[Link]("Number of elements in the Deque are deque are: " + [Link]() );
break;
case 4 :
[Link]("Enter the Element to insert into the
deque:");
int element = [Link]();
[Link](element);
break;
case 5 :
[Link]("Enter the Element to insert into the
deque:");
element = [Link]();
[Link](element);
break;
case 6 :[Link]("The element deleted from front of the
deque is : " + [Link]());
break;
case 7 :[Link]("The element deleted from rear of the
deque is : " + [Link]());
break;
29
case 8 :[Link]();
break;
case 9: [Link]();
break;
case 10 :[Link]();
break;
}
}while(ch>=1 && ch<=10);
}
}

30
7. a) Aim: To write a java program to convert the given infix expression into postfix expression.

Infix to Postfix conversion Algorithm:

1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in
the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-
equal to the precedence of the operator residing on the top of the stack. Push the scanned
operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.

Program:
import [Link];
class Test
{ static int Prec(char ch)
{ switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static String infixToPostfix(String exp)
{
String result = new String("");
Stack<Character> stack = new Stack<>();
for (int i = 0; i<[Link](); ++i)
{
char c = [Link](i);
if ([Link](c))
result += c;
else if (c == '(')
[Link](c);
else if (c == ')')
{
while (![Link]() && [Link]() != '(')
result += [Link]();

31
if (![Link]() && [Link]() != '(')
return "Invalid Expression";
else
[Link]();
}
else
{
while (![Link]() && Prec(c) <= Prec([Link]()))
result += [Link]();
[Link](c);
}
}
while (![Link]())
result += [Link]();
return result;
}
public static void main(String[] args)
{
String exp = "a+b*(c^d-e)^(f+g*h)-i";
[Link](infixToPostfix(exp));
}
}

32
7. b) Aim: To write a java program to evaluate the given postfix expression.

Postfix Evaluation Algorithm:

Following is algorithm for evaluation postfix expressions.
1) Create a stack to store operands (or values).
2) Scan the given expression and do following for every scanned element.
…..a) If the element is a number, push it into the stack
…..b) If the element is a operator, pop operands for the operator from stack. Evaluate the
operator and push the result back to the stack
3) When the expression is ended, the number in the stack is the final answer

Program:
import [Link];
public class Test
{
static int evaluatePostfix(String exp)
{
Stack<Integer> stack=new Stack<>();
for(int i=0;i<[Link]();i++)
{
char c=[Link](i);
if([Link](c))
[Link](c - '0');
else
{
int val1 = [Link]();
int val2 = [Link]();
switch(c)
{
case '+':
[Link](val2+val1);
break;
case '-':
[Link](val2- val1);
break;
case '/':
[Link](val2/val1);
break;
case '*':
[Link](val2*val1);
break;
}
}
}
return [Link]();
}
public static void main(String[] args)
{
String exp="231*+9-";
33
[Link](evaluatePostfix(exp));
}
}

34
8. Aim: To write a program on Binary Search Tree operations (insertion, deletion and
traversals).

Algorithm:

Algorithm insert_BST(data)
1. start
2. node =new Node( ) // allocate memory dynamically for new node
3. [Link] = data
4. [Link] = null
5. [Link] = null
6. if (root = = null) then
6.1 root = node
7. else
7.1 cur = root
7.2 while (cur != null) do
7.2.1 par = cur
7.2.2 if (data <= [Link]) then
[Link] cur = [Link]
7.2.3 else
[Link] cur = [Link]
7.4 if(data <= [Link])
7.4.1 [Link] = node
7.5 else
7.5.1 [Link] = node
8. print "The element inserted into BST successfully"
9. return

Algorithm delete_BST(data)
1. start
2. if (root == null) then
2.1 print "Tree is empty, hence deletion cannot be performed"
3. else
3.1 cur = root
3.2 while(cur != null && [Link] !=data) do
3.2.1 par = cur
3.2.2 if (data <= ([Link]) ) then
[Link] cur = [Link]
3.2.3 else
[Link] cur = [Link]
3.3 if (cur == null) then
3.3.1 print "Given element is not found in BST and hence it cannot be deleted"
3.4 else
3.4.1 if ( cur == root ) then
[Link] if ([Link] == null && [Link] == null) then
[Link].1 root = null
[Link] else if ([Link] != null && [Link] == null) then
[Link].1 root = [Link]
[Link] else if ([Link] == null && [Link] != null) then
35
[Link].1 root = [Link]
[Link] else
[Link].1 temp = ([Link])
[Link].2 root = [Link]
[Link].3 cur = root
[Link].4 while ( [Link] != null)
cur = [Link]
[Link].5 [Link] = temp
3.4.2 else
[Link] if ( [Link] == null && [Link] == null) then
[Link].1 if( ([Link]) <= ([Link])) then
[Link] = null
[Link].2 else
[Link] = null
[Link] else if ( [Link] != null && [Link] == null) then
[Link].1 if( ([Link]) <= ([Link])) then
[Link] = [Link]
[Link].2 else
[Link] = [Link]
[Link] else if ( [Link] == null && [Link] != null) then
[Link].1 if( ([Link]) <= ([Link])) then
[Link] = [Link];
[Link].2 else
[Link] = [Link];
[Link] else
[Link].1 temp = ([Link])
[Link].2 if( ([Link]) <= ([Link])) then
[Link] = [Link]
[Link].3 else
[Link] = [Link]
[Link].4 cur = ([Link])
[Link].5 while( [Link] != null) do
cur = [Link]
[Link].6 [Link] = temp
3.5 print "The element deleted from BST successfully"
4. return

Algorithm inorder( root )

1. start
2. if (root!=null) then
2.1 call inorder ([Link])
2.2 print [Link]
2.3 call inorder ([Link])
3. return.

Algorithm preorder( root )

1. start
2. if (root!=null) then
2.1 print [Link]
36
2.2 call preorder ([Link])
2.3 call preorder ([Link])
3. return.

Algorithm postorder( root )

1. start
2. if (root!=null) then
2.1 call postorder ([Link])
2.2 call postorder ([Link])
2.3 print [Link]
3. return.

Program:
import [Link].*;
class Node
{ int info;
Node left, right;
}
interface BSTADT
{
void insert_BST(int data);
void delete_BST(int data);
void inorder(Node root);
void preorder(Node root);
void postorder(Node root);
}
class BST implements BSTADT
{
Node root=null, par, cur, node;
public void insert_BST(int data)
{
node=new Node( );
[Link]=data;
[Link]=null;
[Link]=null;
if(root == null)
root = node;
else
{
cur = root;
while(cur !=null)
{
par=cur;
if(data <= [Link])
cur=[Link];
else
cur=[Link];
}
if(data <= [Link])
37
[Link]=node;
else
[Link]=node;
}
[Link]("The element inserted into BST successfully");
}
public void delete_BST(int data)
{
Node temp;
if (root == null)
{
[Link]("Tree is empty, hence deletion cannot be performed");
}
else
{
cur = root;
while(cur != null && [Link] !=data)
{
par = cur;
if (data <= ([Link]) )
cur = [Link];
else
cur = [Link];
}
if (cur == null)
{
[Link]("\nGiven element is not found in BST and
hence it cannot be deleted");
}
else
{
if ( cur == root )
{
if ([Link] == null && [Link] == null)
root = null;
else if ([Link] != null && [Link] == null)
root = [Link];
else if ([Link] == null && [Link] != null)
root = [Link];
else
{
temp = ([Link]);
root = [Link];
cur = root;
while ( [Link] != null)
cur = [Link];
[Link] = temp;
}
}
38
else
{
if ( [Link] == null && [Link] == null)
{
if( ([Link]) <= ([Link]))
[Link] = null;
else
[Link] = null;
}
else if ( [Link] != null && [Link] == null)
{
if( ([Link]) <= ([Link]))
[Link] = [Link];
else
[Link] = [Link];
}
else if ( [Link] == null && [Link] != null)
{
if( ([Link]) <= ([Link]))
[Link] = [Link];
else
[Link] = [Link];
}
else
{
temp = ([Link]);
if( ([Link]) <= ([Link]))
[Link] = [Link];
else
[Link] = [Link];
cur = ([Link]);
while( [Link] != null)
cur = [Link];
[Link] = temp;
}
}
[Link]("The element deleted from BST successfully");
}
}
}
public void inorder(Node root)
{ if(root!=null)
{
inorder([Link]);
[Link]([Link]);
inorder([Link]);
}
}
public void preorder(Node root)
39
{ if(root!=null)
{
[Link]([Link]);
preorder([Link]);
preorder([Link]);
}
}
public void postorder(Node root)
{ if(root!=null)
{
postorder([Link]);
postorder([Link]);
[Link]([Link]);
}
}
}
class BSTDemo
{
public static void main(String args[])
{
int choice, element;
Scanner sc = new Scanner([Link]);
BST ob = new BST( );
do
{
[Link]("\n\t\tBinary Search Tree operations");
[Link]("[Link] an element into BST");
[Link]("[Link] an element from BST");
[Link]("[Link] Traversal");
[Link]("[Link] Traversal");
[Link]("[Link] Traversal");
[Link]("[Link]");
[Link]("Enter your choice : ");
choice = [Link]();
switch(choice)
{ case 1 : [Link]("Enter element to insert into BST : ");
element = [Link]();
ob.insert_BST(element);
break;
case 2 : [Link]("Enter element to delete from BST : ");
element = [Link]();
ob.delete_BST(element);
break;
case 3 : [Link]([Link]);
break;
case 4 : [Link]([Link]);
break;
case 5 : [Link]([Link]);
break;
40
default : [Link]("Program Terminated");
}
}while(choice>=1 && choice<=5);
}
}

41
9. a) Aim: To write a program to search an element in a given list using Linear Search
Technique.

Algorithm linearSearch( ):
1. Start
2. Repeat for i=0 to n-1 step by 1 do
2.1 if (key == a[i]) then
2.1.1 return (i)
3. return (-1)

Program:
import [Link].*;
class LinearSearchDemo
{ static int a[ ], key, n, loc ;
static int linearSearch()
{ for( int i=0; i<n; i++)
{
if(key == a[i])
return (i);
}
return (-1);
}
public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements : ");
n = [Link]( );
a = new int[n];
[Link]("Enter elements : ");
for(int i=0;i<n;i++)
a[i] = [Link]();
[Link]("Enter key element to search : ");
key = [Link]();
loc = linearSearch();
if( loc == -1 )
[Link](key + " is not found in the list");
else
[Link](key + " is found in the list at location " + (loc+1) );
}
}

42
9. b) Aim: To write a program to search an element in a given list using Binary Search
Technique.

Algorithm binarySearch(int low, int high):

1. Start
2. if( low > high )
2.1 return (-1)
3. mid = (low + high)/2
4. if( key < a[mid] ) then
4.1 return binarySearch(low, mid-1)
5. else if( key > a[mid]) then
5.1 return binarySearch(mid+1, high)
6. else
6.1 return mid

Program:
import [Link].*;
class BinarySearchDemo
{ static int a[ ], key, n, loc;
static int binarySearch(int low, int high)
{
if( low > high )
return (-1);
int mid = (low + high)/2;
if( key < a[mid] )
return binarySearch(low, mid-1);
else if( key > a[mid])
return binarySearch(mid+1, high);
else
return mid;
}
public static void main(String args[])
{
Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements : ");
n = [Link]( );
a = new int[n];
[Link]("Enter elements : ");
for(int i=0;i<n;i++)
a[i] = [Link]();
[Link]("Enter key element to search:");
key = [Link]();
loc = binarySearch(0, n-1);
if( loc== -1 )
[Link](key + " is not found in the list");
else
[Link](key + " is found in the list " + (loc+1) );
}
}
43
10. Aim: To write a program to sort the given elements in ascending order using quick sort.

Algorithm quick_sort(int a[],int lb,int ub)

1. start
2. flag = true
3. if (lb<ub) then
3.1 key=a[lb]
3.2 i=lb
3.3 j=ub+1
3.4 while(flag)
3.4.1 i=i+1
3.4.2 while(a[i]<key&&i<ub) do
[Link] i=i+1
3.4.3 j--
3.4.4 while((a[j]>key)&&(j>lb)) do
[Link] j=j-1
3.4.5 if(i<j)
[Link] temp=a[i]
[Link] a[i]=a[j]
[Link] a[j]=temp
3.4.6 else
[Link] flag=false
3.5 temp=a[lb]
3.6 a[lb]=a[j]
3.7 a[j]=temp
3.8 quick_sort(a,lb,j-1)
3.9 quick_sort(a,j+1,ub)
4. return

Program:
import [Link].*;
class QSort
{
void quick_sort(int a[],int lb,int ub)
{
int i,j,key,temp;
boolean flag = true;
if(lb<ub)
{
key=a[lb];
i=lb;
j=ub+1;
while(flag)
{
i=i+1;
while(a[i]<key&&i<ub)
i=i+1;
j--;
while((a[j]>key)&&(j>lb))
44
{
j=j-1;
}
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
{
flag=false;
}
}
temp=a[lb];
a[lb]=a[j];
a[j]=temp;
quick_sort(a,lb,j-1);
quick_sort(a,j+1,ub);
}
}
}
class QSDemo
{ public static void main(String args[])
{
Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements : ");
int n = [Link]();
int arr[ ] = new int[n];
[Link]("Enter elements : ");
for(int i=0;i<n;i++)
arr[i] = [Link]();
QSort ob = new QSort();
ob.quick_sort(arr,0,n-1);
[Link]("The sorted elements are:");
for(int i=0;i<n;i++)
[Link]( arr[i]);
}
}

45
11. Aim: To write a program to sort the given elements in ascending order using merge sort.

Algorithm merge_sort(int a[],int start,int finish):

1. Start
2. size=finish-start+1;
3. if (size > 1) then
3.1 mid=(start+finish)/2
3.2 call merge_sort(a,start,mid)
3.3 call merge_sort(a,mid+1,finish)
3.4 call merge(a,start,mid+1,finish)
4. return

Algorithm merge(int a[],int s,int m,int f)

1. Start
2. i =s, j=m, k=1
3. while(i<m && j<=f) do
3.1 if(a[i]<=a[j]) then
3.1.1 temp[k]=a[i]
3.1.2 i=i+1
3.1.3 k=k+1
3.2 else
3.2.1 temp[k]=a[j]
3.2.2 j=j+1
3.2.3 k=k+1
4. if(i>=m) then
4.1 while(j<=f) do
4.1.1 temp[k]=a[j]
4.1.2 j=j+1
4.1.3 k=k+1
5. else
5.1while(i<m) do
5.1.1 temp[k]=a[i]
5.1.2 i=i+1
5.1.3 k=k+1
6. for i=1to k-1 by step 1 do
6.1 a[s+i-1]=temp[i]
7. return

Program:
import [Link].*;
class MSort
{ void merge_sort(int a[],int start,int finish)
{ int size,mid;
size=finish-start+1;
if(size>1)
{
mid=(start+finish)/2;
merge_sort(a,start,mid);
merge_sort(a,mid+1,finish);
46
merge(a,start,mid+1,finish);
}
}
void merge(int a[],int s,int m,int f)
{ int i,j,k;
I nt temp[] = new int [20];
i=s;
j=m;
k=1;
while(i<m&&j<=f)
{
if(a[i]<=a[j])
{
temp[k]=a[i];
i=i+1;
k=k+1;
}
else
{
temp[k]=a[j];
j=j+1;
k=k+1;
}
}
if(i>=m)
{
while(j<=f)
{
temp[k]=a[j];
j=j+1;
k=k+1;
}
}
else
{
while(i<m)
{
temp[k]=a[i];
i=i+1;
k=k+1;
}
}
for(i=1;i<=k-1;i++)
{
a[s+i-1]=temp[i];
}
}
}
class MSDemo
47
{ public static void main(String args[])
{ Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements : ");
int n = [Link]();
int arr[ ] = new int[n];
[Link]("Enter elements : ");
for(int i=0;i<n;i++)
arr[i] = [Link]();
MSort ob = new MSort();
ob.merge_sort(arr,0,n-1);
[Link]("The sorted elements are:");
for(int i=0;i<n;i++)
[Link]( arr[i]);
}
}

48