GuangchaoSun's Blog

1.3 Stack and Queues

发表于  |    |   分类于   |  

学习目标：

  • Bag,Queue和Stack的实现
  • 迭代器的使用

泛型(Generics)

An essential characteristic of collections ADTs is that we should be able to use them for any type of data.
有了泛型，我们只需要一份API（和一次实现）就能够处理所有类型的数据。

Autoboxing

类型参数必须被实例化为引用类型，因此Java有一种特殊机制来使泛型代码能够处理原始数据类型。

1
2
3
Stack<Integer> stack = new Stack<Integer>();
stack.push(17);       //自动装箱(int -> Integer)
int i = stack.pop();  //自动拆箱(Integer -> int)

Java automatically converts between a primitives type and its corresponding wrapper type in assgnment,method arguments,and arithmetic/logic expressions.

Iterable collections

1
2
3
Queue<Transcation> collection = new Queue<Transcation>();
for(Transcation t : collection)
    StdOut.println(t);

迭代

1
2
3
4
5
Iterator<String> i = collection.iterator();
while(i.hasNext()){
  String s = i.next();
  StdOut.println(s);
}

在任意可迭代的集合数据类型中需要实现：

  • 集合数据类型必须实现一个iterator方法并返回一个Iterator对象；
  • Iterator类必须包含两个方法：hasNext()和next()；

要使一个类可迭代，第一步就要在声明中加入implements Iterable<Item>，对应的接口java.lang.Iterable为:

1
2
3
public inerface Iterable<Item>{
  Iterator<Item> iterator();
}

然后在类中添加一个方法iterator()并返回一个迭代器Iterator<Item>。

Bags

  • A bag is a collection where removing items is not supported-its purpose is to provide clients with the abilty to collect items and then to iterate through the collected items
  • Stats is a bag client that reads a sequence of real numbers from standard input and prints out their mean and standard deviation

下面的练习是简单地计算标准输入中的所有double值得平均值和样本标准差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Stats {  
    public static void main(String[] args){  
        Bag<Double> numbers = new Bag<Double>();  
        while (!StdIn.isEmpty()){  
            numbers.add(StdIn.readDouble());  
        }  
        int n = numbers.size();
        double sum = 0.0;
        for(double x : numbers)
            sum += x;
        double mean = sum/n;
        sum = 0.0;
        for(double x:numbers){
            sum +=(x-mean)*(x-mean);
        }
        double stddev = Math.sqrt(sum/(n-1));
        StdOut.printf("Mean:   %.2f\n",mean);
        StdOut.printf("Std dev:%.2f\n",stddev);
    }
}

Pushdown stack

下压栈一个典型的用例就是算数表达式求值。

用例Reverse会把标准输入的所有整数逆序排列，无需预先知道整数有多少。

1
2
3
4
5
6
7
8
9
10
11
public class Reverse{
    public static void main(String[] args){
        Stack<Integer> stack = new Stack<Integer>();
        while(!StdIn.isEmpty()){
            Stack.push(StdIn.readInt());
        }
        for (int i : stack) {
            StdOut.println(i);
        }
    }
}

  • 创建泛型数组在Java中是不允许的，需要使用类型转换
    a = (Item[])new Object[cap];
  • 可迭代的集合数据类型需要实现：
    • 集合数据类型必须实现一个iterator()方法并返回一个iterator对象；
    • Iterator类必须包含两个方法：hasNext()(返回一个boolean值)和next()(返回集合中的一个泛型元素)

Linked List

A linked list is a recurive data that is either empty(null) or a reference to a node having a generic item and a reference to a linked list.
在表头插入结点先将first保存在结点oldfirst中，然后将一个新结点赋予first，并将它的item域设为not，next域设为oldfirst。
遍历

1
2
3
4
for(Node x = first, x != null, x = x.next)
{
        operation
}

  • 算法1.1-下压(LIFO)栈（能够动态调整数组大小的实现）: ResizingArrayStack
  • 算法1.2-下压堆栈（链表实现): Stack
  • 算法1.3-先进先出队列: Queue
  • 算法1.4-背包: Bag

Autoboxing Q + N

Q:How does the autoboxing handle the following code fragment?

1
2
Integer a = null;
int b = a;

N:It result in a run-time error.Primitive type store every value of their corresponding wrapper type except null

Q:Why does the first group of statements print true, but the second false?

1
2
3
4
5
6
7
8
9
10
11
Integer a1 = 100;  
Integer a2 = 100;  
System.out.println(a1 == a2);   // true  
Integer b1 = new Integer(100);  
Integer b2 = new Integer(100);  
System.out.println(b1 == b2);   // false  
Integer c1 = 150;  
Integer c2 = 150;  
System.out.println(c1 == c2);   // false

N:The second prints false because b1 and b2 are references to different Integer objects. The first and third code fragments rely on autoboxing. Surprisingly the first prints true because values between -128 and 127 appear to refer to the same immutable Integer objects (Java’s implementation of valueOf() retrieves a cached values if the integer is between -128 and 127), while Java constructs new objects for each integer outside this range.

exercise

  1. Write a stack client Parentheses.java that reads in sequence of left and right parentheses, braces, and brackets from standard input and uses a stack to determine whether the sequence is properly balanced. For example, your program should print true for [()]{}{[()()]()} and false for [(]).

  2. What does the following code fragment print when n is 50? Give a high-level description of what it does when presented with a positive integer n.
    十进制转二进制

  3. What does the following code fragment do to the queue q?

    Stack<String> s = new Stack<String>();
while(!q.isEmpty())
   s.push(q.dequeue());
while(!s.isEmpty())
   q.enqueue(s.pop());

    Reverse the item on the queue.

  4. Write a filter Program InfixToPostfix.java that converts an arithmetic expression from infix to postfix.

    public class InfixToPostfix {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if      (s.equals("+")) stack.push(s);
            else if (s.equals("*")) stack.push(s);
            else if (s.equals(")")) StdOut.print(stack.pop() + " ");
            else if (s.equals("(")) StdOut.print("");
            else                    StdOut.print(s + " ");
        }
        StdOut.println();
    }
}

  1. Write a program EvaluatePostfix.java that that takes a postfix expression from standard input, evaluates it, and prints the value. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to Evaluate.java.)

    public class EvaluatePostfix {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if      (s.equals("+")) stack.push(stack.pop() + stack.pop());
            else if (s.equals("*")) stack.push(stack.pop() * stack.pop());
            else stack.push(Integer.parseInt(s));
        }
        StdOut.println(stack.pop());
    }
}

  2. 编写一个类ResizingArrayQueue，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。

  1. Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N-1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus.java that takes M and N from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle).

    % java Josephus 2 7
1 3 5 0 4 2 6

  2. Copy a stack. Create a new constructor for the linked-list implementation of Stack.java so that Stack t = new Stack(s) makes t reference a new and independent copy of the stack s.(N)
    Recursive solution: create a copy constructor for a linked list starting at a given Node and use this to create the new stack.

    Node(Node x) {
   item = x.item;
   if (x.next != null) next = new Node(x.next);
}
public Stack(Stack<Item> s) { first = new Node(s.first); }

    Nonrecursive solution: create a copy constructor for a single Node object.

    Node(Node x) { this.item = x.item; this.next = x.next; }

public Stack(Stack<Item> s) {
   if (s.first != null) {
      first = new Node(s.first);
      for (Node x = first; x.next != null; x = x.next)
         x.next = new Node(x.next);
   }
}

  3. Expression evaluation with precedence. Write a problem EvaluateDeluxe.java that extends Evaluate.java to handle expression that are not fully parenthesized,using the standard precedence order for the operators +,-,*,/.

web exercise

21 List iterators.To implement previous() we can use a doubly-linked list. Program DoublyLinkedList.java

25 Adding a list to itself.What is the result of the following code fragment?

1
2
3
4
5
6
7
8
9
List list1 = new ArrayList();
List list2 = new ArrayList();
list1.add(list2);
list2.add(list1);
System.out.println(list1.equals(list2));
List list = new ArrayList();
list.add(list);
System.out.println(list.hashCode());

Answer. stack overflow. The Java documents say that”while it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hasCode methods are no longer well defined on such a list.”

31 Queue with two stacks.Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.
Solutuion:QueueWithTwoStacks.java

32-61未完待续