›
›

Cơ sở dữ liệu - Chapter 3: Queue

pdf 50 trang vanle 3700
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chapter 3: Queue", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chapter_3_queue.pdf

Nội dung text: Cơ sở dữ liệu - Chapter 3: Queue

  1. Chapter 3 - QUEUE Definition of Queue Specifications for Queue Implementations of Queue Linked Queue Contiguous Queue Applications of Queue 1
  2. Linear List Concepts FIFO (Queue) 2
  3. Queue - FIFO data structure • Queues are one of the most common of all data-processing structures. • Queues are used where someone must wait one's turn before having access to something. • Queues are used in every operating system and network: processing system services and resource supply: printer, disk storage, use of the CPU, • Queues are used in business online applications: processing customer requests, jobs, and orders. 3
  4. Queue ADT DEFINITION: A Queue of elements of type T is a finite sequence of elements of T, in which data can be inserted only at one end, called the rear, and deleted from the other end, called the front. Queue is a First In - First Out (FIFO) data structure. Basic operations: • Construct a Queue, leaving it empty. • Enqueue an element. • Dequeue an element. • QueueFront. • QueueRear. 4
  5. Basic operation of Queue (EnQueue) Before After rear front rear front EnQueue a) Successful operation: function returns success rear front rear front (Queue remains EnQueue unchanged) b) Unsuccessful operation: function returns overflow 5
  6. Basic operation of Queue (DeQueue) Before After rear front rear front DeQueue a) Successful operation: function returns success (Queue remains DeQueue unchanged) b) Unsuccessful operation: function returns underflow 6
  7. Basic operation of Queue (QueueFront) Before After rear front rear front Received data: QueueFront X X Queue remains unchanged a) Successful operation: function returns success (Queue QueueFront remains unchanged) b) Unsuccessful operation: function returns underflow 7
  8. Basic operation of Queue (QueueRear) Before After rear front rear front Received data: QueueRear X X Queue remains unchanged a) Successful operation: function returns success (Queue QueueRear remains unchanged) b) Unsuccessful operation: function returns underflow 8
  9. Queue ADT (cont.) Extended operations: • Determine whether the queue is empty or not. • Determine whether the queue is full or not. • Find the size of the queue. • Clear the queue to make it empty. • Determine the total number of elements that have ever been placed in the queue. • Determine the average number of elements processed through the queue in a given period. • 9
  10. Specifications for Queue ADT Create() EnQueue (val DataIn ) DeQueue () QueueFront (ref DataOut ) QueueRear (ref DataOut ) isEmpty () isFull () Clear () Size () // the current number of elements in the queue. Variants: ErrorCode DeQueue (ref DataOut ) 10
  11. Built Queue ADT Queue may be fully inhirited from a List, inside its operations calling List’s operations. EnQueue (val DataIn ) Call List::InsertTail(DataIn) or Call List::Insert(DataIn, Size()) // insert after last lement end EnQueue DeQueue (val DataOut ) Call List::RemoveHead(DataOut) or Call List::Remove(DataOut, 0) // remove element from the 1st position end EnQueue Similar for other operations of Queue 11
  12. Implementations of Queue Contiguous Implementation. Linked Implementation. 12
  13. Linked Queue front rear Node Data a) Conceptual link end Node Queue count 4 front front rear count rear end Queue b) Physical 13
  14. Create an Empty Linked Queue Before After front ?? front ? front = NULL rear ? rear = NULL rear count = 0 count = ? count = 0 14
  15. Create Linked Queue Create() Creates an empty linked queue Pre none Post An empty linked queue has been created. 1. front = NULL 2. rear = NULL 3. count = 0 4. Return end Create 15
  16. EnQueue count 4 front Before: pNew->data = DataIn rear pNew->link = NULL rear->link = pNew rear = pNew count = count + 1 pNew count 5 front After: rear 16
  17. EnQueue (cont.) Count 0 Before: front pNew->data = DataIn rear pNew->link = NULL front = pNew rear = pNew count = count + 1 pNew Count 1 front After: rear 17
  18. DeQueue Count 4 Before: front rear pDel = front front = front->link recycle pDel count = count - 1 pDel Count 3 After: front rear 18
  19. DeQueue pDel Count 1 Before: front pDel= front rear front = NULL rear = NULL recycle pDel count = count - 1 pDel Count 0 After: front rear 19
  20. EnQueue & DeQueue Algorithm  EnQueue is successful when queue is not full.  DeQueue successful when queue is not empty.  Regular cases: o EnQueue: only rear must be updated (points to new element). o DeQueue: only front must be updated (points to next element if exists).  Irregular cases: o EnQueue an element to an empty queue: both rear and front must be updated (point to new element). o DeQueue a queue having only one element: both rear Linked Implementation Linked and front must be updated (receive NULL value).  In any successful case, count must be updated. 20
  21. EnQueue Algorithm EnQueue (val DataIn ) Inserts one element at the rear of the queue. Pre DataIn contains data to be inserted. Post If queue is not full, DataIn has been inserted at the rear of the queue; otherwise, queue remains unchanged. Return success or overflow. 21
  22. EnQueue Algorithm (cont.) EnQueue (val DataIn ) // For Linked Queue Empty queue: 1. Allocate pNew 2. If (allocation was successful) pNew->data = DataIn 1. pNew->data = Data pNew->link = NULL 2. pNew->link = NULL front = pNew 3. if (count = 0) rear = pNew 1. front = pNew count = count + 1 4. else 1. rear->link = pNew Not empty queue: 5. rear = pNew pNew->data = DataIn 6. count = count + 1 pNew->link = NULL 7. return success rear->link = pNew 3. Else rear = pNew 1. return overflow count = count + 1 end EnQueue 22
  23. DeQueue Algorithm DeQueue() Deletes one element at the front of the queue. Pre none Post If the queue is not empty, the element at the front of the queue has been removed; otherwise, the queue remains unchanged. Return success or underflow. 23
  24. DeQueue Algorithm (cont.) DeQueue() Queue has more than one // For Linked Queue element: 1. If (count > 0) pDel = front 1. pDel = front front = front->link 2. front = front->link recycle pDel 3. if (count = 1) count = count - 1 1. rear = NULL Queue has only one element: 4. recycle pDel 5. count = count - 1 pDel= front 6. return success front = NULL // = front->link 2. else rear = NULL 1. return underflow recycle pDel 3. end DeQueue count = count - 1 24
  25. QueueFront Algorithm QueueFront (ref DataOut ) Retrieves data at the front of the queue without changing the queue. Pre none. Post if the queue is not empty, DataOut receives data at its front. The queue remains unchanged. Return success or underflow. // For Linked Queue 1. If (count > 0) 1. DataOut = front->data 2. Return success 2. Else 1. Return underflow 3. End QueueFront 25
  26. Contiguous Implementation Of Queue 26
  27. Contiguous Implementation Of Queue (cont.) Boundary conditions 27
  28. Contiguous Implementation Of Queue (cont.) • The physical model: a linear array with the front always in the first position and all elements moved up the array whenerver the front is deleted. • A linear array with two indices always increasing. • A circular array with front and rear indices and one position left vacant. • A circular array with front and rear indices and a Boolean flag to indicate fullness (or emptiness). • A circular array with front and rear indices and an integer counter of elements 28
  29. Contiguous Implementation Of Queue (cont.) Queue front rear data > count End Queue //Automatically Allocated Array Create() count 0 Pre none. Post An empty queue has been created. front -1 1. count = 0 rear -1 2. front = -1 3. rear = -1 end Create 29
  30. EnQueue & DeQueue Algorithm  EnQueue is successful when queue is not full.  DeQueue is successful when queue is not empty.  Regular cases: o EnQueue: only rear must be updated (increases by 1) o DeQueue: only front must be updated (increases by 1)  Irregular cases: o EnQueue an element to an empty queue: both rear and front must be updated (receive 0 value – 1st position in array). o DeQueue a queue having only one element: both rear and front must be updated (receive -1 value). Contiguous Implementation Contiguous  In any successful case, count must be updated. 30
  31. Queue Applications  Polynomial Arithmetic  Categorizing Data  Evaluate a Prefix Expression  Radix Sort  Queue Simulation 35
  32. Polynomial Arithmetic void PolynomialSum(val p1 ,val p2 , ref q ) Calculates q = p1 + p2 Pre p1 and p2 are two polynomials , each element in them consists of a coefficient and an exponent. Elements in a polynomial appear with descending exponents. Post q is the sum of p1 and p2 Uses Queue ADT data coefficient degree end data Count 4 front rear 36
  33. void PolynomialSum (val p1 , val p2 , ref q ) 1. q.Clear() 2. loop ( NOT p.isEmpty() OR NOT q.isEmpty() ) 1. p1.QueueFront(p1Data) 2. p2.QueueFront(p2Data) data 3. if (p1Data.degree > p2Data.degree) coefficient 1. p1.DeQueue() degree 2. q.EnQueue(p1Data) end data 4. else if (p2Data.degree > p1Data.degree) 1. p2.DeQueue() 2. q.EnQueue(p2Data) 5. else 1. p1.DeQueue() 2. p2.DeQueue() 3. if (p1Data.coefficient + p2Data.coefficient <> 0) 1. qData.coefficient = p1Data.coefficient + p2Data.coefficient 2. qData.degree = p1Data.degree 3. q.EnQueue(qData) End PolynomialSum 37
  34. Categorizing Data  Sometimes data need to rearrange without destroying their basic sequence.  Samples: • Ticket selling: several lines of people waiting to purchase tickets and each window sell tickets of a particular flight. • Delivery center: packages are arranged into queues base on their volumes, weights, destinations, Multiple Queue Application 38
  35. Categorizing Data (cont.) Rearrange data without destroying their basic sequence. 39
  36. Categorizing Data (cont.) 40
  37. Categorizing Data (cont.) Algorithm Categorize Groups a list of numbers into four groups using four queues. 1. queue1, queue2, queue3, queue4 2. loop (not EOF) 1. read (number) 2. if (number < 10) 1. queue1.EnQueue(number) 3. else if (number < 20) 1. queue2.EnQueue(number) 4. else if (number < 30) 1. queue3.EnQueue(number) 5. else 1. queue4.EnQueue(number) 3. // Takes data from each queue. 4. End Categorize 41
  38. Evaluate a Prefix Expression Use two queues in turns to evaluate a prefix expression front rear (q1) (q2) (q1) (q2) (q1)
  39. Radix Sort  Algorithm applied to data that use character string as key.  Very efficient sorting method that use linked queues.  Consider the key one character at a time  Devide the elements into as many sublists as there are possibilities for given character from the key.  To eleminate multiplicity of sublists, consider characters in the key from right to left. 43
  40. Radix Sort Sorted by letter 3 rat mop qp cat map car qr top cot qt tar rap 44
  41. Radix Sort (cont.) 45
  42. Radix Sort (cont.) Sorted by letter 2 qa q0 46
  43. Radix Sort (cont.) 47
  44. Radix Sort (cont.) Sorted by letter 1 qc qm qr qt 48
  45. Radix Sort (cont.) Sorted list 49