[Java] 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);
  }
 }
 }