Complete the body of this function. Use a queue of characters to store the input line as it is being read.

size_t counter( )

// Precondition: There is a line of input waiting to be read from cin.

// Postcondition: A line of input has been read from cin, up to but not

// including the newline character. The return value of the function

// is the number of times that the LAST character of the line appeared

// somewhere in this line.

// EXAMPLE Input: ABBXDXXZX

// The value returned by counter would be 4 for this input since there

// are 4 X's in the input line.

{

size_t answer = 0;

queue q;

I am going to execute this code with THREE inserts and ONE get_front:

queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout << s.get_front( );

Suppose that s is represented by a circular array. Draw the state of these private member variables of s after the above code:

_______ __________________________________

first| | data| | | | | |

|_______| |______|______|______|______|______|

[0] [1] [2] [3] [4]

I am going to execute this code with THREE insert and ONE get_front:

queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout << s.get_front( );

Suppose that s is represented by a linked list. Draw the state of the private member variables of s after the above code:

_______

front_ptr| |

|_______|

_______

rear_ptr| |

|_______|

Describe why it is a bad idea to implement a linked list version a queue which uses the head of the list as the rear of the queue.

Suppose that you want to implement the priority_queue so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:

template

class priority_queue

{

typedef Item value_type;

void push(const Item&x entry);

value_type top( );

...

private:

node *head_ptr;

};

(A) Write ONE sentence to describe how the insert member function will work (with constant time). (B) Then implement the top function (which will have linear worst-case time). In your implementation, you DO NOT have to worry about items with equal priority (they may come out of the prioirty queue however you like, without necessarily having FIFO behavior). You may also assume that these two toolkit functions have been modified to work with the priority_queue's node:

void list_head_remove(Node*& head_ptr); // Removes head node of a list

void list_remove(Node* precursor); // Removes node after *precursor

Multiple Choice

One difference between a queue and a stack is:

A. Queues require dynamic memory, but stacks do not.

B. Stacks require dynamic memory, but queues do not.

C. Queues use two ends of the structure; stacks use only one.

D. Stacks use two ends of the structure, queues use only one.

If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

A. ABCD

B. ABDC

C. DCAB

D. DCBA

Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).

A. rand() < P

B. rand() > P

C. rand() < P * RAND_MAX

D. rand() > P * RAND_MAX

Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the push member function place the new entry in the array?

A. data[1]

B. data[2]

C. data[11]

D. data[12]

Consider the implementation of the queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).

A. The constructor would require linear time.

B. The get_front function would require linear time.

C. The insert function would require linear time.

D. The is_empty function would require linear time.

In the linked list implementation of the queue class, where does the push member function place the new entry on the linked list?

A. At the head

B. At the tail

C. After all other entries that are greater than the new entry.

D. After all other entries that are smaller than the new entry.

In the circular array version of the queue class (with a fixed-sized array), which operations require linear time for their worst-case behavior?

A. front

B. push

C. empty

D. None of these operations require linear time.

In the linked-list version of the queue class, which operations require linear time for their worst-case behavior?

A. front

B. push

C. empty

D. None of these operations require linear time.

If data is a circular array of CAPACITY elements, and last is an index into that array, what is the formula for the index after last?

A. (last % 1) + CAPACITY

B. last % (1 + CAPACITY)

C. (last + 1) % CAPACITY

D. last + (1 % CAPACITY)

I have implemented the queue with a circular array, keeping track of first, last, and count (the number of items in the array). Suppose first is zero, and last is CAPACITY-1. What can you tell me about count?

A. count must be zero.

B. count must be CAPACITY.

C. count could be zero or CAPACITY, but no other values could occur.

D. None of the above.

I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?

A. Neither changes

B. Only front_ptr changes.

C. Only rear_ptr changes.

D. Both change.

I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?

A. Neither changes

B. Only front_ptr changes.

C. Only rear_ptr changes.

D. Both change.

Suppose top is called on a priority queue that has exactly two entries with equal priority. How is the return value of top selected?

A. The implementation gets to choose either one.

B. The one which was inserted first.

C. The one which was inserted most recently.

D. This can never happen (violates the precondition)