Java数据结构之链表、栈、队列、树的实现方法示例

/**链表节点定义 * @author colonel * */class Node { public int data; Node next=null; public Node(int data){ this.data=data; }}

/**链表操作类 * @author colonel * */public class operateClass { public Node headNode=null; /*给链表添加界节点 * @param data 链表节点数据 */ public Node addNode(int data){ Node newNode=new Node(data); if (headNode==null) {  headNode=newNode;  newNode.next=null;  return headNode; } Node tempNode=headNode; while (tempNode.next!=null) {  //tempNode=headNode;  tempNode=tempNode.next; } tempNode.next=newNode; return headNode; } /**删除节点 * @param 删除节点的位置 * */ public boolean delNode(int index){ if (index<1||index>length()) {  return false; } if (index==1) {  headNode=headNode.next;  return true; } Node preNode=headNode; Node curNode=preNode.next; int count=2; while (curNode!=null) {  if (count==index) {  preNode.next=curNode.next;  return true;  }  preNode=curNode;  curNode=curNode.next;  count++; } return true; } /**取链表的长度 * @return返回链表的长度 */ public int length(){ int length=0; Node temp=headNode; while (temp!=null) {  length++;  temp=temp.next; } return length; } /**按照值域对链表数据排序 * @return 返回排序后的链表头节点 */ public Node orderList(){ Node nextNode=null; int temp=0; Node curNode=headNode; while (curNode.next!=null) {  nextNode=curNode.next;  while (nextNode!=null) {  if (curNode.data>nextNode.data) {  temp=curNode.data;  curNode.data=nextNode.data;  nextNode.data=temp;  }  nextNode=nextNode.next;  }  curNode=curNode.next; }  return headNode; } /** * 去除链表中值域重复的元素 */ public void redRepeat(){ if (length()<=1) {  return; } Node curNode=headNode; while (curNode!=null) {  Node insidNode=curNode.next;  Node insidPreNode=insidNode;  while (insidNode!=null) {  if (insidNode.data==curNode.data) {   insidPreNode.next=insidNode.next;   //return;  }  insidPreNode=insidNode;  insidNode=insidNode.next;  }  curNode=curNode.next; } } /**倒序输出链表中所有的数据 * @param hNode 链表头节点 */ public void reversePrint(Node hNode){ if (hNode!=null) {  reversePrint(hNode.next);  System.out.println(hNode.data); } } /** * 从头节点开始到为节点结尾打印出值 */ public void printList(){ Node tmpNode=headNode; while (tmpNode!=null) {  System.out.println(tmpNode.data);  tmpNode=tmpNode.next; } }}

class MyStack<E>{ private Object[] stack; int top=-1; public MyStack(){ stack=new Object[10]; } public boolean isEmpty(){ return top==0; } /**弹出栈顶元素（不删除） * @return */ public E peek(){ if (isEmpty()) {  return null; } return (E) stack[top]; } /**出栈站顶元素 * @return 栈顶元素 */ public E pop(){ E e=peek(); stack[top]=null; top--; return e; } /**压栈 * @param item 待压元素 * @return 返回待压元素 */ public E push(E item){ //ensureCapacity(top+1); stack[++top]=item; return item; } /**栈满扩容 * @param size */ public void ensureCapacity(int size){ int len=stack.length; if (size>len) {  int newLen=10;  stack=Arrays.copyOf(stack, newLen); } } /**返回栈顶元素 * @return */ public E getTop(){ if (top==-1) {  return null; } return (E) stack[top]; }}

/** * @author colonel *队节点定义 * @param <Elem> */class queueNode<Elem>{ queueNode<Elem> nextNode=null; Elem data; public queueNode(Elem data){ this.data=data; }}

/** * @author colonel *队列操作类 * @param <Elem> */class MyQueue<Elem>{ private queueNode<Elem> headNode=null; private queueNode<Elem> tailNode=null; private queueNode<Elem> lastNode=null; /**判断该队列是否为空 * @return 返回true or false */ public boolean isEmpty(){ return headNode==tailNode; } /**入队操作 * @param data 节点元素值 */ public void put(Elem data){ queueNode<Elem> newNode=new queueNode<Elem>(data); if (headNode==null&&tailNode==null) {  headNode=tailNode=newNode;  //tailNode=headNode.nextNode;  lastNode=tailNode.nextNode;  return; } tailNode.nextNode=newNode; tailNode=newNode; lastNode=tailNode.nextNode; //tailNode=tailNode.nextNode; } /**出队操作 * @return 返回出队元素 */ public Elem pop(){ if (headNode==lastNode) {  return null; } queueNode<Elem> tempNode=headNode; Elem statElem=tempNode.data; headNode=tempNode.nextNode; return statElem; } /**返回队列长度 * @return 长度 */ public int size(){ if (isEmpty()) {  return 0; } int length=0; queueNode<Elem> temp=headNode; while (temp!=null) {  length++;  temp=temp.nextNode; } return length; }}

/**树节点定义 * @author colonel * */class TreeNode{ public int data; public TreeNode leftNode; public TreeNode rightNode; public TreeNode(int data){ this.data=data; this.leftNode=null; this.rightNode=null; }}

/**二叉排序树操作类 * @author colonel * */class OperateTree{ public TreeNode rootNode; public OperateTree(){ rootNode=null; } /**元素插入二叉排序树 * @param data 待插节点数据 */ public void insert(int data){ TreeNode newNode=new TreeNode(data); if (rootNode==null) {  rootNode=newNode; }else {  TreeNode current=rootNode;  TreeNode parent;  while (true) {  parent=current;  if (data<current.data) {   current=current.leftNode;   if (current==null) {   parent.leftNode=newNode;   return;   }  } else {   current=current.rightNode;   if (current==null) {   parent.rightNode=newNode;   return;   }  }  } } } /**构建二叉排序树 * @param item 元素数组 */ public void buildTree(int[] item){ for (int i = 0; i < item.length; i++) {  insert(item[i]); } } /** * 先序遍历二叉树 */ public void preOrder(TreeNode root){ if (root!=null) {  System.out.println(root.data);  preOrder(root.leftNode);  preOrder(root.rightNode); } } /**中序遍历 * @param root */ public void inOrder(TreeNode root){ if (root!=null) {  inOrder(root.leftNode);  System.out.println(root.data);  inOrder(root.rightNode); } } /**后序遍历 * @param root */ public void afterOrder(TreeNode root){ if (root!=null) {  afterOrder(root.leftNode);  afterOrder(root.rightNode);  System.out.println(root.data); } } /** * 层序遍历二叉排序树 */ public void layerTrave(){ if (this.rootNode==null) {  return; } Queue<TreeNode> myQueue=new LinkedList<>(); myQueue.add(rootNode); while (!myQueue.isEmpty()) {  TreeNode tempNode=myQueue.poll();  System.out.println(tempNode.data);  if (tempNode.leftNode!=null) {  myQueue.add(tempNode.leftNode);  }  if (tempNode.rightNode!=null) {  myQueue.add(tempNode.rightNode);  } } }