Java基础知识--数据结构

一、栈

数组容器

package cn.xiaoxiang.structure;public class Stack {//数组容器private Object[] stack;//最大容量private int maxSize;//当前元素个数private int item; /*** * @param maxSize 栈的最大容量*/public Stack(int maxSize){this.maxSize = maxSize;stack = new Object[this.maxSize];item = 0;}/*** 压栈* @param obj 存入栈中的内容*/public void push( Object obj){if(!isFull()){stack[item++] = obj;}else{throw new RuntimeException("栈中已满");}}/*** 弹栈* @return*/public Object pop(){if(!isEmpty()){return stack[--item];}else{throw new RuntimeException("栈中已空");}}/*** 判断栈是否为空* @return*/public boolean isEmpty(){return item==0;}/*** 判断栈是否满了* @return*/public boolean isFull(){return  item == stack.length;}/*** 得到栈当前的存储量* @return*/public int size(){return  item;}
}

链表容器

package cn.xiaoxiang.structure;public class LinkStack {//栈顶private Node top = null; /*** 压栈* @param item 要放栈顶的元素* @return 返回参数item*/public E push(E item){Node newNode = new Node(item);Node curNode = top;top = newNode;newNode.next = curNode;return item;}/*** 弹栈* @return 返回栈顶的元素*/public E pop(){if(isEmpty())return null;E item = top.data;top = top.next;return item;}/*** 往栈顶瞟一眼* @return 返回栈顶元素*/public E peek(){E item = null;if(top!=null)item = top.data;return item;}/*** 查找指定元素在栈中的位置* @param item 要查找的元素* @return 返回指定元素在栈中的实际位置，从1开始，没有找到返回-1*/public int search(E item){int pos = 0;Node curNode = top;while(curNode !=null){pos++;if(curNode.data.equals(item)){break;}curNode = curNode.next;}if(curNode==null)return -1;return pos;}/*** 判栈空* @return 栈为空返回true,否则返回false*/public boolean isEmpty(){return top==null;}public void empty(){top = null;}public class Node {public E data;public Node next = null;public Node(E data) {this.data = data;}}
}

二、队列

数组容器

package cn.xiaoxiang.structure;public class Queue {private Object[] queue;//最大容量private int maxSize;//当前元素个数private int item;//入列索引private int in;//出列索引private int out;public Queue(int maxSize){this.maxSize = maxSize;queue = new Object[this.maxSize];item = 0;in = -1;out = -1;}/*** 入列* @param obj*/public void insert(Object obj){if(!isFull()){item++;queue[++in] = obj;}else{throw new RuntimeException("列队已满");}}/*** 出列* @return*/public Object remove(){if(!isEmpty()){item--;return queue[++out];}else{throw new RuntimeException("列队已空");}}/*** 得到已入列队的存储量* @return*/public int size(){return item;}/*** 判断列队是否为空* @return*/public boolean isEmpty(){return item == 0;}/*** 判断列队是否已满* @return*/public boolean isFull(){return item == maxSize;}}

链表容器

package cn.xiaoxiang.structure;public class LinkQueue {private Node head = null;private Node tail = null;/*** 入列，往列队尾部添加一个元素* @param item 要添加的元素* @return 添加成功返回true，否则返回false*/public boolean add(E item){Node newNode = new Node(item);if(head == null){head = newNode;tail = head;}else{tail.next = newNode;tail = newNode;}return true;}/*** 出列，从列队头部去掉一个元素* @return 返回列队头部元素，列队为空则返回null*/public E remove(){E item = null;if(head!=null){item = head.data;head = head.next;}return item;}/*** 往列队头部瞟一眼* @return 返回列队头部元素，列队为空则返回null*/public E peek(){E item = null;if(head!=null){item = head.data;}return item;}/*** 判断列队是否为空* @return 列队为空返回true，否则返回false*/public boolean isEmpty(){return head == null;}public class Node {public E data;public Node next = null;public Node(E data) {this.data = data;}}
}

三、链表

单向链表

package cn.xiaoxiang.structure;public class SingleLinkList {//链表的头结点public Node head = null;  //链表的尾结点private Node tail = null; /*** 从头部往链表中添加一个元素* @param data 要添加的元素* @return 要添加的元素在链表中已存在则不添加并返回false，否则添加并返回true*/public boolean add2Head(Object data){if(exist(data))return false;Node newNode = new Node(data);newNode.next = head;head = newNode;return true;}/*** 从尾部往链表中添加一个元素* @param data 要添加的元素* @return 要添加的元素在链表中已存在则不添加并返回false，否则添加并返回true*/public boolean add2Tail(Object data){if(exist(data))return false;Node newNode = new Node(data);if(head==null){head = newNode;tail = head;}else{tail.next = newNode;tail = newNode;}return true;}/*** 获取链表中index索引处的元素* @param index 元素的索引值，从0开始* @return 返回索引所对应的元素*/public Object get(int index){if(index<0||index>size()-1)throw new IndexOutOfBoundsException(index+"");Node curNode = head;Object data = null;while(curNode!=null){index--;if(index<0){data = curNode.data;break;}curNode = curNode.next;}return data;}/*** 从链表中移除指定的元素* @param data 要移除的元素* @return 移除成功返回true,否则返回false*/public boolean remove(Object data){if(!exist(data))return false;if(head.data.equals(data)){head = head.next;}else{Node curNode = head;Node nextNode = curNode.next;while(nextNode!=null){if(nextNode.data.equals(data)){curNode.next = nextNode.next;break;}curNode = nextNode;nextNode = curNode.next;}}return true;}/*** 在链表中指定元素的前面插入一个元素* @param before 指定的元素* @param data 要插入的元素* @return 插入成功返回true,否则返回false,若要要插入的元素在链表中已存在也返回false*/public boolean insertBefore(Object before,Object data){if(!exist(before))throw new RuntimeException("你所指定的插入点不存在");if(exist(data))return false;Node newNode = new Node(data);Node curNode = head;if(head.data.equals(before)){head = newNode;newNode.next = curNode;}else{Node nextNode = curNode.next;while(nextNode!=null){if(nextNode.data.equals(before)){curNode.next = newNode;newNode.next = nextNode;break;}curNode = nextNode;nextNode = curNode.next;}}return true;}/*** 在链表中指定元素的后面插入一个元素* @param after 指定的元素* @param data  要插入的元素* @return 插入成功返回true,否则返回false,若要要插入的元素在链表中已存在也返回false*/public boolean insertAfter(Object after,Object data){if(!exist(after))throw new RuntimeException("你所指定的插入点不存在");if(exist(data))return false;Node newNode = new Node(data);Node curNode = head;while(curNode!=null){if(curNode.data.equals(after)){newNode.next = curNode.next;curNode.next = newNode;break;}curNode = curNode.next;}return true;}/*** 判断链表是否为空* @return 链表为空返回true,否则返回false*/public boolean isEmpty(){return head==null;}/*** 判断指定的元素在链表中是否存在* @param data 指定的元素* @return 存在返回true,否则返回false*/public boolean exist(Object data){boolean result = false;Node curNode = head;while(curNode!=null){if(curNode.data.equals(data)){result = true;break;}curNode = curNode.next;}return result;}/*** 获取链表的大小* @return 返回链表的实际大小*/public int size() {int size = 0;Node curNode = head;while(curNode!=null){size++;curNode = curNode.next;}return size;}public class Node {public Object data;public Node next = null;public Node(Object data) {this.data = data;}}
}

双向链表

package cn.xiaoxiang.structure;public class DoubleLinkList {//链表的头结点public Node head = null;  //链表的尾结点public Node tail = null; /*** 从头部往链表中添加一个元素* @param data 要添加的元素* @return 要添加的元素在链表中已存在则不添加并返回false，否则添加并返回true*/public boolean add2Head(Object data){if(exist(data))return false;Node newNode = new Node(data);if (head == null) {tail = newNode;}newNode.next = head;head.previous = newNode;head = newNode;return true;}/*** 从尾部往链表中添加一个元素* @param data 要添加的元素* @return 要添加的元素在链表中已存在则不添加并返回false，否则添加并返回true*/public boolean add2Tail(Object data){if(exist(data))return false;Node newNode = new Node(data);if(head==null){head = newNode;tail = head;}else{tail.next = newNode;newNode.previous = tail;tail = newNode;}return true;}/*** 获取链表中index索引处的元素* @param index 元素的索引值，从0开始* @return 返回索引所对应的元素*/public Object get(int index){if(index<0||index>size()-1)throw new IndexOutOfBoundsException(index+"");Node curNode = head;Object data = null;while(curNode!=null){index--;if(index<0){data = curNode.data;break;}curNode = curNode.next;}return data;}/*** 从链表中移除指定的元素* @param data 要移除的元素* @return 移除成功返回true,否则返回false*/public boolean remove(Object data){if(!exist(data))return false;if (size() == 1) {head = tail = null;} else {if (head.data.equals(data)) {head = head.next;} else if (tail.data.equals(data)) {tail = tail.previous;} else {Node curNode = head;Node nextNode = curNode.next;while (nextNode != null) {if (nextNode.data.equals(data)) {curNode.next = nextNode.next;nextNode.next.previous = curNode;break;}curNode = nextNode;nextNode = curNode.next;}}}return true;}/*** 在链表中指定元素的前面插入一个元素* @param before 指定的元素* @param data 要插入的元素* @return 插入成功返回true,否则返回false,若要要插入的元素在链表中已存在也返回false*/public boolean insertBefore(Object before,Object data){if(!exist(before))throw new RuntimeException("你所指定的插入点不存在");if(exist(data))return false;Node newNode = new Node(data);Node curNode = head;if(head.data.equals(before)){head = newNode;newNode.next = curNode;curNode.previous = newNode;}else{Node nextNode = curNode.next;while(nextNode!=null){if(nextNode.data.equals(before)){curNode.next = newNode;newNode.previous = curNode;newNode.next = nextNode;nextNode.previous = newNode;break;}curNode = nextNode;nextNode = curNode.next;}}return true;}/*** 在链表中指定元素的后面插入一个元素* @param after 指定的元素* @param data  要插入的元素* @return 插入成功返回true,否则返回false,若要要插入的元素在链表中已存在也返回false*/public boolean insertAfter(Object after,Object data){if(!exist(after))throw new RuntimeException("你所指定的插入点不存在");if(exist(data))return false;Node newNode = new Node(data);if(tail.data.equals(after)){Node tempNode = tail;tail = newNode;newNode.previous = tempNode;tempNode.next = newNode;}else{Node curNode = head;while(curNode!=null){if(curNode.data.equals(after)){newNode.next = curNode.next;curNode.next.previous = newNode;curNode.next = newNode;newNode.previous = curNode;break;}curNode = curNode.next;}}return true;}/*** 判断链表是否为空* @return 链表为空返回true,否则返回false*/public boolean isEmpty(){return head==null;}/*** 判断指定的元素在链表中是否存在* @param data 指定的元素* @return 存在返回true,否则返回false*/public boolean exist(Object data){boolean result = false;Node curNode = head;while(curNode!=null){if(curNode.data.equals(data)){result = true;break;}curNode = curNode.next;}return result;}/*** 获取链表的大小* @return 返回链表的实际大小*/public int size() {int size = 0;Node curNode = head;while(curNode!=null){size++;curNode = curNode.next;}return size;}public class Node {public Object data;public Node next = null;public Node previous  = null;public Node(Object data) {this.data = data;}}
}

转载于:https://my.oschina.net/u/3323607/blog/2253386

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！