Queue

Views:
 
Category: Education
     
 

Presentation Description

Queue DATA STRUCTURE

Comments

By: adityapaliwal34 (76 month(s) ago)

Hello, Please check your mailbox.

By: sudarshanbansode (86 month(s) ago)

please sir send me ppts sudarshanbansode1854@gmail.com

By: alexryder35 (87 month(s) ago)

it is very nice and so good

Presentation Transcript

Queue:

Queue By:- Aditya Paliwal Comp. Science dept. Email:-adityapaliwal34@gmail.com 8989884134 1

Using a Queue:

Using a Queue Queue is a linear list of elements Deletions can take place only one end-Front Insertions can take place at other end – Rear It is also called as FIFO 2

Example of a Tunnel:

Example of a Tunnel Few vehicles are crossing this tunnel Sequence of vehicles 3

The Queue Operations:

The Queue Operations A queue is like a line of people waiting for a bank teller. The queue has a front and a rear. Front Rear 4

Queue with elements (Deletion):

Queue with elements (Deletion) 1 5 4 3 2 Front Rear 05 02 03 04 01 5 4 3 2 Front Rear 05 02 03 04 1 01 On deleting one element from the front After deletion of an element FRONT is incremented by 1 5

Queue with elements (Insertion):

Queue with elements (Insertion) 1 5 4 3 2 Front Rear 05 02 03 04 01 1 5 4 3 2 Front Rear 05 02 03 01 6 06 7 07 Rear On Inserting elements After insertion of an element REAR is incremented by 1 04 6

Representation of Queues:

Representation of Queues Queue represented in two ways: One way list (or) Linear Array Linked representation of queues 7

Array Representation of Queue:

Array Representation of Queue It is maintained by linear array QUEUE And two pointer variables FRONT & REAR FRONT = NULL and REAR=NULL FRONT = FRONT + 1 (whenever element is deleted from queue) REAR = REAR + 1 (whenever element is added to the queue) FRONT=REAR (Only one element) 8

Array Implementation:

Array Implementation A queue can be implemented with an array, as shown here. For example, this queue contains the integers 4 (at the front), 8 and 6 (at the rear). [0] [1] [2 [3] ABC JKL GHI DEF NULL NULL [4] [5] Front Rear We don’t care what’s in this part 9

Array Implementation:

Array Implementation The easiest implementation also keeps track of the number of items in the queue and the index of the first element (at the front of the queue), the last element (at the rear). [0] [1] [2] [3] ABC NULL GHI DEF NULL NULL [4] [5] Front Rear 3 2 0 SIZE First Last 10

A Dequeue Operation:

A Dequeue Operation When an element leaves the queue, size is decremented, and first changes, too. [0] [1] [2] [3] ABC NULL GHI DEF NULL NULL Front Rear 2 2 SIZE First Last [4] [5] 1 11

An Enqueue Operation:

An Enqueue Operation When an element enters the queue, size is incremented, and last changes, too. [0] [1] [2] [3] JKL GHI DEF NULL NULL Front Rear 3 3 SIZE First Last 1 [4] [5] 12

At the End of the Array:

At the End of the Array There is special behavior at the end of the array. For example, suppose we want to add a new element to this queue, where the last index is [5]: [0] [1] [2] [3] x Y Z Front Rear 3 5 SIZE First Last 3 [4] [5] 13

At the End of the Array:

At the End of the Array The new element goes at the front of the array (if that spot isn’t already used): [0] [1] [2] [3] A x Y Z Front Rear 4 5 SIZE First Last 0 [4] [5] 14

Array Implementation:

Array Implementation Easy to implement But it has a limited capacity with a fixed array Or you must use a dynamic array for an unbounded capacity Special behavior is needed when the rear reaches the end of the array. 15

QINSERT(QUEUE, N, FRONT, REAR, ITEM):

QINSERT(QUEUE, N, FRONT, REAR, ITEM) If FRONT=1 & REAR=N, or if FRONT = REAR+1, then Write: OVERFLOW and Return. If FRONT = null, then (Queue is Empty) set FRONT=1 and REAR = 1 Else if REAR=N then, set REAR = 1 Else: set REAR= REAR+1 End if Set QUEUE (REAR)= ITEM (inserts new element) Return. 16

Queue_delete (QUEUE, N, FRONT, REAR, ITEM):

Queue_delete (QUEUE, N, FRONT, REAR, ITEM) If FRONT= null then, “underflow” and return Set ITEM= QUEUE(FRONT) If (FRONT=REAR)then Set FRONT=NULL and REAR = NULL else if (FRONT =N) then set FRONT=1 else set FRONT= FRONT+1 End if Return 17

Linked representation of queues:

Linked representation of queues Queue implemented as a linked list with two pointer variables (FRONT & REAR) INFO field holds the element LINK field holds the pointers to the neighboring elements A B C D Front Rear A Info Link 18

Algorithm Insertion in LL:

Algorithm Insertion in LL LinkQ_insert(info, link, front, rear, avail, item) 1. If AVAIL = NULL, then “overflow” and exit 2. Set NEW = AVAIL and AVAIL=LINK (AVAIL) 3. Set INFO [NEW] = ITEM & LINK (NEW)=NULL 4. If (FRONT = NULL) then FRONT = REAR = NEW Else: set LINK (REAR)=NEW & REAR=NEW 5. Exit 19

Linkq_delete(info,link, front, rear, avail, item):

Linkq_delete(info,link, front, rear, avail, item) If FRONT=NULL, then write ”underflow” and exit Set TEMP=FRONT ITEM =INFO [TEMP] FRONT = LINK [TEMP] LINK (TEMP)=AVAIL & AVAIL=TEMP Exit. 20

DEQUEUES:

DEQUEUES is a linear list in which elements can be added or removed at either end not in middle Maintained by circular array with two pointers LEFT & RIGHT LEFT is NULL ( deque is empty) 21

Priority Queues:

Priority Queues Its collection of elements & each has been assigned priority Rules are An element of higher priority is processed before any element of lower priority Two elements with same priority are processed according to the order in which they were added to the queue 22

Thank You:

Thank You DEPT. OF COMPUTER SCIENCE ENGINEERING 23

authorStream Live Help