True/False (10)

Chapter 10 - Queues, Deques, and Priority Queues

1. Queues are used in operating systems.

2. The item most recently added to a queue is at the back of the queue.

3. Unlike a stack, a queue does not restrict access to its entries.

4. The Java Class Library interface for Queue has no operation to modify the contents of the front

   entry.

5. You can push, pop and get items at either end of the ADT deque.

6. The Queue interface extends the Deque interface.

7. A priority queue cannot have null entries

8. The null value can be used to signal failure to remove or retrieve an entry from a priority queue

   when it is empty.

9. The Java Class Library ADT PriorityQueue uses the compareTo method to determine how to

   order entries.

10. The ArrayDeque class implements the Stack interface.

Short Answer (5)

1. Draw the contents of the queue after the following statements execute. Clearly label the front and back of the queue.

QueueInterface bankLine = new LinkedQueue<>(); bankLine .enqueue(John); bankLine .enqueue(Matthew); String next = bankLine .dequeue();

bankLine .enqueue(Drew); bankLine .enqueue(Heather); bankLine .enqueue(David); next = bankLine .dequeue();

2. Draw the contents of the queue after the following statements execute. Clearly label the front and back of the queue.

QueueInterface bankLine = new LinkedQueue<>(); bankLine .enqueue(John); bankLine .enqueue(Matthew); String next = bankLine .dequeue();

next = bankLine .dequeue(); bankLine .enqueue(Drew); bankLine .enqueue(Heather); next = bankLine .dequeue(); bankLine .enqueue(David); next = bankLine .dequeue();

3. Describe what happens when the following code is executed.

QueueInterface bankLine = new LinkedQueue<>(); bankLine .enqueue(John); bankLine .enqueue(Matthew); String next = bankLine .dequeue();

bankLine .enqueue(Heather); next = bankLine .dequeue(); next = bankLine .dequeue(); bankLine .enqueue(Nancy); next = bankLine .dequeue(); next = bankLine .dequeue();

4. Draw the contents of the deque after the following statements execute. Clearly label the front and back of the deque.

DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToFront(Jack);waitingLine.addToFront(Rudy); waitingLine.addToBack(Larry); waitingLine.addToBack(Sam);

String name = waitingLine.getFront();

5. Draw the contents of the deque after the following statements execute. Clearly label the front and back of the deque.

DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToBack(Adam); waitingLine.addToFront(Rudy); waitingLine.addToBack(Larry); waitingLine.addToBack(Sam); waitingLine.addtoFront(Jack);

String name = waitingLine.getFront(); name = getFront();

Multiple Choice (30)

1. Which of the following real-world events could be simulated using a queue?

   1. bank line

   2. a shared network printer

   3. restaurant reservation list

   4. all of the above

2. The ____ ADT organizes its entries according to the order in which they were added.

   1. queue

   2. stack

   3. list

   4. priority queue

3. What a. first-in first-out

type of behavior defines a queue?

2. first-in last-out

3. last-in first-out

4. none of the above

4. How does a queue organize it items?

   1. according to the order in which they were added

   2. by priority

   3. alphabetically

   4. randomly

5. Where does a queue add new items?

   1. at the back

   2. at the front

   3. in the middle

   4. randomly

6. Where will you find the item added earliest to a queue?

   1. at the front

   2. at the back

   3. in the middle

   4. randomly

7. The method for adding a new item to the back of a queue is called a. enqueue

2. dequeue

3. getFront

4. none of the above

8. The method for removing an item from the front of a queue is called

   1. dequeue

   2. enqueue

   3. getFront

   4. none of the above

9. The method for retrieving the queues front entry without altering the queue is called

   1. getFront

   2. enqueue

   3. dequeue

   4. none of the above

10. A common alias for the queue method enqueue is

    1. put

    2. add

    3. insert

    4. all of the above

11. A common alias for the queue method dequeue is

    1. get

    2. remove

    3. delete

    4. all of the above

12. A common alias for the queue method getFront is

    1. peek

    2. get

    3. put

    4. all of the above

13. The dequeue method

    1. throws an exception if the queue is empty

    2. returns the item at the front of the queue

    3. removes the item at the front of the queue

    4. all of the above

14. After the following statements execute, what item is at the front of the queue? QueueInterface zooDelivery = new LinkedQueue<>();

zooDelivery .enqueue(lion); zooDelivery .enqueue(tiger); zooDelivery .enqueue(cheetah); String next = zooDelivery .dequeue(); next = zooDelivery .dequeue(); zooDelivery .enqueue(jaguar);

1. cheetah

2. jaguar

3. tiger

4. lion

15. After the following statements execute, what item is at the back of the queue? QueueInterface zooDelivery = new LinkedQueue<>(); zooDelivery .enqueue(lion); zooDelivery .enqueue(tiger);

zooDelivery .enqueue(cheetah); String next = zooDelivery .dequeue(); next = zooDelivery .dequeue(); zooDelivery .enqueue(jaguar);

1. jaguar **

2. cheetah

3. tiger

4. lion

16. When a. time-driven simulation

a counter enumerates simulated time units, it is called a(n)

2. clock simulation

3. event-driven simulation

4. all of the above

17. In order to modify the front entry of a queue

    1. you need a set method defined

    2. you need to dequeue the front entry, modify the contents, and then use the requeue

       method to place it back on the front of the queue

    3. you cannot modify it under any circumstances

    4. none of the above

18. The Java Class Library interface Queue method to put an entry on the back of a queue that throws an exception of the method fails is

a. add b. offer c. put d. poll

19. The Java Class Library interface Queue method to put an entry on the back of a queue that returns false if the method fails is

    a. offer b. add c. put d. poll

20. The Java Class Library interface Queue method that retrieves and removes the entry at the front of a queue and throws a NoSuchElementException if the queue was empty is

    a. remove b. poll c. retrieve d. get

21. The Java Class Library interface Queue method that retrieves and removes the entry at the front of a queue and returns null if the queue was empty is

    a. poll b. remove c. retrieve d. get

22. The Java Class Library interface Queue method that retrieves the entry at the front of a queue

but throws a NoSuchElementException if the queue was empty is

a. empty b. peek c. poke d. look

23. The Java Class Library interface Queue method that retrieves the entry at the front of a queue but returns null if the queue was empty is

a. peek b. empty c. poke d. look

24. A deque ADT behaves a. like a queue

2. like a stack

3. both a & b

4. none of the above

25. What item is at the front of the list after these statements are executed?

    DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToFront(Jack); waitingLine.addToFront(Rudy); waitingLine.addToBack(Larry); waitingLine.addToBack(Sam);

    String name = waitingLine.getFront();

    a. Jack b. Rudy c. Larry d. Sam

26. What item is at the front of the list after these statements are executed?

    DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToFront(Jack); waitingLine.addToFront(Rudy); waitingLine.addToBack(Larry); waitingLine.addToBack(Sam);

    String name = waitingLine.getBack();

    a. Rudy b. Jack c. Larry d. Sam

27. The ADT priority queue organizes objects a. according to priority of the objects b. alphabetically c. from front to back

    d. from back to front

28. What item is at the front of the list after these statements are executed?

    DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToFront(Jack);

waitingLine.addToBack(Rudy); waitingLine.addToBack(Larry); waitingLine.addToFront(Sam); String name = waitingLine.getFront(); name = getBack(); waitingLine.addtoBack(Adam);

a. Jack b. Rudy c. Adam d. Sam

29. What item is at the front of the list after these statements are executed?

    DequeInterface waitingLine = new LinkedDeque<>(); waitingLine.addToBack(Adam); waitingLine.addToFront(Rudy); waitingLine.addToBack(Larry); waitingLine.addToBack(Sam); waitingLine.addtoFront(Jack);

    String name = waitingLine.getFront(); name = getFront();

    a. Adam b. Rudy c. Jack d. Sam

30. The _____ ADT that has operations to add, remove, or retrieve entries at both the front and back of a queue is called a

    1. deque

    2. reversible queue

    3. reversible stack

    4. all of the above