Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: Dec 2014

Type definition for Queue ADT:

typedef struct node
{
void* dataPtr;
struct node* next;
}QUEUE_NODE;
typedef struct
{
QUEUE_NODE* front;
QUEUE_NODE* back;
int count_total;
}QUEUE;

Here each node contains a void pointer to the data and a link pointer to next element in the queue. The queue head structure also contains three elements, the queue's front element, its last element and the count of number of elements present in queue.

ADT for various function operations:

QUEUE* create_queue(void);          //creates a queue
bool is_empty(QUEUE* queue);            //checks if queue is empty
bool is_full(QUEUE* queue);         //checks if queue is full
bool enqueue(QUEUE* queue,void* itemPtr);   //inserts a item into queue
bool dequeue(QUEUE* queue,void* itemPtr)    //delete element from queue
QUEUE* destroy_queue(QUEUE* queue);     //deletes the queue

Applications of Queue:

a. In operating systems:

• In an OS multiple programs are executing at the same time.
• Every process is associated with as state of the process which can be ready, running, blocked, wait, etc.
• An OS maintains a queue of all such processes. The queue is used for scheduling these processes. Whenever a process completes execution, it is removed from queue and the next in queue are given turn. When a process changes its state, it is added to the queue and gets scheduled for execution.

b. Websites:

• Queues are used for any situation where you want to efficiently maintain a First-in-first out order on some entities. These situations arise literally in every type of software development.
• Imagine you have a web-site which serves files to thousands of users. You cannot service all requests, you can only handle say 100 at once.
• A fair policy would be first-come-first serve: serve 100 at a time in order of arrival. A Queue would definitely be the most appropriate data structure.

c. Printers:

• Say you have a number of documents to be printed at once.
• Your OS puts all of these docs in a queue and sends them to the printer.
• The printer takes and prints each document in the order the docs are put in the queue, i.e., First In, First Out.