嘉义市网站建设_网站建设公司_UX设计_seo优化

(一).栈

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.length==this.usedSize; }

首先我们先判断栈是否满了，如果满了，则需要我们手动扩容，当然，我们自己实现的时候是2倍扩容

如果没满，我们只需要将下标为usedSize的数组的值设为val即可，同时usedSize要++

(3).出栈

//出栈 public int pop(){ //判断栈是否为null if (isEmpty()){ throw new EmptyStackException("栈为空，无法出栈"); } int value=this.element[this.usedSize-1]; this.usedSize--; return value; } private boolean isEmpty(){ return this.usedSize==0; }

在出栈时，我们首先要判断栈是否为空，那么如何判断栈是否为空？

我们说过，usedSize表示栈中的数据个数，所以当usedSize=0的时候，此时栈就是空的

当栈不为空时，我们只需要将数组下标为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.usedSize==0; }

我们只需要判断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 node=new ListNode(val); if (isEmpty()){ this.first=this.last=node; }else{ this.last.next=node; node.prev=last; this.last=node; } } public boolean isEmpty(){ if (this.first==null){ 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{ value=this.first.val; this.first=this.first.next; if (this.first!=null){ this.first.prev=null; } } return value; } public boolean isEmpty(){ if (this.first==null){ return true; } return false; }

出队，我们采取的是头删

首先依旧是先判断队是否为空，如果为空，则返回-1

如果不为空，我们通过变量value来接收first节点的值，然后让first=first.next，即让first指向下一个节点

然后我们需要判断一下此时的first是否为空，如果为空，说明此时这个队列只有一个头节点，所以我们就不需要将first的前驱置为空了，因为first此时已经为空了

如果此时的first不为空，那么我们将first的前驱再置为空

最后返回我们的value值

(5).获取队头元素

//获取队头元素 public int peek(){ if (this.first==null){ System.out.println("队为空，无法删除"); return -1; } return this.first.val; }

首先我们先判断一下，队头是否为空，如果为空，则直接返回-1

如果不为空，直接返回first.val即可

3.循环队列

我们可以使用数组来实现一个循环队列

但是这样会有一个问题

当前五个数据都出队了之后，那么我们前五个数据的空间用不了了，也就是说每次出队之后都会浪费一个空间

那么我们该如何解决这个问题，同时我们如何判断这个顺序队是否满了和空了？

答：只要first和last相遇了，那么这个队列就空了

如何判断是否满了？

1.定义一个size来统计个数

2.添加一个标记，可以定义一个boolean类型的数据

3.浪费一个空间，即开辟空间的时候多开一个，在判断是否满了的时候，我们可以通过看last的下一个是否为first

但是还有一个问题

此时，当我想要在last的位置插入数据的时候，我该如何进行判断？

last+1==first吗？

这样肯定是不正确，因为，如果last再+1，那么数组就越界了，那我们该如何解决？

我们可以这样判断

(last+1)%arr.length

我们可以想一想是不是这样，此时last=10，此时数组的长度为11，那么就是(10+1)%11

正好等于0，恰好可以解决我们的问题

那么我们该如何判断满？

同样要进行模除

即如果(last+1)%arr.length==first，此时队列就满了

完整版代码

public int first; public int last; public int[] arr; public test(int k) { arr=new int[k+1]; } public boolean enQueue(int value) { if(isFull()){ return false; } arr[last]=value; last=(last+1)%arr.length; return true; } public boolean deQueue() { if(isEmpty()){ return false; } first=(first+1)%arr.length; return true; } public int Front() { if(isEmpty()){ return -1; } return arr[first]; } public int Rear() { if(isEmpty()){ return -1; } int index=last==0?arr.length-1:last-1; return arr[index]; } public boolean isEmpty() { return first==last; } public boolean isFull() { return first==(last+1)%arr.length; }

4.双端队列

双端队列，允许两端都可以进行插入和删除数据

可是通过上面的图片我们可以看到，Queue和双端队列Deque都是接口，不能实例化，那么我们要怎么进行使用？

通过上面的图片我们可以看到，我们的双向链表是实现了Deque接口的

同时Deque接口继承了Queue接口

也就是说我们可以实例化一个LinkedList接口然后用Deque接收，我们就可以使用双端队列的方法了

同样也可以实例化一个LinkedList接口然后用Queue接收，就可以使用普通队列的方法了

同样，站和队列都可以使用Deque接口

public static void main(String[] args) { //双端链式队列 Deque<Integer> deque1=new LinkedList<>(); //双端数组队列 Deque<Integer> deque2=new ArrayDeque<>();//底层是一个数组 }