Queues Presentation

QUEUES Presented by: Jovar V.Tabat Ma.Liezell N. Acosta

What is Queue? •It is an ordered list in which all insertion take place at the other end, known as the bottom. This type of processing behavior is also called FIFO or First-In-First-Out.

Representation of Queues

Queues may be represented as: 1.OneDimensional Arrays

One - Dimensional Array Representation Arr [n] => Arr [n-1] =>

Arr [4] => Arr [3] => Arr [2] => Arr [1] =>

… Phillip

<=Top

Retchan Gretchen

<= Bottom

One – Dimensional Array If we are going to delete “Gretchen” the output will be look like this:

Arr [n] =>

Arr [n-1] => Arr [4] =>

…

Arr [3] =>

Phillip Arr [2] =>

Retchan Arr [1] =>

<=Top <= Bottom

Queues are represented as One-Dimensional Array when:

1.The maximum size of the queue is known. 2.The amount of time wasted in shifting

Single-Linked List Representation HEAD

25 H

Jason 5H

TAIL

5H

Melai 6H

6H

Carol

Null

Queues are represented as singlylinked list when: 1. The maximum size of the queue

QUEUE OPERATION There are Three Basic Operation that may be performed on queues. 1.Inserting an element at the top of a queue. 2.Deleting the bottom element from a queue.

Inserting a Node at the Top of a Queue • Head : The address of the first node in the queue • Tail : The address of the last node in the queue • Value : The value to be inserted into the queue Code: Insert _ Q (Head, Tail , Value)

Deleting the Bottom Node From a Queue • Head : The address of the first node in the queue •Tail : The address of the last node in the queue Code: Delete _ Q (Head, Tail)

Retrieving the Bottom Element from a Queue Code : Retrieve _ Q ( Head)

Circular Queues • Here, the elements of the array are “ arranged” in a circular fashion with Arr[1] following Arr[n].

Arr [3] Arr [2] Top = 0 Bottom = 0

Arr [4] Arr [1]

Arr [6]

Arr [5]

One-Dimensional Array as Circular Queues ♥When using this, the bottom of the queue is not always located in Arr[1].Instead, the bottom, and top of the queue is monitored by two variables which we will also call TOP and BOTTOM. ♥TOP and BOTTOM contain the value (0) ♥ If we insert “A” into the queue, TOP will be 1 and BOTTOM will be 1 too.

Representation of Circular Queue Arr[2]

Top = 1 Bottom = 1

Arr[3]

Arr[1] Arr[4]

A

Arr[6]

Arr[5]

Circular Queue after inserting “A”

Representation of Circular Queue Arr[2]

Top = 2

Arr[3]

B Bottom = 1

Arr[1] Arr[4]

A

Arr[6]

Arr[5]

Circular Queue after Inserting ”B”

Representation of Circular Queue Arr[2]

Top, Bottom = 2

Arr[3]

B

Arr[1] Arr[4]

Arr[6]

Arr[5]

Circular Queue After Deleting the Bottom Element

Inserting an Element into Circular Queue • Top : The location of the element at the top of the queue. • Bottom : The location of the element at the bottom of the queue. • Arr : The array representing the queue. • Max : The maximum number of elements in the queue. • Value : The value of the element to be inserted into the queue.

Code for Inserting Element • Insert _ Circular_ Q ( Top, Bottom, Arr, Max, Value ) Top=Bottom = 0

Arr[1] Arr[2]

Arr[3] Arr[4]

Arr5] Arr[6] Arr[7] Arr[8] Arr[9] Arr[10]

Circular Queue With Maximum 10 Elements

Code for Inserting Element • Insert _ Circular_ Q ( Top, Bottom, Arr, Max, Value )

A Arr[1] Arr[2]

Arr[3] Arr[4]

Arr5] Arr[6] Arr[7] Arr[8] Arr[9] Arr[10]

Circular Queue With Maximum 10 Elements Insert A: Insert _ Circular_ Q ( 0, 0, Arr, 10, “A” ) Top=1 Bottom=1 Arr[1]=“A”

Code for Deleting Element • Delete _ Circular_ Q ( Top, Bottom, Arr, Max)

A Arr[1] Arr[2]

Arr[3] Arr[4]

Arr5] Arr[6] Arr[7] Arr[8] Arr[9] Arr[10]

Circular Queue With Containing 1 Element Delete A: Delete _ Circular_ Q ( 1,1, Arr, 10) Top=0 Bottom=0

♥THANK YOU FOR LISTENING♥