Queue
QuQue eu ue e
INTRODUCTION
A queue is a collection of entities are kept in order. The principal operations are Addition of entities to the rear terminal position Removal of entities from the front terminal Qu eu position. e Queue is a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. A queue is an example of a linear data structure.
Front Rear
Real Life Ex: Waiting in line
Qu eu
Applications related to Computer Science: Threads Job scheduling (e.g. Round-Robin algorithm for CPU allocation)
QUEUE OPERATIONS
enqueue - insert item at the back of queue. dequeue - return (and virtually remove) the front item from queue. init - initialize queue, reset all variables. Qu eu There are other operations such as full and empty. e
A Linked Implementation of a Queue
Use chain of linked nodes for the queue Two ends at opposite ends of chain Accessing last node inefficient with only head reference Qu eu Could keep a reference to the tail of the e chain With references to both Place front of queue at beginning of chain Place back of queue at end of chain
A Linked Implementation of a Queue
Qu eu
A Linked Implementation of a Queue
Qu eu
Array-Based Implementation of a Queue
Initially, let queue[0] be the front
frontIndex, backIndex
are indices of front
and back
If we maintain queue[0] is front e
Must shift entries when we remove the front
Qu eu
Instead, we move frontIndex
Problem then is array can become full But now beginning of array could be empty and available for use
Applications: Job Scheduling
front rear Q[0] Q[1] Q[2] Q[3] -1 -1 -1 0 J1 Qu e -1 1 J1 J2 u e -1 2 J1 J2 J3 0 2 J2 J3 1 2 J3
Find out the errors?
Comments queue is empty Job 1 is added Job 2 is added Job 3 is added Job 1 is deleted Job 2 is deleted
PROCEDURE ADD(QUEUE, F, R, N, item)
[This will inserts item in the queue after R (rear) where n is size of array.]
1. [Overflow ?] if (R >= N) write Stack is full. return. 2. [Increment R] R <-- R + 1 3. [Insert Element] QUEUE [R] <-- item. 4. [Setting the F (Front) pointer] if (F=0) F=1 return.
Qu eu
PROCEDURE DELETE(QUEUE, F, R, item)
[Deletes item from the stack, F is the Front end pointer and R is the rear end pointer]
1. [Underflow ?] if (R <= 0) write Stack is empty. return. 2. [Deleting Element] Qu eu item <-- QUEUE[F] e 3. [Incrementing F] F <-- F + 1 4. [Checking for empty queue] if (F > R) then F <-- R <-- 0 return.
Qu eu e
En-queue & De-queue
Qu eu
En-queue & De-queue
Qu eu
Implementation using Arrays
#include <stdio.h> #define MAX 50 void insert(); void delet(); void display(); int queue[MAX], rear=-1, front=-1, item; Qu eu main() e { int ch; do { printf("\n\n1. Insert\n2. Delete\n3. Display\n4. Exit\n"); printf("\nEnter your choice: "); scanf("%d", &ch);
switch(ch) { case 1: insert(); break; case 2: delete(); break; Qu case 3: eu e display(); break; case 4: exit(0); default: printf("\n\nInvalid entry. Please try again...\n"); }} while(1); getch(); }
void insert()
{
if(rear == MAX-1) printf("\n\nQueue is full."); else
{
printf("\n\nEnter ITEM: "); scanf("%d", &item); if (rear == -1 && front == -1) Qu { eu e rear = 0; front = 0;
}
else rear++; queue[rear] = item; printf("\n\nItem inserted: %d", item);
} }
void delete() { if(front == -1) printf("\n\nQueue is empty."); else { item = queue[front]; if (front == rear) Qu { eu e front = -1; rear = -1; } else front++; printf("\n\nItem deleted: %d", item); } }
void display() { int i; if(front == -1) printf("\n\nQueue is empty."); else { printf("\n\n"); Qu eu for(i=front; i<=rear; i++) e printf(" %d", queue[i]); } }
Implementation using Arrays
#include<stdio.h> #include<malloc.h> #define MAXSIZE 10 void insertion(); void deletion(); void display(); Qu struct node eu e { int info; struct node *link; }*new,*temp,*p,*front=NULL,*rear=NULL; typedef struct node N; main() { int ch;
do { printf("\n\t\t\tLinked queue"); printf("\n [Link]"); printf("\n [Link]"); printf("\n [Link]"); printf("\n [Link]"); printf("\n Enter your choice : "); scanf("%d",&ch); switch(ch) { Qu case 1: eu insertion(); e break; case 2: deletion(); break; case 3: display(); break; default: break; }}while(ch<=3); }
void insertion() { int item; new=(N*)malloc(sizeof(N)); printf("\nEnter the item : "); scanf("%d",&item); new->info=item; new->link=NULL; if(front==NULL) Que ue { front=new; } else { rear->link=new; rear=new; } }
void deletion() { if(front==NULL) printf("\nQueue is empty"); else { p=front; printf("\nDeleted element is : %d",p->info); front=front->link; free(p); } } Qu void display() eu { e if(front==NULL) printf("\nQueue is empty"); else { printf("\nThe elements are : "); temp=front; while(temp!=NULL) { printf("%d",temp->info); temp=temp->link; }}}
The biggest lie on the planet, when I get what Ie want I will be HAPPY!
Qu eu