Search for notes by fellow students, in your own course and all over the country.

Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.

My Basket

Buy These Notes

You have nothing in your shopping cart yet.

Title: Queue (DSA)
Description: Basic to advance coverage of Queue concept in DSA and practice questions.
Buy These NotesPreview

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

Shashank Yadav (KIET-Ghaziabad)

8
...

 Queue is also called FIFO (First In First Out), since the first element in a queue will be
the first element out of the queue
...

o By Linear array
o By Linked list

8
...

Q is queue of 6 indexes
...
1
...

QINSERT(Q, N, FRONT, REAR, ITEM)
Where Q is a queue of N indexes, FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...

1
...
Print(Queue is Full)
b
...
If (FRONT==0) then
a
...
REAR=REAR+1
4
...
Return
8
...
2 Algorithm for deleting element from Queue
...
FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...
If (FRONT==0 or FRONT> REAR) then
a
...
Return
2
...
FRONT= FRONT+1
4
...
1
...

#include ...
h>
#define N 10
struct queue
{
int data[N];
int front, rear;
};
void QInsert(struct queue*, int);
int QDelete(struct queue*);
void Traverse(struct queue*);
void main()
{
int choice, item;
struct queue Q;
Q
...
rear=-1;
clrscr();
do
{
32 | P a g e

Shashank Yadav (KIET-Ghaziabad)

printf("\nEnter choice for Queue \n");
printf("1
...
Delete \n3
...
Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\nEnter number for inserting in queue\t");
scanf("%d",&item);
QInsert(&Q, item);
break;
case 2: item= QDelete(&Q);
printf("\nDeleted item is %d", item);
break;
case 3: Traverse(&Q);
}
}while(choice!=4);
}
void QInsert(struct queue*Q, int item)
{
if(Q->rear==N-1)
printf("\nQueue is full");
else
{
if(Q->front==-1)
Q->front= Q->front+1;
Q->rear=Q->rear+1;
Q->data[Q->rear]=item;
printf("\n%d has been inserted into queue", item);
}
}
int QDelete(struct queue*Q)
{
int item;
if(Q->front==-1 || Q->front > Q->rear)
{
printf("\nQueue is empty");
return(0);
}
item=Q->data[Q->front];
Q->front=Q->front+1;
return(item);
}
void Traverse(struct queue *Q)
33 | P a g e

Shashank Yadav (KIET-Ghaziabad)

{
int i;
printf("\nQueue elements are \n");
for(i=Q->front; i<=Q->rear; i++)
{
printf("%d\t",Q->data[i]);
}
}

8
...

8
...
1 Algorithm for inserting element into Circular-Queue
...
FRONT and REAR are two integer variable,
FRONT stores the position of first element and REAR stores the position of last element of
queue
...

1
...
Print(Queue is Full)
b
...
If (FRONT==0) then
a
...
REAR= (REAR%N+1)
34 | P a g e

//check overflow condition

Shashank Yadav (KIET-Ghaziabad)

4
...
Return
8
...
2 Algorithm for deleting element from Circular-Queue
...
FRONT and REAR are two integer variable,
FRONT stores the position of first element and REAR stores the position of last element of
queue
...
If (FRONT==0) then
//check underflow condition
a
...
Return
2
...
If (FRONT==REAR) then
a
...
REAR=0
4
...
Return(ITEM)

8
...
3 C program for Circular-Queue (Insertion, Deletion, Traversing)
...
h>
#include ...
front=-1;
Q
...
Insert \n2
...
Traverse \n4
...
3 Deque /(Double-Ended-Queue) /(Dequeue) /(Deck):
 A deque is a linear list in which elements can be added or removed at either end but not
in the middle
...
3
...

DQ_REAR_INSERT(Q, N, FRONT, REAR, ITEM)
Where Q is a deque of N indexes, FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...

1
...
Print(Queue is Full)
b
...
If (FRONT==0) then
a
...
REAR=REAR+1
4
...
Return

DQ_FRONT_INSERT(Q, N, FRONT, REAR, ITEM)
Where Q is a deque of N indexes, FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...


37 | P a g e

Shashank Yadav (KIET-Ghaziabad)

1
...
Print(ITEM cannot be inserted)
b
...
FRONT=FRONT-1
3
...
Return
8
...
2 Algorithm for deleting element from a Deque
...
FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...
If (FRONT==0 or FRONT> REAR) then
a
...
Return
2
...
FRONT= FRONT+1
4
...
FRONT and REAR are two integer variable, FRONT
stores the position of first element and REAR stores the position of last element of queue
...
If (REAR==0 or FRONT>REAR) then
a
...
Return
2
...
REAR=REAR-1
4
...
3
...

#include ...
h>
#define N 10
struct dqueue
{
int data[N];
int front, rear;
};
void DQ_Rear_Insert(struct dqueue*, int);
void DQ_Front_Insert(struct dqueue*, int);
38 | P a g e

Shashank Yadav (KIET-Ghaziabad)

int DQ_Front_Delete(struct dqueue*);
int DQ_Rear_Delete(struct dqueue*);
void DQTraverse(struct dqueue*);
void main()
{
int choice, item;
struct dqueue Q;
Q
...
rear=-1;
clrscr();
do
{
printf("\nEnter choice for Queue \n");
printf("1
...
Front Inseat \n");
printf("3
...
Rear Delete \n");
printf("5
...
Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\nEnter number for inserting in queue\t");
scanf("%d", &item);
DQ_Rear_Insert(&Q, item);
break;
case 2: printf("\nEnter number for inserting in queue\t");
scanf("%d",&item);
DQ_Front_Insert(&Q, item);
break;
case 3: item= DQ_Front_Delete(&Q);
printf("\nDeleted item is %d", item);
break;
case 4: item= DQ_Rear_Delete(&Q);
printf("\nDeleted item is %d", item);
break;
case 5: DQTraverse(&Q);
}
}while(choice!=6);
}
void DQ_Rear_Insert(struct dqueue*Q, int item)
{
if(Q->rear==N-1)
printf("\nQueue is full");
else
{
39 | P a g e

Shashank Yadav (KIET-Ghaziabad)

if(Q->front==-1)
Q->front= Q->front+1;
Q->rear=Q->rear+1;
Q->data[Q->rear]=item;
printf("\n%d has been inserted into queue", item);
}
}
void DQ_Front_Insert(struct dqueue*Q, int item)
{
if(Q->front<=0)
printf("\nElement cannot be inserted");
else
{
Q->front=Q->front-1;
Q->data[Q->front]=item;
printf("\n%d has been inserted into queue", item);
}
}
int DQ_Front_Delete(struct dqueue*Q)
{
int item;
if(Q->front==-1 || Q->front > Q->rear)
{
printf("\nQueue is empty");
return(0);
}
item=Q->data[Q->front];
Q->front=Q->front+1;
return(item);
}
int DQ_Rear_Delete(struct dqueue*Q)
{
int item;
if(Q->rear==-1 || Q->front > Q->rear)
{
printf("\nQueue is empty");
return(0);
}
item=Q->data[Q->rear];
Q->rear=Q->rear-1;
return(item);
}
40 | P a g e

Shashank Yadav (KIET-Ghaziabad)

void DQTraverse(struct dqueue *Q)
{
int i;
printf("\nQueue elements are \n");
for(i=Q->front;i<=Q->rear;i++)
{
printf("%d\t",Q->data[i]);
}
}

8
...

o An element of higher priority is processed before any element of lower priority
...

 There are various ways of maintaining a priority queue in memory
...
5 Applications of Queue:
 Round-robin technique for processor scheduling is implemented using queues
...

i
...
jobs sent to a printer are placed on a queue
...
For example, BFS,
traversing of a binary tree etc
Title: Queue (DSA)
Description: Basic to advance coverage of Queue concept in DSA and practice questions.
Buy These NotesPreview