Chapter 20 Stacks and Queues

A ______ is a collection of items that allows addition and removal of items in a last-infirst-out manner.

stack

A stack can be viewed as an abstract data type that supports three main operations, traditionally called ____ ______ ____ ____.

push, peek, and pop

The _____ operation takes a single item and adds it to the top of the stack

push

The ____ operation returns the item currently at the top of the stack, but does not remove it.

peek

The _____ operation removes (and returns) the item currently stored at the top of the stack.

pop

A ______is just a list that enforces last-in-first-out access

stack

1. 20.1 What is the common name for an operation that adds an element to a stack?

push

2. 20.2 What is the common name for an operation that removes an element from a stack?

pop

3. 20.3 What should a stack method for removing an item do when the stack is empty?

Throw an exception

4. 20.4 In what order are elements added and removed from a stack?

Last in first out

5. 20.5 Cite an example from everyday life where a collection of items behaves like a stack.

Some examples are a stack of plates or trays in a cafeteria, a line of cars parked single file in a narrow driveway, and a person wearing an undershirt, a shirt, a jacket, and an overcoat.

A ______ is a collection of items that is accessed in a first-in-first-out fashion.

queue

add a new item x to the rear of the queue

enqueue(x)

remove and return the item at the front of the queue

dequeue( )

check if the queue is empty

empty( )

return, but do not remove, the item at the front of the queue

peek( )

1. 20.6 What is the common name for an operation that adds an element to a queue?

enqueue

2. 20.7 In what order are elements added and removed from a queue?

first in first out

3. 20.8 Cite an example of a queue from everyday life.

Some examples are a grocery store checkout line, a line of cars going through a toll booth.

4. 20.9 In an array implementation of a queue, why is it necessary to treat the array as a circular buffer?

By the time the add operation reaches the end of the array, the remove operation may have emptied the spaces of the beginning of the array, allowing the add operation to wrap around and start storing elements at the beginning. Similarly, when the remove empties spaces at the end of the array, it should wrap around to the beginning.

1. A collection that is accessed in first-in-first-out fashion is called .
1. a stack
2. a queue
3. a linked list
4. an array-based collection

a queue

2. A collection that is accessed in last-in-first-out fashion is called .
1. a stack
2. a queue
3. a linked list
4. none of the above

a stack

3. The order in which cars go through a toll booth is best described as .
1. a stack
2. a queue
3. a linked list
4. none of the above

a queue

4. The concept of seniority, which some employers use to hire and fire workers is .
1. a stack
2. a queue
3. a linked list
4. none of the above

a stack

5. The stack method that returns an element from the stack without removing it is .
1. pop
2. push
3. peek
4. spy

peek

6. If the stack method push is called on an empty stack, .
1. it throws an EmptyStackException
2. it adds its argument to the stack
3. it calls the stack method empty
4. none of the above

it adds its argument to the stack

7. True or False: You can use the JCF stack to directly create a stack of int.

False

8. True or False: If pop is called on an empty stack, it will not return until the user puts something on the stack.

False

9. True or False: When using an array to implement a stack, the push method will wrap around to the beginning of the stack when it reaches the end.

False

10. True or False: In a linked implementation of a queue, the references front and rear can only be equal if the queue is empty.

False