婚纱网站建设目的,wordpress商店插件怎么用,适合企业员工培训的课程,烟台网站建设公司地址从这里开始将要进行Java数据结构的相关讲解#xff0c;Are you ready#xff1f;Lets go~~ java中的数据结构模型可以分为一下几部分: 1.线性结构 2.树形结构 3.图形或者网状结构 接下来的几张#xff0c;我们将会分别讲解这几种数据结构#xff0c;主要也是通过Java代码的…从这里开始将要进行Java数据结构的相关讲解Are you readyLets go~~ java中的数据结构模型可以分为一下几部分: 1.线性结构 2.树形结构 3.图形或者网状结构 接下来的几张我们将会分别讲解这几种数据结构主要也是通过Java代码的方式来讲解相应的数据结构。 今天要讲解的是:Java线性结构 Java数据结构之线性结构 说到线性结构的话我们可以根据其实现方式分为两类: 1顺序结构的线性表 2链式结构的线性表 3栈和队列的线性表 对于1和2的讲解请参考下面的地址:http://www.cnblogs.com/xiohao/p/4353910.html 下面主要讲解线性结构中的栈和队列。 1.线性结构之栈的讲解 所谓栈是一种特殊的线性结构它的特点在于只允许我们在线性表的尾端进行insert和remove操作。可以理解为是一种受限的 线性表。往线性表中加入一个元素我们称为入栈从线性表中移除一个元素我们称为出栈。实在不懂百度一下你就知道了。 在Java的jdk中的实现以Stack(底层继承的是Vector类)和LinkedList(里面同样实现了pushpoppeek等操作)为主还是那句话感兴趣的 自己查看源代码即可。 下面我们进行相关模仿 首先通过数组来模仿入栈和出栈操作: package com.yonyou.test;import java.util.Arrays;/*** 测试类* author 小浩* 创建日期 2015-3-20*/
public class Test{ public static void main(String[] args) {SequenceStackString stacknew SequenceStackString();System.out.println(顺序栈的初始化长度为:stack.length());stack.push(Hello);stack.push(World);stack.push(天下太平);System.out.println(当前stack中的元素为:stack);System.out.println(当前stack.peek();中的元素为:stack.peek());System.out.println(当前元素线性表是否为空:stack.empty());}}/*** 创建一个线性栈* 注意这个类是线程不安全的在多线程下不要使用* author 小浩* 创建日期 2015-3-20* param T*/
class SequenceStackT
{//线性栈的默认长度为10private int DEFAULT_SIZE 10;// 保存数组的长度。private int capacity;// 定义当底层数组容量不够时程序每次增加的数组长度private int capacityIncrement 0;// 定义一个数组用于保存顺序栈的元素private Object[] elementData;// 保存顺序栈中元素的当前个数private int size 0;/*** 以默认数组长度创建空顺序栈*/public SequenceStack(){capacity DEFAULT_SIZE;elementData new Object[capacity];}/*** 以一个初始化元素来创建顺序栈* param element*/public SequenceStack(T element){this();elementData[0] element;size;}/*** 以指定长度的数组来创建顺序栈* param element 指定顺序栈中第一个元素* param initSize 指定顺序栈底层数组的长度*/public SequenceStack(T element , int initSize){this.capacity initSize;elementData new Object[capacity];elementData[0] element;size;}/*** 以指定长度的数组来创建顺序栈* param element 指定顺序栈中第一个元素* param initSize 指定顺序栈底层数组的长度* param capacityIncrement 指定当顺序栈的底层数组的长度不够时底层数组每次增加的长度*/public SequenceStack(T element , int initSize, int capacityIncrement){this.capacity initSize;this.capacityIncrement capacityIncrement;elementData new Object[capacity];elementData[0] element;size;}/*** 获取顺序栈的大小* return*/public int length(){return size;}/*** 入栈* param element*/public void push(T element){ensureCapacity(size 1);elementData[size] element;}/*** 很麻烦而且性能很差* param minCapacity*/private void ensureCapacity(int minCapacity){// 如果数组的原有长度小于目前所需的长度if (minCapacity capacity){if (capacityIncrement 0){while (capacity minCapacity){// 不断地将capacity长度加capacityIncrement// 直到capacity大于minCapacity为止capacity capacityIncrement;}}else{// 不断地将capacity * 2直到capacity大于minCapacity为止while (capacity minCapacity){capacity 1;}}elementData Arrays.copyOf(elementData , capacity);}}/*** 出栈* return*/SuppressWarnings(unchecked)public T pop(){T oldValue (T)elementData[size - 1];// 释放栈顶元素elementData[--size] null;return oldValue;}/*** 返回栈顶元素但不删除栈顶元素* return*/SuppressWarnings(unchecked)public T peek(){return (T)elementData[size - 1];}/*** 判断顺序栈是否为空栈* return*/public boolean empty(){return size 0;}/*** 清空顺序栈*/public void clear(){// 将底层数组所有元素赋为nullArrays.fill(elementData , null);size 0;}/*** 重写toString*/public String toString(){if (size 0){return [];}else{StringBuilder sb new StringBuilder([);for (int i size - 1 ; i -1 ; i-- ){sb.append(elementData[i].toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}}
}其次通过链式存储来模仿入栈和出栈操作具体内容可以看下面的代码: package com.yonyou.test;/*** 测试类* author 小浩* 创建日期 2015-3-20*/
public class Test{ public static void main(String[] args) {LinkStackString stacknew LinkStackString();System.out.println(顺序栈的初始化长度为:stack.length());stack.push(Hello);stack.push(World);stack.push(天下太平);System.out.println(当前stack中的元素为:stack);System.out.println(当前stack.peek();中的元素为:stack.peek());System.out.println(当前元素线性表是否为空:stack.empty());}}/*** 创建一个链式存储的线性栈* 注意这个类是线程不安全的在多线程下不要使用* author 小浩* 创建日期 2015-3-20* param T*/
class LinkStackT
{// 定义一个内部类NodeNode实例代表链栈的节点。private class Node{// 保存节点的数据private T data;// 指向下个节点的引用private Node next;// 无参数的构造器public Node(){}// 初始化全部属性的构造器public Node(T data , Node next){this.data data;this.next next;}}// 保存该链栈的栈顶元素private Node top;// 保存该链栈中已包含的节点数private int size;/*** 创建空链栈*/public LinkStack(){// 空链栈top的值为nulltop null;}/*** 以指定数据元素来创建链栈该链栈只有一个元素* param element*/public LinkStack(T element){top new Node(element , null);size;}/*** 返回链栈的长度* return*/public int length(){return size;}/*** 进栈* param element*/public void push(T element){// 让top指向新创建的元素新元素的next引用指向原来的栈顶元素top new Node(element , top);size;}/*** 出栈* return*/public T pop(){Node oldTop top;// 让top引用指向原栈顶元素的下一个元素top top.next;// 释放原栈顶元素的next引用oldTop.next null;size--;return oldTop.data;}/*** 访问栈顶元素但不删除栈顶元素* return*/public T peek(){return top.data;}/*** 判断链栈是否为空栈* return*/public boolean empty(){return size 0;}/*** 清空链栈*/public void clear(){// 将底层数组所有元素赋为nulltop null;size 0;}/*** 重写toString方法*/public String toString(){// 链栈为空链栈时if (empty()){return [];}else{StringBuilder sb new StringBuilder([);for (Node current top ; current ! null; current current.next ){sb.append(current.data.toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}}
}2.线性结构之队列的讲解 队列也是一种被限制过的线性结构它使用固定的一端来插入元素队尾在另一端删除相关的元素队头。 其基本特征为“先进先出”而栈的基本特点为“先进后出”。 在Java的jdk中主要的实现类为Dueue接口的实现类ArrayDeque(线性)和LinkedList(链式) 其中Dueue接口是一个双端队列它继承了队列根接口Queue同时Queue接口有实现队列的6个根本方法 抛出异常的版本不抛出异常的版本返回null插入1、 boolean add(E e); 2、 boolean offer(E e);移除3、 E remove(); 4、 E poll();访问5、 E element(); 6、 E peek(); 如果感兴趣的话请查相关的源代码。 首先讲解的是队列的顺序存储: 具体内容请看相关代码: package com.yonyou.test;import java.util.Arrays;/*** 测试类* author 小浩* 创建日期 2015-3-20*/
public class Test{ public static void main(String[] args) {SequenceQueueString queuenew SequenceQueueString();System.out.println(队列的初始化长度为:queue.length());queue.add(Hello);queue.add(World);queue.add(天下太平);System.out.println(当前stack中的元素为:queue);queue.remove();System.out.println(当前stack中的元素为:queue);System.out.println(当前元素线性表是否为空:queue.empty());}}/*** 创建一个存储的线性队列* 注意这个类是线程不安全的在多线程下不要使用* author 小浩* 创建日期 2015-3-20* param T*/
class SequenceQueueT
{//线性队列的默认长度private int DEFAULT_SIZE 16;// 保存数组的长度。private int capacity;// 定义一个数组用于保存顺序队列的元素private Object[] elementData;// 保存顺序队列中元素的当前个数private int front 0;private int rear 0;/*** 以默认数组长度创建空顺序队列*/public SequenceQueue(){capacity DEFAULT_SIZE;elementData new Object[capacity];}/*** 以一个初始化元素来创建顺序队列* param element*/public SequenceQueue(T element){this();elementData[0] element;rear;}/*** 以指定长度的数组来创建顺序队列* param element 指定顺序队列中第一个元素* param initSize 指定顺序队列底层数组的长度*/public SequenceQueue(T element , int initSize){this.capacity initSize;elementData new Object[capacity];elementData[0] element;rear;}/*** 获取顺序队列的大小* return*/public int length(){return rear - front;}/*** 插入队列* param element*/public void add(T element){if (rear capacity - 1){throw new IndexOutOfBoundsException(队列已满的异常);}elementData[rear] element;}/*** 移出队列* return*/SuppressWarnings(unchecked)public T remove(){if (empty()){throw new IndexOutOfBoundsException(空队列异常);}// 保留队列的front端的元素的值T oldValue (T)elementData[front];// 释放队列的front端的元素elementData[front] null;return oldValue;}/*** 返回队列顶元素但不删除队列顶元素* return*/SuppressWarnings(unchecked)public T element(){if (empty()){throw new IndexOutOfBoundsException(空队列异常);}return (T)elementData[front];}/*** 判断顺序队列是否为空队列* return*/public boolean empty(){return rear front;}/**清空顺序队列* */public void clear(){//将底层数组所有元素赋为nullArrays.fill(elementData , null);front 0;rear 0;}/*** 重写toString方法*/public String toString(){if (empty()){return [];}else{StringBuilder sb new StringBuilder([);for (int i front ; i rear ; i ){sb.append(elementData[i].toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}}
}其次讲解的是队列的线性存储的循环组成: 对于上面的非循环存储可能会非常大的浪费空间下面我们将要创建一个对应的循环链表的概念这样的话可能会有效的节约相应的空间。 因为循环链表可以有效的消除假满的现象哦。 废话不在多说请看代码: package com.yonyou.test;import java.util.Arrays;/*** 测试类* author 小浩* 创建日期 2015-3-20*/
public class Test{ public static void main(String[] args) {LoopQueueString queuenew LoopQueueString();System.out.println(队列的初始化长度为:queue.length());queue.add(Hello);queue.add(World);queue.add(天下太平);System.out.println(当前stack中的元素为:queue);queue.remove();System.out.println(当前stack中的元素为:queue);System.out.println(当前元素线性表是否为空:queue.empty());}}/*** 创建一个顺序存储的循环线性队列* 注意这个类是线程不安全的在多线程下不要使用* author 小浩* 创建日期 2015-3-20* param T*/
class LoopQueueT
{//循环队列的默认长度为16private int DEFAULT_SIZE 16;// 保存数组的长度。private int capacity;// 定义一个数组用于保存循环队列的元素private Object[] elementData;// 保存循环队列中元素的当前个数private int front 0;private int rear 0;/*** 以默认数组长度创建空循环队列*/public LoopQueue(){capacity DEFAULT_SIZE;elementData new Object[capacity];}/*** 以一个初始化元素来创建循环队列* param element*/public LoopQueue(T element){this();elementData[0] element;rear;}/*** 以指定长度的数组来创建循环队列* param element 指定循环队列中第一个元素* param initSize 指定循环队列底层数组的长度*/public LoopQueue(T element , int initSize){this.capacity initSize;elementData new Object[capacity];elementData[0] element;rear;}/*** 获取循环队列的大小* return*/public int length(){if (empty()){return 0;}return rear front ? rear - front: capacity - (front - rear);}/*** 插入队列* param element*/public void add(T element){if (rear front elementData[front] ! null){throw new IndexOutOfBoundsException(队列已满的异常);}elementData[rear] element;// 如果rear已经到头那就转头rear rear capacity ? 0 : rear;}/*** 移出队列* return*/SuppressWarnings(unchecked)public T remove(){if (empty()){throw new IndexOutOfBoundsException(空队列异常);}// 保留队列的front端的元素的值T oldValue (T)elementData[front];// 释放队列的front端的元素elementData[front] null;// 如果front已经到头那就转头front front capacity ? 0 : front;return oldValue;}/*** 返回队列顶元素但不删除队列顶元素* return*/SuppressWarnings(unchecked)public T element(){if (empty()){throw new IndexOutOfBoundsException(空队列异常);}return (T)elementData[front];}/*** 判断循环队列是否为空队列* return*/public boolean empty(){//rearfront且rear处的元素为nullreturn rear front elementData[rear] null;}/*** 清空循环队列*/public void clear(){// 将底层数组所有元素赋为nullArrays.fill(elementData , null);front 0;rear 0;}/*** 重写toString方法*/public String toString(){if (empty()){return [];}else{// 如果front rear有效元素就是front到rear之间的元素if (front rear){StringBuilder sb new StringBuilder([);for (int i front ; i rear ; i ){sb.append(elementData[i].toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}// 如果front rear有效元素为front-capacity之间、// 和0-front之间的元素else{StringBuilder sb new StringBuilder([);for (int i front ; i capacity ; i ){sb.append(elementData[i].toString() , );}for (int i 0 ; i rear ; i){sb.append(elementData[i].toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}}}
}最后要说的队列的链式存储具体的实现方式还是请看代码吧。 package com.yonyou.test;import java.util.Arrays;/*** 测试类* author 小浩* 创建日期 2015-3-20*/
public class Test{ public static void main(String[] args) {LinkQueueString queuenew LinkQueueString();System.out.println(队列的初始化长度为:queue.length());queue.add(Hello);queue.add(World);queue.add(天下太平);System.out.println(当前stack中的元素为:queue);queue.remove();System.out.println(当前stack中的元素为:queue);System.out.println(当前元素线性表是否为空:queue.empty());}}/*** 创建一个链式存储的线性队列* 注意这个类是线程不安全的在多线程下不要使用* author 小浩* 创建日期 2015-3-20* param T*/
//定义一个内部类NodeNode实例代表链队列的节点。
class LinkQueueT{private class Node{// 保存节点的数据private T data;// 指向下个节点的引用private Node next;// 无参数的构造器public Node(){}// 初始化全部属性的构造器public Node(T data , Node next){this.data data;this.next next;}}// 保存该链队列的头节点private Node front;// 保存该链队列的尾节点private Node rear;// 保存该链队列中已包含的节点数private int size;/*** 创建空链队列*/public LinkQueue(){// 空链队列front和rear都是nullfront null;rear null;}/*** 以指定数据元素来创建链队列该链队列只有一个元素* param element*/public LinkQueue(T element){front new Node(element , null);// 只有一个节点front、rear都指向该节点rear front;size;}/*** 返回链队列的长度* return*/public int length(){return size;}/*** 将新元素加入队列* param element*/public void add(T element){// 如果该链队列还是空链队列if (front null){front new Node(element , null);// 只有一个节点front、rear都指向该节点rear front;}else{// 创建新节点Node newNode new Node(element , null);// 让尾节点的next指向新增的节点rear.next newNode;// 以新节点作为新的尾节点rear newNode;}size;}/*** 删除队列front端的元素* return*/public T remove(){Node oldFront front;front front.next;oldFront.next null;size--;return oldFront.data;}/*** 访问链式队列中最后一个元素* return*/public T element(){return rear.data;}/*** 判断链式队列是否为空队列* return*/public boolean empty(){return size 0;}/*** 清空链队列*/public void clear(){// 将front、rear两个节点赋为nullfront null;rear null;size 0;}/*** 重写toString方法*/public String toString(){// 链队列为空链队列时if (empty()){return [];}else{StringBuilder sb new StringBuilder([);for (Node current front ; current ! null; current current.next ){sb.append(current.data.toString() , );}int len sb.length();return sb.delete(len - 2 , len).append(]).toString();}}
}这里还是补充一下吧除了以上介绍的队列外我们还可以经用到的一个队列是双端队列。 所谓双端队列指的是我们可以在队列的两端进行插入和删除操作。如果我们只允许在队列的一端进行插入和删除的操作那么队列也就成为 我们之前看到的栈了是不是很有意思没错就是这样的。其实栈队列其本质都是一种受限制的线性表只好不过限制的情况不同而已。 还需要说的jdk中Deque接口就是一个双端队列的实用接口。它可以理解为Queue和Stack的一个中和体。虽然上面的栈提到了类Stack 但是现在已经不推荐使用了一般情况我们应该使用Deque因为它的功能更加强大。 在jdk中双端队列接口Deque有两个实现类ArrayDeque(顺序存储的双端队列)和LinkedList(链式存储的双端队列) 是不是发现了LinkedList的功能太强大了。没错它就是这么任性没办法。 下面的看一下它的部分源代码: * since 1.2* param E the type of elements held in this collection*/public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializableimplements ListE, DequeE, Cloneable, java.io.Serializable 看到红色字体了了吧剩下你懂的~~ 好吧今天就先到这里吧~~~ 转载于:https://www.cnblogs.com/xiohao/p/4354276.html
