Queue:
A Queue is a linear data structure which follows First In First Out (FIFO) principle, in which insertion is performed at rear end deletion is performed at front end.
(or)
A queue is a "waiting line" type of data structure. Much like with a stack, we can insert items into a queue and remove items from a queue. However, a queue has "first come, first served" behavior in that the first item inserted into the queue is the first one removed.
Operations on Queue:
- Enqueue
- Dequeue
Exception condition:
Overflow: Attempt to insert an element, when the queue is full
Underflow: Attempt to delete an element from the queue, when the queue is empty.
Uses of Queues:
Queues are commonly used in operating systems and other software where some sort of waiting line has to be maintained for obtaining access to a resource. For example, an operating system may keep a queue of processes that are waiting to run on the CPU. It might also keep a queue of print jobs that are waiting to be printed on a printer. Queues are also used in simulations of stores and their waiting lines at the check-out counters.
Alogarithm Steps:
Step 1: Create nodes first, last, cur
Step 2: Read the queue operation.
Step 3: Create a list.
- Create a new empty node cur.
- Allocate memory for the node cur.
- Read the queue’s first element in cur node’s data part.
- Assign cur node’s link part as Null.
- Assign first=last=cur.
Step 4: If the queue operation is Insertion then do the following steps
- Create a new empty node cur.
- Allocate memory for the node cur.
- Read the queue’s element in cur node’s data part.
- Assign cur node’s link part as null.
- Assign last = cur.
Step 5: If the queue operation is Deletion then do the following steps.
- If first equal to NULL then display queue is empty.
- Assign cur as first. (i.e. cur=first).
- Assign first as first of link (i.e. first=first->link).
- Assign cur of link as NULL. (i.e. cur->link=NULL).
- Reallocate the node cur from memory.
Step 6: If the operation is Display then do the following steps
- Assign cur as first.
- Repeat until cur becomes Null.
- Display cur node’s data.
- Assign cur as cur of link.
Step 7: go to step 2.
C Program To Implement Queue Using linked list
CPP Program To Implement Queue Using linked list
|