下压堆栈的实现方式

算法第四版学习笔记一(下压堆栈的实现)

使用数组和链表两种实现方式
数组实现方式:

 1package ren.laughing.algorithms;
 2
 3import java.util.Iterator;
 4
 5/**
 6 * 下压堆栈(数组实现)
 7 * 
 8 * @author Laughing_Lz
 9 * @createTime 2018年9月2日
10 * @param <E>
11 */
12public class ResizingArrayStack<Eimplements Iterable<E{
13
14  private E[] items = (E[]) new Object[1];
15  private int N = 0;
16
17  public boolean isEmpty() {
18    return N == 0;
19  }
20
21  public int size() {
22    return N;
23  }
24
25  /**
26   * 动态调整数组大小 保持数组大小与栈大小之比小于一个常数
27   * 
28   * @param max 调整后的数组长度
29   */
30  public void resize(int max) {
31    E[] temp = (E[]) new Object[max];
32    for (int i = 0; i < N; i++) {
33      temp[i] = items[i];
34    }
35    items = temp;
36  }
37
38  public void push(E item) {
39    if (N == items.length) {
40      resize(2 * items.length);
41    }
42    items[N++] = item;
43  }
44
45  public E pop() {
46    E item = items[--N];
47    // 避免对象游离
48    items[N] = null;
49    if (N > 0 && N == items.length / 4) {
50      resize(items.length / 2);
51    }
52    return item;
53  }
54
55  /**
56   * 实现foreach遍历
57   */
58  @Override
59  public Iterator<E> iterator() {
60    return new StackIterator();
61  }
62
63  private class StackIterator implements Iterator<E{
64    private int i = N;
65
66    @Override
67    public boolean hasNext() {
68      return i > 0;
69    }
70
71    @Override
72    public E next() {
73      return items[--i];
74    }
75
76  }
77}

链表实现方式:

 1package ren.laughing.algorithms;
 2
 3import java.util.Iterator;
 4
 5/**
 6 * 下压堆栈(链表实现)
 7 * 
 8 * @author Laughing_Lz
 9 * @createTime 2018年9月2日
10 * @param <E>
11 */
12public class Stack<Eimplements Iterable<E{
13
14  private Node first;
15  private int N;
16
17  private class Node {
18    E item;
19    Node next;
20  }
21
22  public boolean isEmpty() {
23    return N == 0;
24  }
25
26  public int size() {
27    return N;
28  }
29
30  public void push(E item) {
31    Node oldfirst = first;
32    first = new Node();
33    first.item = item;
34    first.next = oldfirst;
35    N++;
36  }
37
38  public E pop() {
39    E item = first.item;
40    first = first.next;
41    N--;
42    return item;
43  }
44
45  /**
46   * 实现foreach遍历
47   */
48  @Override
49  public Iterator<E> iterator() {
50    return new StackIterator();
51  }
52
53  private class StackIterator implements Iterator<E{
54
55    private Node current = first;
56
57    @Override
58    public boolean hasNext() {
59      return first != null;
60    }
61
62    @Override
63    public E next() {
64      E item = current.item;
65      current = first.next;
66      return item;
67    }
68
69  }
70}

发表评论

电子邮件地址不会被公开。 必填项已用*标注