Data Structures Module-IV
Module-IV
1)
Implementation of Queue Operations using
i) Arrays ii) Linked List
2)
Implementation of Circular Queue Operations using
i) Arrays ii) Linked List
3)
Implement Dequeue using Linked List.
1)
a) Implementation of Queue Operations using Arrays.
#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
void enqueue();
void dequeue();
void display();
int
queue[SIZE],front=-1,rear=-1,ele;
int main()
{
int ch;
while(1)
{
printf("\n menu");
printf("\n 1.enqueue\n 2.dequeue\n
3.display");
printf("\n enter ur choice");
scanf("%d",&ch);
switch(ch)
{
case 1:enqueue();
break;
case 2:dequeue();
break;
case 3:display();
break;
default:exit(1);
}
}
return 0;
}
void enqueue()
{
if(rear==SIZE-1)
printf("queue is empty");
else
{
rear++;
printf("\n enter an element to be
inserted into the queue ");
scanf("%d",&ele);
queue[rear]=ele;
if(front==-1)
front=0;
}
}
void dequeue()
{
if(front==-1&&rear==-1)
printf("\n queue is empty");
else if(front==rear)
{
printf("\n deleted element from
the queue is %d",queue[front]);
front=-1;
rear=-1;
else
{
ele=queue[front];
printf("\n delete node from the
queue is %d",ele);
front++;
}
}
void display()
{
if(front==-1&&rear==-1)
printf("\n the elements of queue
are\n");
for(i=front;i<=rear;i++)
{
printf("%d\t",queue[i]);
}
}
Output:
menu
1.enqueue
2.dequeue
3.display
enter ur choice1
1.enqueue
2.dequeue
3.display
enter ur choice1
1.enqueue
2.dequeue
3.display
enter ur choice1
menu
1.enqueue
2.dequeue
3.display
enter ur choice3
6 12 18
menu
1.enqueue
2.dequeue
3.display
enter ur choice2
delete node from the queue is 6
menu
1.enqueue
2.dequeue
3.display
enter ur choice2
delete node from the queue is 12
menu
1.enqueue
2.dequeue
3.display
enter ur choice3
18
menu
1.enqueue
2.dequeue
3.display
enter ur choice4
Process exited after 80.37
seconds with return value 1
Press any key to continue
. . .
1)
b) Implementation of Queue Operations using Linked List.
#include <stdio.h>
#include <stdlib.h>
void enqueue( );
void dequeue( );
void display( );
int value;
struct node
{
int data;
struct node *next;
}*front,*rear,*new,*temp;
int main()
{
int ch;
while(1)
{
printf("\nMENU\n");
printf("\n1.enqueue\n2.dequeue\n3.display");
printf("\nenter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:enqueue( );
break;
case 2:dequeue( );
break;
case 3:display( );
break;
default:exit(1 );
}
}
return 0;
}
{
new=(struct node *)malloc(sizeof(struct node));
printf("\nenter an element to be inserted into queue\n");
scanf("%d",&value);
new->data=value;
new->next=NULL;
if(rear==NULL)
{
front=rear=new;
}
else
{
rear->next=new;
rear=new;
}
}
void dequeue( )
printf("\nQueue is empty");
}
else
{
temp=front;
printf("\nDeleted element from the queue is %d",front->data);
front=front->next;
temp->next=NULL;
}
}
void display( )
{
if(front==NULL
)
{
printf("\nQueue
is empty");
}
else
{
printf("\nThe elements of queue are\n");
temp=front;
while(temp!=NULL)
{
printf("%d\t",temp->data);
temp=temp->next;
}
}
}
Output:-
MENU
1.enqueue
2.dequeue
3.display
enter your choice1
enter an element to be inserted into queue
5
MENU
1.enqueue
2.dequeue
3.display
enter your choice1
enter an element to be inserted into queue
10
MENU
1.enqueue
2.dequeue
3.display
enter your choice1
enter an element to be inserted into queue
15
MENU
1.enqueue
2.dequeue
3.display
enter your choice3
The elements of queue are
5 10 15
MENU
1.enqueue
2.dequeue
3.display
enter your choice2
Deleted element from the queue is 5
MENU
1.enqueue
2.dequeue
3.display
enter your choice3
The elements of queue are
10 15
MENU
1.enqueue
2.dequeue
3.display
enter your choice4
--------------------------------
Process exited after 59.49 seconds with return value 1
Press any key to continue . . .
#include<stdio.h>
#define capacity 6
int queue[capacity];
int front = -1, rear = -1;
// Here we check if the Circular queue is full or
not
int checkFull ()
{
if
((front == rear + 1) || (front == 0 && rear == capacity - 1))
{
return 1;
}
return 0;
}
// Here we check if the Circular queue is empty
or not
int checkEmpty ()
{
if (front
== -1)
{
return 1;
}
return 0;
}
// Addtion in the Circular Queue
void enqueue (int value)
{
if
(checkFull ())
printf ("Overflow condition\n");
else
{
if
(front == -1)
front = 0;
rear
= (rear + 1) % capacity;
queue[rear] = value;
printf ("%d was enqueued to circular queue\n", value);
}
}
// Removal from the Circular Queue
int dequeue ()
{
int
variable;
if
(checkEmpty ())
{
printf ("Underflow condition\n");
return -1;
}
else
{
variable = queue[front];
if
(front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % capacity;
}
printf ("%d was dequeued from circular queue\n", variable);
return 1;
}
}
// Display the queue
void print ()
{
int i;
if
(checkEmpty ())
printf
("Nothing to dequeue\n");
else
{
printf ("\nThe queue looks like: \n");
for
(i = front; i != rear; i = (i + 1) % capacity)
{
printf ("%d ", queue[i]);
}
printf ("%d \n\n", queue[i]);
}
}
int main ()
{
// Not
possible as the Circular queue is empty
dequeue ();
enqueue
(15);
enqueue
(20);
enqueue
(25);
enqueue
(30);
enqueue (35);
print ();
dequeue ();
dequeue ();
print ();
enqueue
(40);
enqueue
(45);
enqueue
(50);
enqueue
(55); //Overflow
condition
print ();
return 0;
}
Output:
Underflow condition
15 was enqueued to circular queue
20 was enqueued to circular queue
25 was enqueued to circular queue
30 was enqueued to circular queue
35 was enqueued to circular queue
The queue looks like:
15 20 25 30 35
15 was dequeued from circular queue
20 was dequeued from circular queue
The queue looks like:
25 30 35
40 was enqueued to circular queue
45 was enqueued to circular queue
50 was enqueued to circular queue
Overflow condition
The queue looks like:
25 30 35 40 45 50
2)
b) Implementation of Circular Queue Operations using Linked List
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct
node *next;
};
struct node *f = NULL;
struct node *r = NULL;
void enqueue (int d) //Insert elements in Queue
{
struct
node *n;
n =
(struct node *) malloc (sizeof (struct node));
n->data = d;
n->next = NULL;
if ((r ==
NULL) && (f == NULL))
{
f = r
= n;
r->next = f;
}
else
{
r->next = n;
r =
n;
n->next = f;
}
}
void dequeue () //
Delete an element from Queue
{
struct
node *t;
t = f;
if ((f ==
NULL) && (r == NULL))
printf
("\nQueue is Empty");
else if
(f == r)
{
f = r
= NULL;
free
(t);
}
else
{
f =
f->next;
r->next = f;
free
(t);
}
}
void display ()
{ //
Print the elements of Queue
struct
node *t;
t = f;
if ((f ==
NULL) && (r == NULL))
printf
("\nQueue is Empty");
else
{
do
{
printf (" %d", t->data);
t = t->next;
}
while
(t != f);
}
}
int main ()
{
enqueue
(34);
enqueue
(22);
enqueue
(75);
enqueue
(99);
enqueue
(27);
printf
("Circular Queue: ");
display
();
printf ("\n");
dequeue
();
printf
("Circular Queue After dequeue: ");
display
();
return 0;
}
Output:
Circular Queue:
34 22 75 99 27
Circular Queue After dequeue: 22 75 99 27
Comments
Post a Comment