Chapter 20

Question 1

queue

Answer 1

An ordered set of objects waiting for a service of some kind.

Question 2

Queue

Answer 2

An ADT that performs the operations one might perform on a queue.

Question 3

queueing policy

Answer 3

The rules that determine which member of a queue is removed next.

Question 4

FIFO

Answer 4

First In, First Out, a queueing policy in which the first member to arrive is the first to be removed.

Question 5

priority queue

Answer 5

A queueing policy in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed.

Question 6

Priority Queue

Answer 6

An ADT that defines the operations one might perform on a priority queue.

Question 7

linked queue

Answer 7

An implementation of a queue using a linked list.

Question 8

constant time

Answer 8

An operation whose runtime does not depend on the size of the data structure.

Question 9

linear time

Answer 9

An operation whose runtime is a linear function of the size of the data structure.