The queue
and priority_queue
adaptors are defined in the queue
header. Table 9.19 lists the operations supported by these types.
The library queue
uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back and objects leaving the queue are removed from the front. A restaurant that seats people in the order in which they arrive is an example of a FIFO queue.
A priority_queue
lets us establish a priority among the elements held in the queue. Newly added elements are placed ahead of all the elements with a lower priority. A restaurant that seats people according to their reservation time, regardless of when they arrive, is an example of a priority queue. By default, the library uses the <
operator on the element type to determine relative priorities. We’ll learn how to override this default in § 11.2.2 (p. 425).
Exercise 9.52: Use a stack
to process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis, pop
elements down to and including the open parenthesis off the stack
. push
a value onto the stack
to indicate that a parenthesized expression was replaced.