CONCEPT EXERCISES
8.1 What advantage was obtained by implementing the List interface before declaring the Stack class? Get the solution of 8.1
8.2 Suppose we define:
Queue<Integer> queue = new LinkedList<Integer>();
Show what the LinkedList object (referenced by) queue will look like after each of the following messages is sent:
a. queue.add (2000);
b. queue. add (1215);
c. queue. add (1035);
d. queue. add (2117);
e. queue.remove();
f. queue. add (1999);
g. queue.remove(); Get the solution of 8.2
8.3 Re-do Exercise 8.2, parts a through g, for a stack instead of a queue. Start with
Stack<Integer> stack = new Stack<Integer>();
stack.push (2000); Get the solution of 8.3
8.4 Suppose that elements "a", "b", "c", "d", "e" are pushed, in that order, onto an initially empty stack, which is then popped four times, and as each element is popped, it is enqueued into an initially empty queue.
If one element is then dequeued from the queue, what is the next element to be dequeued? Get the solution of 8.4
8.5 Use a stack of activation records to trace the execution of the recursive fact method after an initial call of fact (4). Here is the method definition:
/**
/**
* Calculates n!.
*
* @param n the integer whose factorial is calculated.
*
* @return n!.
*
*/
protected static long fact (int n)
{
if (n <= 1)
return 1;
return n ∗ fact (n - 1);
} // method fact Get the solution of 8.5
8.6 Translate the following expressions into postfix notation:
1. x + y ∗ z
2. (x + y) ∗ z
3. x − y − z ∗ (a + b)
4. (a + b) ∗ c − (d + e ∗ f/((g/h + i − j) ∗ k))/ r
Test your answers by running the InfixToPostfix project in Lab 15. Get the solution of 8.6
8.7 Translate each of the expressions in Programming Exercise 8.6 into prefix notation. Get the solution of 8.7
8.8 An expression in postfix notation can be evaluated at run time by means of a stack. For simplicity, assume that the postfix expression consists of integer values and binary operators only. For example, we might have the following postfix expression:
8 5 4 + ∗ 7 −
The evaluation proceeds as follows: When a value is encountered, it is pushed onto the stack. When an operator is encountered, the first—that is, top—and second elements on the stack are retrieved and popped, the operator is applied (the second element is the left operand, the first element is the right operand) and the result is pushed onto the stack. When the postfix expression has been processed, the value of that expression is the top (and only) element on the stack.
For example, for the preceding expression, the contents of the stack would be as follows:
4
5 5
8 8 8
----- ----- ----- -----
9 7
8 72 72 65
----- ----- ----- -----
Convert the following expression into postfix notation and then use a stack to evaluate the expression:
5 + 2 ∗ (30 − 10/5) Get the solution of 8.8
PROGRAMMING EXERCISES
8.1 Declare and test the PureStack class (see Section 8.1.2) with a LinkedList field.
Hint: Each of the definitions is a one-liner. Get the solution of 8.1
8.2 Declare and test the PureStack class (see Section 8.1.2) with an ArrayList field.
Hint: For the sake of efficiency, the top of the stack should be at index size() - 1. Get the solution of 8.2
8.3 Develop an iterative, stack-based version of the ways method in Programming Exercise 5.7. Test your method with unit testing. Get the solution of 8.3
