多种数据结构的Java实现

多种数据结构的Java实现

class Node {
  Object item; Node next;
    Node (Object v) {
     item = v; next = null;
  }
}

头指针，空尾指针
初始化：head = null;
在x后插入t：
if ( x == null)
{ head = t; head.next = null; }
else { t.next = x.next; x.next = t; }
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head; t != null; t = t.next )

检查链表是否为空：if ( head == null )
空头结点，空尾指针
初始化：head = new Node(); head.next = null;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head.next; t != null; t = t.next )
检查链表是否为空：if ( head.next == null )
空头结点，空尾结点
初始化：head = new Node(); z = new Node(); head.next = z; z.next = z;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head.next; t != z; t = t.next )
检查链表是否为空：if ( head.next == z )
循环链表
第一次插入：head.next = head;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：t = head; do { t = t.next; } while ( t != head );
检查是否只有一个数据项：if ( head.next == head )

堆栈

数组实现

class Stack {
  private Object[] s;
  private int n;
  Stack ( int maxN ) {
    s = new Object[maxN]; n = 0;
  }
  boolean isEmpty() { return ( n == 0 ); }
  void push ( Object item ) { s[n++] = item; }
  Object pop() {
    Object t = s[--n]; s[n] = null; return t;
  }
}

链表实现
class Stack {
  private Node head;
  private class Node {
    Object item; Node next;
    Node ( Object item, Node next ) {
      this.item = item; this.next = next;
    }
  }
  Stack ( Object maxN ) { head = null; }
  boolean isEmpty() { return ( head ==null ); }
  void push ( Object item ) { head = new Node(item, head); }
  Object pop() {
    Object v = head.item;
    Node t = head.next;
    head = t;
    return v;
  }
}

FIFO队列的链表实现

class Queue {
  private class Node {
    Object item; Node next;
    Node ( Object item ) {
      this.item = item; this.next = null;
    }
  }
  Private Node head, tail;
  Queue ( Object max ) { head = null; tail = null; }
  boolean isEmpty() { return ( head ==null ); }
  void put ( Object item ) {
    Node t = tail;
    tail = new Node(item);
    if ( empty() )
      head = tail;
    else t.next = tail
  }
  Object get() {
    Object v = head.item;
    Node t = head.next;
    head = t;
    return v;
  }
}