A Concise Introduction to Data Structures Using Java

1. import java.util.EmptyStackException;
   
2. 2
   
3. 3  public class IntArrayStack implements IntStack {
   
4. 4         private int top = -1;
   
5. 5         private int[] data;
   
6. 6         private static final int DEFAULT_CAPACITY = 10;
   
7. 7
   
8. 8         public IntArrayStack() {
   
9. 9         data = new int[DEFAULT_CAPACITY];
   
10. 10         }
    
11. 11
    
12. 12         public void push(int item) {
    
13. 13         if (top == data.length - 1) resize(2 * data.length);
    
14. 14         data[++top] = item;
    
15. 15         }
    
16. 16
    
17. 17         public int pop() {
    
18. 18         if (isEmpty()) throw new EmptyStackException();
    
19. 19         return data[top--];
    
20. 20         }
    
21. 21
    
22. 22         private void resize(int newCapacity) {
    
23. 23         int[] newData = new int[newCapacity];
    
24. 24         for (int i = 0; i <= top; i++) {
    
25. 25         newData[i] = data[i];
    
26. 26         }
    
27. 27         data = newData;
    
28. 28         }
    
29. 29
    
30. 30         public static void main(String[] args) {
    
31. 31         IntStack s = new IntArrayStack();
    
32. 32         for (int i = 0; i < 5; i++) {
    
33. 33         s.push(i);
    
34. 34         }
    
35. 35         }
    
36. 36  }

复制代码

1. A Node class is used to represent the nodes that link together to form linked
   
2. lists. A typical Node class has only its two fields, data and next, and a
   
3. constructor, as in Listing 3.3.
   
4. Listing 3.3: Node
   
5. 1  public class Node {
   
6. 2         private int data;
   
7. 3         private Node next;
   
8. 4
   
9. 5         public Node(int data, Node next) {
   
10. 6         this.data = data;
    
11. 7         this.next = next;
    
12. 8         }
    
13. 9  }
    
14. To implement a stack, we only need two linked list operations: insert and
    
15. remove from the front of the list.

复制代码

1. Listing 3.4: Integer Linked Stack
   
2. 1  public class IntLinkedStack implements IntStack {
   
3. 2         private Node top;
   
4. 3
   
5. 4         public void push(int item) {
   
6. 5         top = new Node(item, top);
   
7. 6         }
   
8. 7
   
9. 8         public int pop() {
   
10. 9         int result = top.data;
    
11. 10         top = top.next;
    
12. 11         return result;
    
13. 12         }
    
14. 13
    
15. 14         private class Node {
    
16. 15         private int data;
    
17. 16         private Node next;
    
18. 17
    
19. 18         private Node(int data, Node next) {
    
20. 19         this.data = data;
    
21. 20         this.next = next;
    
22. 21         }
    
23. 22         }
    
24. 23  }

复制代码

1. Inside a generic class or interface definition, the type parameter and the
   
2. generic type itself may be used for declarations as if they were regular types.
   
3. (There is an important limitation with arrays that will be addressed in the
   
4. next section.) For example, Listing 4.1 contains code for a generic Node class.
   
5. Listing 4.1: Generic Node
   
6. 1  public class Node<T> {
   
7. 2         private T data;
   
8. 3         private Node<T> next;
   
9. 4
   
10. 5         public Node(T data, Node<T> next) {
    
11. 6         this.data = data;
    
12. 7         this.next = next;
    
13. 8         }
    
14. 9  }

复制代码

1. Listing 4.3: Generic Array Stack
   
2. 1  public class ArrayStack<E> implements Stack<E> {
   
3. 2         private E[] data;
   
4. 3         private int top = -1;
   
5. 4         private static final int DEFAULT_CAPACITY = 10;
   
6. 5
   
7. 6         @SuppressWarnings("unchecked")
   
8. 7         public ArrayStack() {
   
9. 8         data = (E[]) new Object[DEFAULT_CAPACITY];
   
10. 9         }
    
11. 10
    
12. 11         public E pop() {
    
13. 12         E result = data[top];
    
14. 13         data[top--] = null;
    
15. 14         return result;
    
16. 15         }
    
17. 16  }

复制代码

1. Listing 4.4: Evaluate Postfix (Pseudocode)
   
2. 1  For each term in expression
   
3. 2         If term is an operator
   
4. 3         Pop second operand
   
5. 4         Pop first operand
   
6. 5         Apply operator to operands and push result
   
7. 6         Else
   
8. 7         Push operand onto stack
   
9. 8  Pop result

复制代码

1. Listing 4.5 outlines a similar algorithm to translate infix to postfix. It uses a
   
2. stack to hold operators and is slightly more complex than Listing 4.4 because
   
3. of the inner loop in lines 3 and 4. This algorithm assumes there are no
   
4. parentheses in the infix expression.
   
5. Listing 4.5: Infix to Postfix (Pseudocode)
   
6. 1  For each term in expression
   
7. 2         If term is an operator
   
8. 3         Pop all operators of same or higher precedence
   
9. 4         and copy each to output
   
10. 5         Push this operator onto stack
    
11. 6         Else
    
12. 7         Copy operand to output
    
13. 8  Pop remaining operators and copy to output

复制代码

1. Listing 4.6: Operator Rank
   
2. 1  public class Expression {
   
3. 2         private static int rank(String op) {
   
4. 3         switch (op) {
   
5. 4         case "*":
   
6. 5         case "/":
   
7. 6         return 2;
   
8. 7         case "+":
   
9. 8         case "-":
   
10. 9         return 1;
    
11. 10         default:
    
12. 11         return -1;
    
13. 12         }
    
14. 13         }
    
15. 14  }

复制代码

1. Listing 4.7: Infix to Postfix
   
2. 1  // Add to Expression class
   
3. 2  private static final String SPACE = " ";
   
4. 3
   
5. 4  public static String toPostfix(String expr) {
   
6. 5         StringBuilder result = new StringBuilder();
   
7. 6         Stack<String> operators = new ArrayStack<>();
   
8. 7         for (String token : expr.split("\\s+")) {
   
9. 8         if (rank(token) > 0) {
   
10. 9         while (!operators.isEmpty() &&
    
11. 10         rank(operators.peek()) >= rank(token)) {
    
12. 11         result.append(operators.pop() + SPACE);
    
13. 12         }
    
14. 13         operators.push(token);
    
15. 14         } else {
    
16. 15         result.append(token + SPACE);
    
17. 16         }
    
18. 17         }
    
19. 18         while (!operators.isEmpty()) {
    
20. 19         result.append(operators.pop() + SPACE);
    
21. 20         }
    
22. 21         return result.toString();
    
23. 22  }

复制代码