平乡企业做网站甘肃建筑人才网

平乡企业做网站,甘肃建筑人才网,网站建设实训报告ppt,注册一个公司网站的费用(一).栈1.栈的概念栈是一种先进后出的顺序表#xff0c;只允许在固定的一端进行插入和删除。进行插入和删除的一端称为栈顶#xff0c;另一端称为栈底在栈中#xff0c;插入数据叫做入栈/压栈/进栈删除数据也叫做出栈在生活中#xff0c;羽毛球就和栈类似#xff0c;先放进…(一).栈1.栈的概念栈是一种先进后出的顺序表只允许在固定的一端进行插入和删除。进行插入和删除的一端称为栈顶另一端称为栈底在栈中插入数据叫做入栈/压栈/进栈删除数据也叫做出栈在生活中羽毛球就和栈类似先放进去的球最后拿出来2.模拟实现栈这是Java提供的栈所提供的功能所以接下来我们就要模拟实现这些功能(1).创建成员变量public int[] element; public int usedSize; public MyStack() { this.element new int[10]; }首先我们要明确实现栈我们是用数组进行实现所以我们首先是要有一个数组同时需要一个变量来记录当前栈我们所使用的个数同时我们需要一个构造方法即当程序运行起来的时候我们首先开辟10个空间(2).入栈//入栈 public void push(int val){ //判断栈是否满了 if (isFull()){ //满了则需要扩容 this.element Arrays.copyOf(element,2*this.element.length); }else{ this.element[this.usedSize]val; this.usedSize; } } private boolean isFull(){ return this.element.lengththis.usedSize; }首先我们先判断栈是否满了如果满了则需要我们手动扩容当然我们自己实现的时候是2倍扩容如果没满我们只需要将下标为usedSize的数组的值设为val即可同时usedSize要(3).出栈//出栈 public int pop(){ //判断栈是否为null if (isEmpty()){ throw new EmptyStackException(栈为空无法出栈); } int valuethis.element[this.usedSize-1]; this.usedSize--; return value; } private boolean isEmpty(){ return this.usedSize0; }在出栈时我们首先要判断栈是否为空那么如何判断栈是否为空我们说过usedSize表示栈中的数据个数所以当usedSize0的时候此时栈就是空的当栈不为空时我们只需要将数组下标为usedSize-1位置的值返回即可因为数组下标为usedSize位置表示即将插入数据的下标而不是栈中最后一个数据的下标所以我们要返回usedSize-1位置的下标(4).查看栈顶的数据public int peek(){ if (isEmpty()){ throw new EmptyStackException(栈为空无法获取栈顶数据); } return this.element[this.usedSize-1]; }首先同样我们也要先判断栈是否为空如果为空则抛出异常public class EmptyStackException extends RuntimeException{ public EmptyStackException() { super(); } public EmptyStackException(String s) { super(s); } }如果不抛出异常直接返回栈顶的数据注意查看栈顶的数据并不是出栈(5).判断栈是否为空private boolean isEmpty(){ return this.usedSize0; }我们只需要判断usedSize是否为0即可3.链式栈顾名思义就是用链表来存储栈此时建议使用头插和头删来实现我们的push()和pop()方法因为这样的时间复杂度低为O(1)如果采用尾插尾删你每次都需要找到前一个节点这样的时间复杂度为O(N)。如果使用双向链表则push()和pop()的时间复杂度都是O(1)4.栈虚拟机栈栈帧的区别栈是数据结构中的其中一种数据结构虚拟机栈是JVM虚拟机的一块内存栈帧是封装了方法运行所需的所有信息的内存块(二).队列1.概念队列是一种先进先出的特殊顺序表。只允许一端进行插入数据另一端进行删除数据进行插入数据的一端称为队尾进行删除数据的一端称为队头。插入数据也称为入队删除数据也称为出队2.模拟实现队列这是Java提供的队列的方法下面我们就模拟实现这些功能(1).创建成员变量static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val val; } }首先我们使用双向链表来实现我们的队列同时提供一个构造方法来初始化我们的val(2).创建头尾节点public ListNode first; public ListNode last;接下来我们只需要对first和last进行操作即可(3).入队//入队 尾插 public void offer(int val){ ListNode nodenew ListNode(val); if (isEmpty()){ this.firstthis.lastnode; }else{ this.last.nextnode; node.prevlast; this.lastnode; } } public boolean isEmpty(){ if (this.firstnull){ return true; } return false; }入队我们采取的是尾插首先我们先判断一下队是否为空在判断队是否为空时我们只需要判断头节点是否为空即可如果为空则表示整个队就是空的此时返回true即可否则返回false如果为空那么要入队的这个节点既是头节点也是尾节点如果队不为空那么只需要让last节点的后驱next指向node然后让node节点的前驱prev指向last同时让node成为新的尾即可(4).出队//出队 头删 public int poll(){ int value; if (isEmpty()){ System.out.println(队为空无法删除); return -1; }else{ valuethis.first.val; this.firstthis.first.next; if (this.first!null){ this.first.prevnull; } } return value; } public boolean isEmpty(){ if (this.firstnull){ return true; } return false; }出队我们采取的是头删首先依旧是先判断队是否为空如果为空则返回-1如果不为空我们通过变量value来接收first节点的值然后让firstfirst.next即让first指向下一个节点然后我们需要判断一下此时的first是否为空如果为空说明此时这个队列只有一个头节点所以我们就不需要将first的前驱置为空了因为first此时已经为空了如果此时的first不为空那么我们将first的前驱再置为空最后返回我们的value值(5).获取队头元素//获取队头元素 public int peek(){ if (this.firstnull){ System.out.println(队为空无法删除); return -1; } return this.first.val; }首先我们先判断一下队头是否为空如果为空则直接返回-1如果不为空直接返回first.val即可3.循环队列我们可以使用数组来实现一个循环队列但是这样会有一个问题当前五个数据都出队了之后那么我们前五个数据的空间用不了了也就是说每次出队之后都会浪费一个空间那么我们该如何解决这个问题同时我们如何判断这个顺序队是否满了和空了答只要first和last相遇了那么这个队列就空了如何判断是否满了1.定义一个size来统计个数2.添加一个标记可以定义一个boolean类型的数据3.浪费一个空间即开辟空间的时候多开一个在判断是否满了的时候我们可以通过看last的下一个是否为first但是还有一个问题此时当我想要在last的位置插入数据的时候我该如何进行判断last1first吗这样肯定是不正确因为如果last再1那么数组就越界了那我们该如何解决我们可以这样判断(last1)%arr.length我们可以想一想是不是这样此时last10此时数组的长度为11那么就是(101)%11正好等于0恰好可以解决我们的问题那么我们该如何判断满同样要进行模除即如果(last1)%arr.lengthfirst此时队列就满了完整版代码public int first; public int last; public int[] arr; public test(int k) { arrnew int[k1]; } public boolean enQueue(int value) { if(isFull()){ return false; } arr[last]value; last(last1)%arr.length; return true; } public boolean deQueue() { if(isEmpty()){ return false; } first(first1)%arr.length; return true; } public int Front() { if(isEmpty()){ return -1; } return arr[first]; } public int Rear() { if(isEmpty()){ return -1; } int indexlast0?arr.length-1:last-1; return arr[index]; } public boolean isEmpty() { return firstlast; } public boolean isFull() { return first(last1)%arr.length; }4.双端队列双端队列允许两端都可以进行插入和删除数据可是通过上面的图片我们可以看到Queue和双端队列Deque都是接口不能实例化那么我们要怎么进行使用通过上面的图片我们可以看到我们的双向链表是实现了Deque接口的同时Deque接口继承了Queue接口也就是说我们可以实例化一个LinkedList接口然后用Deque接收我们就可以使用双端队列的方法了同样也可以实例化一个LinkedList接口然后用Queue接收就可以使用普通队列的方法了同样站和队列都可以使用Deque接口public static void main(String[] args) { //双端链式队列 DequeInteger deque1new LinkedList(); //双端数组队列 DequeInteger deque2new ArrayDeque();//底层是一个数组 }