Exercise 6.1. Write a program that displays the first 50 prime numbers in descending order. Use a stack to store the prime numbers.

Exercise 6.2. Implement a method with signature transfer(S,T) that transfers all elements from stack S onto stack T, so that the elements that stars at the top of S is the first to be inserted onto T, and the element that at the bottom of S ends up at the top of T.

Exercise 6.3. Give a recursive method for removing all the elements from a stack.

Exercise 6.4. Implement a method with signature concatenate(LinkedQueue Q2) for the linkedQueue class that takes all elements of Q2 and appends them to the end of the original queue. The operation should run in O(1) times and should result in Q2 being an empty queue.

Exercise 6.5. Suppose that you have three nonempty stacks R, S and T. Describe a sequence of operations that results in S storing all elements originally in T below all of S’s original elements, with both sets of those elements in their original order. The final configuration for R should be the same as its original configuration. For example, if R = (1,2,3), S=(4,5) and T=(6,7,8,9). when ordered from bottom to top, then the final configuration should have R=(1,2,3) and S = (6,7,8,9,4,5).

Exercise 6.6. Implement a clone() method for the ArrayStack class

Exercise 6.7. Implement a clone() method for the ArrayQueue class

Exercise 6.8. When a share of common stock of some company is sold, the capital gain (or sometimes loss) is the difference between the share’s selling price and the price originally paid to buy it. This rule is easy to understand for a single share but if we sell multiple shares of stock bought over a long period of time, then we must identified the shares actually being sold. A standard accounting principle for identifying which shares of a stock were sold in such a case is to use a FIFO protocol — The shares sold are the ones that have been held the longest (indeed this is the default method built into several personal finance software packages). For example, suppose we buy 100 shares at $20 each on day 1, 20 shares at $24 on day 2, 200 shares at $36 on day 3 adn then sell 150 shares on day 4 at $30 each. Then applying the FIFO protocol means that of the 150 shares sold, 100 were bought on day 1, 20 were bought on day 2, and 30 were bought on day 3. The capital gain in this case would therefore be 100*10 + 20*6 + 30*(-6) or $940. Write a program that takes as input a sequence of transactions of the form “buy x shares at $y each” or “sell x shares at $y each”, assuming that the transaction occur on consecutive days and the value of x and y are integers. Given this input sequence, the output should be the total capital gain (or loss) for the entire sequence, using the FIFO protocol to identify the shares.

Exercise 6.9. Consider the generic queue class defined below. This class is implemented using composition (or the adapter design pattern). Define a new queue class that extends java.util.LinkedList.


public class GenericQueue < E > {
  private java.util.LinkedList < E > list
      = new java.util.LinkedList < >();
  public void enqueue(E e){
    list.addLast(e);
}
  public E dequeue(){
    return list.removeFirst();
}
  public int getSize(){
    return list.size();
}
@ override 
  public String toString(){
    return "Queue: " + list.toString(); 
}
}

Exercise 6.10.
Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if “(exp1) op (exp2)” is a normal fully parenthesized expression whose operation is “op”, the postfix version of this is “pexp1 pexp2 op” where pexp1 is the postfix version of exp1 and pexp2 is the postfix version of exp2. The postfix version of a single number or variable is just that number or variable. So, for example, the postfix version of “((5+2)*(8-3))/4” is “5 2 + 8 3 – * 4 /”. Give a non recursive program that can input an expression in postfix notation and output its value.

Exercise 6.11.
Design an ADT for a two color, double-stack ADT that consists of two stacks — one “red” and one “blue” — and has as its operations color coded versions of the regular stack ADT operations. For example, this ADT should support both a redPush operation and a bluePush operation. Give an efficient implementation of this ADT using a single array whose capacity is set at some value N that is assumed to be always larger than the sizes of the red and blue stacks combined.

Exercise 6.12.
Stacks are often used to provide “undo” support in applications like a Web browser or text editor. While support for undo can be implemented with an unbounded stack, many applications provide only limited support for such an undo history, with a fixed-capacity stack. When push
is invoked with the stack at full capacity, rather than throwing an exception, a
more typical semantic is to accept the pushed element at the top while “leaking”
the oldest element from the bottom of the stack to make room. Give an implementation of such a LeakyStack abstraction, using a circular array