Scribd
Upload
10 views19 pages

Queue 2

A queue is a first-in first-out (FIFO) data structure. The document discusses queue operations and implementations including array-based and circular array-based queues. Circular queues are better than standard arrays for queue implementation as they avoid costly shifting when removing elements. Common applications of queues include printing job management, packet forwarding, message queues, and I/O buffering. The document provides examples of enqueue and dequeue operations on a circular queue and discusses queue interfaces versus implementations.

Uploaded by

Mustafa Adil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views19 pages

Queue 2

A queue is a first-in first-out (FIFO) data structure. The document discusses queue operations and implementations including array-based and circular array-based queues. Circular queues are better than standard arrays for queue implementation as they avoid costly shifting when removing elements. Common applications of queues include printing job management, packet forwarding, message queues, and I/O buffering. The document provides examples of enqueue and dequeue operations on a circular queue and discusses queue interfaces versus implementations.

Uploaded by

Mustafa Adil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

Introduction to

Queues
2
Introduction to Queues
 What is a queue?
 Queue operations.
 Queue implementations.
 Queue As Array
 Queue As Circular Array

 Applications of queue.
Array Implementation of Queue
3

n-1 3 2 1 0
DCBA

Max_Size rear front

After A leaves,
n-1 3 2 1 0
DCB

Max_Size rear front


4
Problem

 An array has limited size, once rear is at the end of


this array, and there is new item coming in, what can
we do?

n-1 3 2 1 0
Y X ……

rear front
5
Two Solutions

 Shifting all items to front in the array when


dequeue operation. ( Too Costly… )

A
n-1 3 2 1 0 n-1 3 2 1 0
leaves
…… CBA …… CB

rear= front= rear= front=


3 0 2 0
 Wrapped around array ---- Circular Array
6
Circular Array

rear=
3
 Wrapped around array 3
2
n-1 3 2 1 0 front= 1 BC
…… CBA 0
0 A

rear= front= n-1


3 0
EnQueue & DeQueue In Circular Array
7

 EnQueue • DeQueue
 rear = (rear + 1) MOD n – front = (front + 1) MOD n

3 rear=3 front=1 3
2 2
1 BC 1 BC

0 A 0
n- n-
1 1
8
Empty/Full In Circular Array
 When rear equals front, Queue is empty
 When (rear + 1) MOD n equals front, Queue is
full
 Circular array with capacity n at most can hold n-
1 items.
Implementation for CQueue
9

Interface
 Users don’t need to know how Queue is implemented.
 User only need to know how they can operate the
Queue.
 There are many ways to implement Queue, but all of
them have the same interfaces
 enqueue, dequeue, peek, isFull, isEmpty
Implementation for Circular Queue
10

// header file (for example Qh.h)


#define max 6
struct queuest
{
int QueueA[max];
int front;
int back;
};
11
12
13
14
// main1.cpp: implementation of the main class.
#include <iostream.h>
15
#include <stdlib.h>
#include <dos.h>
#include "main1.h“
void main()
{

queuest cq;
int nn;
CQueue.initialize(&cq);
for(;;)
{
// main1.h: interface for the main class.
cout<<endl;
#include "cqueue.h“
cout<<"*****************************"<<endl; …
cout<<"*1- Insertion operation *"<<endl; …
cout<<"*2- Delete operation *"<<endl; cqueue CQueue;
cout<<"*3- Display operation *"<<endl; ….
…..
cout<<"*4- Exit *"<<endl;
cout<<"****************************"<<endl;
cout<<" Enter your (1-4) :";cin>>nn;
cout<<endl;
switch (nn)
16 {
case 1:
cout<<endl<<"Enter the no. of element";
cin>>n1;
for(i=0;i<n1;i++)
{
cout<<"Enter the element...";
cin>>m;
CQueue.enqueue(&cq,m);
CQueue.printcq(&cq);
}
break;
case 2:
cout<<CQueue.dequeue(&cq)<<" ";
break;
case 3:
CQueue.printcq(&cq);
break; }
}
Applications of Queue
17

 Printing Job Management


 Packet Forwarding in Routers
 Message queue in Windows
 I/O buffer
Printing Job Management
18

 Many users send their printing jobs to a public


printer
 Printer will put them into a queue according to
the arrival time and print the jobs one by one
 These printing documents are A.doc, B.doc,
C.doc and D.doc
19
Lab Exercise:-
Write a program in C++ to implement Operations on Circular Queue

Homework:-
1-Program to implement insert and delete operations on Priority Queue .

You might also like