Queue

Views:
 
Category: Education
     
 

Presentation Description

How to insert and delete in queue.

Comments

Presentation Transcript

Data Structure :

By: sachin shrivastava Data Structure By : Sachin Shrivastava 1

PowerPoint Presentation:

By : Sachin Shrivastava 5 QUEUES QUEUES

PowerPoint Presentation:

Queues : A queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queues). Queue mainly follows the principal of FIFO (First-in-First-out) or FCFS (First-come-First-serve) By : Sachin Shrivastava 6 QUEUES Examples of a around the real world are a line at a bank or bus Stop and a group of cars waiting at a tool booth.

PowerPoint Presentation:

By : Sachin Shrivastava 7 QUEUES

PowerPoint Presentation:

By : Sachin Shrivastava 8 QUEUES Properties of Queue : Queue can be consider as a line of items, which has following essential properties- It has two end that are front and rear. Addition of new item can only be done at rear. Deletion of an item can only be done from front. The item which is added first will be deleted first. Hence the structure is frequently called “FIFO”. Only one item can be added at one time. Only one item can be deleted at one time. No element other than front and rear element are visible. Drawback of Queue : After some addition/deletion operations, there will be a situation in which rear reaches to the last position of array and there is empty space before front. Since addition can only be done at rear, so no item can be added even if we have empty space in the queue.

PowerPoint Presentation:

By : Sachin Shrivastava 9 QUEUES Solution of this Drawback : We can solve above problem by shifting of items, for shifting we have two approaches - As soon as an item is deleted, shift the entire queue towards the beginning of the array. It ensures that the front always remains at zeros position. So, if there is any space it will be after rear. But in this Dqueue (Delete) operation is very time consuming because it required a lot of data movement operation. During Enqueue (adding) operation as soon as rear reaches at the last of array and front is not at first position or says zeros position. This method is better than previous, because the frequency of data movement operation is very less.

PowerPoint Presentation:

By : Sachin Shrivastava 10 QUEUES Operations on a Queue : The basic operations that can be performed on queue are – Create a queue. Check queue is empty. Check queue is full. Enqueue operation. Dequeue operation.

PowerPoint Presentation:

By : Sachin Shrivastava 11 QUEUES Algorithm for Addition in a Queue : Step1 : initialize Front =0 and Rear =-1 [Check overflow condition] Step 2 : If Rear >= MaxSize -1. Write : “Queue overflow” Exit Else : Set Rear = Rear+1 Step3 : Queue[Rear] = item Step4 : If Front = -1 [set the front pointer] set front = 0 Step5 : Return

PowerPoint Presentation:

By : Sachin Shrivastava 12 QUEUES Algorithm for Deletion from a Queue : [ Check Underflow condition ] Step1 : if Front <0 Write : “Queue is Empty” Exit Else : Set Item = Queue[Front] [Remove Element from Front] Step2 : Find new value of front If (Front = Rear) [Checking for empty Queue] set Front =0, Rear = -1 [Re-initialize the pointers] else: Front = Front + 1 Step3 : Exit

PowerPoint Presentation:

By : Sachin Shrivastava 13 QUEUES Types of Queue : There are several variations we can made to a simple queue, to suit our Requirement. There of the major variations made in a simple queue are Circular queue. De-queue (Double ended queue). Priority queue.

PowerPoint Presentation:

By : Sachin Shrivastava 14 QUEUES 1. Circular queue : A circular queues is one in which the insertion of a new element in done at The very first location of the queue, if the last location of the queue is full. “ We can say that a circular queue is one in which the first element comes just after the last element ” It can be viewed as a loop of wire, in which the two ends of the wire are connected together. Q[0] Q[1] Q[2] Q[3] Q[4] Circular Queue

PowerPoint Presentation:

By : Sachin Shrivastava 15 QUEUES A circular queue overcomes the problem of unutilized space in linear queues Implemented as arrays. A circular queue also have a front and rear to keep the track of the elements to deleted and inserted and therefore to maintain the unique characteristic of the queue. The following are some basic characteristics of circular queue – Front will always be pointing to the first element(as in the linear queue) If front = rear the queue will be empty. Each time a new element is inserted into the queue the rear is incremented by one. rear = rear + 1 Each time an element is deleted from the queue the value of front is incremented by one. front = front + 1

PowerPoint Presentation:

By : Sachin Shrivastava 16 QUEUES Insertion : In figure shows the process of insertion in a circular queue. If the queue will be full and we now try to add another element to the queue as the new element is inserted from the rear end, the position of the element to be inserted will be calculated by the relation – Rear = (rear + 1) % Maxsize Queue [rear] = Value Q[0] Q[1] Q[2] Q[3] Q[4] Circular Queue (a) 5 10 20 Front Rear Q[0] Q[1] Q[2] Q[3] Q[4] 5 10 20 Front 30 40 Circular Queue (b) Rear

PowerPoint Presentation:

By : Sachin Shrivastava 17 QUEUES Deletion : In figure, the queue is full. Now, if we delete one element from the queue, it will be deleted from the front end. After deleting the front element, the front should be modified according to position of front. That is, if front indicates to the last element of the circular queue then after Deleting that element the front should be again reset to 0 (front = 0). Otherwise after every deletion the new position which front should indicate will be given as - Q[0] Q[1] Q[2] Q[3] Q[4] 5 10 20 Rear Front 30 40 Circular Queue (c) Front = (front + 1) % Maxsize

PowerPoint Presentation:

By : Sachin Shrivastava 18 QUEUES 2. Deque : Deque is a linear list in which, insertion of an element and deletion of an element is performed at both end. Deque is know as Double Ended Queue. Front Rear A B C D E Insertion Deletion Deletion Insertion In deque, if the element is inserted from the “Front-end” the “Front” is decreased by 1 and if it is inserted at the “Rear-end”, then “Rear” is increased by 1. If the element is deleted from the “Front-end”, then the front is increased by 1 and if the element is deleted from “Rear-end”, then “Rear” is decreased by 1. When “Front” is equal to “Rear” before deletion then ”Front” and “Rear” are both set to NULL, to indicate that the deque is empty (a) A Deque [0] [1] [2] [3] [4]

PowerPoint Presentation:

By : Sachin Shrivastava 19 QUEUES Input restricted Deque. Front Rear A B C D E Deletion Deletion Insertion (b) Input-restricted Deque Front Rear A B C D E Insertion (c) Output-restricted Deque Insertion Deletion 2. Output-restricted Deque There are two types of deque : Input restricted deque. Output restricted deque.

PowerPoint Presentation:

Algorithm to insert an element at Rear End of Deque : Front Rear Front Rear Step1 : [ check the possibility of insertion at rear ] it(rear==maxsize-1) then display : “Deque is full” Exit Else Step 2 : [ Increase the value of rear by 1 ] Set Rear = Rear+1 Step3 : [Store the item at rear of Deque] Q[rear] = item Step4 : End By : Sachin Shrivastava 20 QUEUES A B C D E [0] [2] [3] [4] A B C D [0] [3] [2] [4] [1] [1] 1. Insertion of an element at the rear end of the deque.

PowerPoint Presentation:

Algorithm to delete element at Front of Deque : Front Rear Front Rear Step1 : [ check the possibility of deletion at front ] it(front==rear) then display : “Deque is empty” Exit Else Step 2 : [Store the front element of Deque] item = Q[front] Step3 : [Increase the value of front by 1] Set Front = Front+1 Step4 : End By : Sachin Shrivastava 21 QUEUES [0] [2] [3] [4] A B C D [0] [3] [2] [4] [1] [1] 2. Delete an element at the front end of the deque.

PowerPoint Presentation:

Algorithm to insert an element at Front End of Deque : Front Rear Front Rear Step1 : [ check the possibility of insertion at front ] it(front==0) then display : “Deque is full” Exit Else Step 2 : [ Decrease the value of front by 1 ] Set Front = Front - 1 Step3 : [Store the item at front of Deque] Q[front] = item Step4 : End By : Sachin Shrivastava 22 QUEUES A B C D [0] [2] [3] [4] C D [0] [3] [2] [4] [1] [1] 3. Insertion an element at the front end of the deque.

PowerPoint Presentation:

Algorithm to delete an element at Rear of Deque : Front Rear Front Rear Step1 : [ Check the possibility of deletion at rear ] it(front==rear) then display : “Deque is empty” Exit Else Step 2 : [Store the rear element of Deque] item = Q[rear] Step3 : [ Decrease the value of rear by 1 ] Set rear = rear - 1 Step4 : End By : Sachin Shrivastava 23 QUEUES [0] [2] [3] [4] A B C D [0] [3] [2] [4] [1] [1] 4. Delete an element at the rear end of the deque.

PowerPoint Presentation:

By : Sachin Shrivastava 24 QUEUES 3. Priority Queue : Priority queue is a set of element such that each element has been assigned a priority. Depending upon that priority the various operation can be performed over the elements. In priority queue, we follows some rules for performing operations, which are as follows – The element having the higher priority is processed before any element of lower priority. Two elements with the same priority are processed according to the order in which they were added to the Queue. There are two type of priority queue – Ascending priority queue. Descending priority queue.

authorStream Live Help