Queue.md (832B)
1 +++ 2 title = "Queue" 3 +++ 4 5 # Queue 6 7 ## Queue 8 9 - FIFO 10 - enqueue to end, dequeue from start 11 - implement using circular array 12 - Q.head is front of queue 13 - Q.tail is end of queue 14 - if is empty, Q.head == Q.tail 15 - check for overflow/underflow and rap appropriately 16 17 ## Priority queue 18 19 - keys are totally ordered, most important element is served first 20 - min-priority: minimum is most important 21 - max-priority: maximum is most important 22 - add: insert(priority queue, element) — O(logn) 23 - increase-key: increases key of an element to a given key 24 - maximum: gives element with max key 25 - extract-max: removes and returns element with max key — O(logn) 26 - implement with a heap: 27 - either max-heap or min-heap, depending on the type of queue needed 28 - max/min can be in ϴ(1) by returning first element of max/min-heap