queue

Property: FIFO

Operation:

push_back, pop_front

Q.add(obj), Q.remove(&obj)

------

STL style

Q.push(obj);

Q.pop();

obj = Q.front();

obj = Q.back();

must_have:

maxsize, head, tail;

// head and tail are array index

array

;

// either static or dynamic

nice_to_have: count;

circular queue, circular buffer

(head++) % maxsize

(tail++) % maxsize

issue:

empty condition: head==tail

full condition: head==tail

how to distinguish empty and full conditions?

must_have: head, tail;

// head and tail are object node pointers

no need for maxsize

do we have circular issue?

do we have empty and full issue?

linked list is dynamic, there is no full case

if both head and tail are NULL, it is empty

need a count?

nice_to_have: count

Application of Queue in Simulation

many queue applications need priority

Implementation variations

implement with an ordered queue
- one queue with elements ordered by priority
- add/push needs to put element in proper priority order
- pop from top is always highest priority
- strict ordering
implement with multiple queues
- each priority uses one queue
implement with heap
- if all we need is ONLY to determine the highest priority element
- tree like algorithm with array based implementation
- elegant and fast

Page updated

Google Sites

Report abuse