UNIT-I
QUEUES
(Introduction)
CH BALAKRISHNA
Department of CSE
Sai Spurthi Institute of Technology
Definition
• Queue is a linear data structure.
• Queue is a collection of homogeneous data elements, where insertion operation is
performed at rear end and deletion operation is performed at front end.
• Stack follows FIFO principle. i.e. First In First Out
Queue Operations:- We can perform mainly 2 operations on Queue.
1.Enqueue :- Inserting an element into the Queue
2.Dequeue:- Deleting an element from the Queue
10 20 30 40 50
Enqueue :-
Inserting an element into the Queue
Q
10
Enqueue :-
Inserting an element into the Queue
Q
20 10
Enqueue :-
Inserting an element into the Queue
Q
30 20 10
Enqueue :-
Inserting an element into the Queue
Q
40 30 20 10
Enqueue :-
Inserting an element into the Queue
Q
50 40 30 20 10
Enqueue :-
Inserting an element into the Queue
Q
50 40 30 20 10
QUEUE OVERFLOW
Enqueue :-
Inserting an element into the Queue
Q
50 40 30 20 10
QUEUE OVERFLOW
Dequeue :-
Deleting an element from the Queue
Q
30 20 10
Dequeue :-
Deleting an element from the Queue
Q
30 20
Dequeue :-
Deleting an element from the Queue
Q
30
Dequeue :-
Deleting an element from the Queue
QUEUE UNDERFLOW
QUEUES Using Arrays
Washington
WASHINGTON UNIVERSITY IN ST LOUIS
Array Representation of Queue
• Queue is a linear data structure.
• Queue is a collection of homogeneous data elements, where insertion operation is
performed at rear end and deletion operation is performed at front end.
• Stack follows FIFO principle. i.e. First In First Out
Queue Operations:- We can perform mainly 2 operations on Queue.
1.Enqueue :- Inserting an element into the Queue
2.Dequeue:- Deleting an element from the Queue
Q[4] Q[3] Q[2] Q[1] Q[0]
10 20 30 40 50
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
10
Rear 0
-1
Front -1
0
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
20 10
Rear 1
0
Front 0
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
30 20 10
Rear 1
2
Front 0
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
40 30 20 10
Rear 3
2
Front 0
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
50 40 30 20 10
Rear 3
4
Front 0
else
void enqueue( ) {
{ rear++;
if(rear==SIZE-1) printf("\nEnter an element to be inserted into the
{ queue");
printf("\nQueue is full"); scanf("%d", &ele);
} queue[rear]=ele;
if(front == -1)
front = 0;
}
} //End of Enqueue()
Q[4] Q[3] Q[2] Q[1] Q[0]
50 40 30 20 10
Rear 4
Front 0 QUEUE OVERFLOW
Else
void dequeue( ) {
{ ele=queue[front];
if(front == -1 || front > rear) printf("\nDeleted element from the queue is %d", ele);
{
front++;
printf("\nQueue is Empty");
}
front = -1;
} //End of Enqueue()
rear = -1
}
Q[4] Q[3] Q[2] Q[1] Q[0]
30 20 10
Rear 2
Front 0
1
Else
void dequeue( ) {
{ ele=queue[front];
if(front == -1 || front > rear) printf("\nDeleted element from the queue is %d", ele);
{
front++;
printf("\nQueue is Empty");
}
front = -1;
} //End of Enqueue()
rear = -1
}
Q[4] Q[3] Q[2] Q[1] Q[0]
30 20
Rear 2
Front 1
2
Else
void dequeue( ) {
{ ele=queue[front];
if(front == -1 || front > rear) printf("\nDeleted element from the queue is %d", ele);
{
front++;
printf("\nQueue is Empty");
}
front = -1;
} //End of Enqueue()
rear = -1
}
Q[4] Q[3] Q[2] Q[1] Q[0]
30
Rear 2
Front 2
3
Else
void dequeue( ) {
{ ele=queue[front];
if(front == -1 || front > rear) printf("\nDeleted element from the queue is %d", ele);
{
front++;
printf("\nQueue is Empty");
}
front = -1;
} //End of Enqueue()
rear = -1
}
QUEUE UNDERFLOW
Q[4] Q[3] Q[2] Q[1] Q[0]
Rear -1
2
Front 3
-1
else
void display( ) {
{
printf("\n The elements of queue are\n");
if(front == -1 || front > rear)
for(i=front; i<=rear; i++)
{
printf("%d\t", queue[i]);
printf("\n Queue is Empty");
}
front = -1;
} //End of display()
rear = -1
}
Q[4] Q[3] Q[2] Q[1] Q[0]
50 40 30 20 10
Rear 4
Front 0
QUEUE Using Linked List
Washington
WASHINGTON UNIVERSITY IN ST LOUIS
Linked List Representation of Queue
• Queue is a linear data structure.
• Queue is a collection of homogeneous data elements, where insertion operation is
performed at rear end and deletion operation is performed at front end.
• Stack follows FIFO principle. i.e. First In First Out
Queue Operations:- We can perform mainly 2 operations on Queue.
1.Enqueue :- Inserting an element into the Queue
2.Dequeue:- Deleting an element from the Queue Rear
10 20 30 40 50 NULL
Front
Value Pointer
Node
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*front,*rear;
void enqueue( )
{
newNode=(struct node *)malloc(sizeof(struct node));
printf("\n Enter an element to be inserted into queue\n");
Scanf("%d", &value);
newNode->data=value;
newNode->next=NULL;
if(rear==NULL)
{
front=rear=newNode;
}
else Front Rear 10 NULL 1
{
rear->next=newNode;
rear=newNode;
} Front
} NULL
Rear
void enqueue( )
{
newNode=(struct node *)malloc(sizeof(struct node));
printf("\n Enter an element to be inserted into queue\n");
Scanf("%d", &value);
newNode->data=value;
newNode->next=NULL;
if(rear==NULL)
{ Rear 20 NULL 2
front=rear=newNode;
}
else Front 10 1
{
rear->next=newNode;
rear=newNode;
}
}
void enqueue( )
{
newNode=(struct node *)malloc(sizeof(struct node));
printf("\n Enter an element to be inserted into queue\n");
Scanf("%d", &value);
newNode->data=value; Rear 30 NULL
NULL 3
newNode->next=NULL;
if(rear==NULL)
{ 20 2
front=rear=newNode;
}
else Front 10 1
{
rear->next=newNode;
rear=newNode;
}
}
void dequeue( )
{
if(rear==NULL || front==NULL)
{
printf(“ Queue is Empty”);
}
else
{ Rear 30 NULL 3
front=front->next;
}
} 20 2
Front 10 1
void dequeue( )
{
if(if(rear==NULL || front==NULL)
{
printf(“ Queue is Empty”);
}
else
{ Rear 30 NULL 2
front=front->next;
}
}
Front 20 1
void dequeue( )
{
if(if(rear==NULL || front==NULL)
{
printf(“ Queue is Empty”);
}
else
{ Rear 30 NULL 1
front=front->next; Front
}
}
Front
Display Rear
10 20 30 40 50 NULL
void Display( )
{
if(if(rear==NULL || front==NULL)
{
printf(“ Queue is Empty”);
}
else
{
temp=front;
while(temp!=NULL)
{
printf(“%d->”,temp->data);
temp=temp->next;
}
}
}
