Java Software Structures, 4th Edition Exercise Solutions, Ch. 3
Chapter 3 Exercise Solutions
EX 3.1 Compare and contrast data types, abstract data types, and data structures.
A data type is a set of values and operations defined on those values. An abstract
EX 3.2 List the collections in the Java Collections API and mark the ones that are
covered in this text.
EX 3.3 Define the concept of abstraction and explain why it is important in software
development.
Abstraction hides certain details at certain times. Most modern software is far too
EX 3.4 Hand trace a stack X through the following operations:
X.push(new Integer(4));
X.push(new Integer(3));
Integer Y = X.pop();
X.push(new Integer(7));
The stack, after each operation (top of stack on the left):
4
3 4
4
EX 3.5 Given the resulting stack X from the previous exercise, what would be the
result of each of the following?
Y = X.peek();
The value of Y would be 9 and the stack would remain unchanged.
EX 3.6 What should be the time complexity of the isEmpty(), size(), and toString()
methods?
Using the count variable, the size method is O(1) and simply returns the value of count.
EX 3.7 Show how the undo operation in a word processor can be supported by the
use of a stack. Give specific examples and draw the contents of the stack after
various actions are taken.
Suppose the following actions were taken, in order, in the word processor: (1) type the
title, (2) make the title bold, (3) delete the third paragraph, and (4) center the author’s
EX 3.8 In the postfix expression evaluation example, the two most re- cent operands
are popped when an operator is encountered so that the sub-expression can
be evaluated. The first operand popped is treated as the second operand in the
sub-expression, and the second operand popped is the first. Give and explain
an example that demonstrates the importance of this aspect of the solution.
For operations such as addition and multiplication, the order of operands does not
matter, but for subtraction and division, for instance they do. So the postfix expression
EX 3.9 Draw an example using the five integers (12, 23, 1, 45, 9) of how a stack could
be used to reverse the order (9, 45, 1, 23, 12) of these elements.
The five values would be pushed onto the stack in order, yielding (with the top of the
stack on the left):
EX 3.10 Explain what would happen to the algorithms and the time complexity of an
array implementation of the stack if the top of the stack were at position 0.
A array-based stack implementation can take advantage of the fact that all processing
on the stack takes place on one end. By implementing it so that the bottom of the stack