怎么删除网站死链,怎么改网站模块,网站建站步骤流程,wordpress live2d插件1.数组
数组#xff08;Array#xff09;是一种很常见的数据结构。它由相同类型的元素#xff08;element#xff09;组成#xff0c;并且是使用一块连续的内存来存储。
我们直接可以利用元素的索引#xff08;index#xff09;计算出该元素对应的存储地址。
数组的特…1.数组
数组Array是一种很常见的数据结构。它由相同类型的元素element组成并且是使用一块连续的内存来存储。
我们直接可以利用元素的索引index计算出该元素对应的存储地址。
数组的特地那是提供随机访问并且容量有限。
假如数组的长度为 n。
访问O1//访问特定位置的元素
插入On //最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除On//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时 2.链表
2.1 链表简介
链表LinkedList虽然是一种线性表但是并不会按线性的顺序存储数据使用的不是连续的内存空间来存储数据。
链表的插入和删除操作的复杂度为O(1)只需要知道目标位置元素的上一个元素即可。但是在查找一个节点或者访问特定位置的节点的时候复杂度为O(n).
使用链表结构可以克服数组需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但链表不会节省空间相比于数组会占用更多的空间因为链表中每个节点存放的还有指向其他节点的指针。除此之外链表不具有数组随机读取的优点
2.2 链表分类
常见链表分类
1.单链表
2.双向链表
3.循环链表
4.双向循环链表
假如链表中有n个元素。
访问On//访问特定位置的元素
插入删除O1//必须要要知道插入元素的位置
2.2.1 单链表
单链表 单向链表只有一个方向点解只有一个后继指针next指向后面的节点。因此链表这种数据结构通常在物理内存上不是连续的。我们习惯性地把第一个结点叫头结点链表通常有一个不保存任何值的head节点头结点通过头结点我们可以遍历整个链表。为节点通常指向null。 2.2.2 循环链表
循环链表其实是一种特殊的单链表和单链表不同的是循环链表的尾结点不是指向null。而是指向链表的头结点。 2.2.3 双向链表
双向链表 包含两个指针一个prev指向前一个结点一个next指向后一个结点。 2.2.4 双向循环链表
双向循环链表 最后一个结点的next指向head而head的prev指向最后一个结点构成一个环。 2.3 应用场景
如果需要支持随机访问的话链表没办法做到。如果需要存储的数据元素的个数不确定并且需要经常添加和删除数据的话使用链表比较合适。如果需要存储的数据元素的个数确定并且不需要经常添加和删除数据的话使用数组比较合适。 2.4 数组vs链表
数组支持随机访问而链表不支持。数组使用的是连续内存空间对 CPU 的缓存机制友好链表则相反。数组的大小固定而链表则天然支持动态扩容。如果声明的数组过小需要另外申请一个更大的内存空间存放数组元素然后将原数组拷贝进去这个操作是比较耗时的 3.栈
3.1 栈简介 栈Stack只允许在有序的线性数据集合的一端称为栈顶top进行加入数据push和移除数据pop。因而按照 后进先出LIFO, Last In First Out 的原理运作。在栈中push和pop的操作都发生在栈顶。
栈常用一维数组或链表来实现用数组实现的栈叫做顺序栈用链表实现的栈叫做链式栈。
假设堆栈中有n个元素。
访问On//最坏情况
插入删除O1//顶端插入和删除元素 3.2 栈的常见应用场景
当我们要处理的数据只涉及在一端插入和删除数据并且满足 后进先出LIFO, Last In First Out 的特性时我们就可以使用栈这个数据结构。 3.2.1. 实现浏览器的回退和前进功能 我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候你点击回退按钮我们依次把 4,3 这两个页面从 Stack1 弹出然后压入 Stack2 中。假如你又想回到页面 3你点击前进按钮我们将 3 页面从 Stack2 弹出然后压入到 Stack1 中。示例图如下: 3.3.2 检查符号是否成对出现 给定一个只包括 (){}[] 的字符串判断该字符串是否有效。 有效字符串需满足 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 比如 ()、()[]{}、{[]} 都是有效字符串而 (]、([)] 则不是。 这个问题实际是 Leetcode 的一道题目我们可以利用栈 Stack 来解决这个问题。
首先我们将括号间的对应规则存放在 Map 中这一点应该毋容置疑创建一个栈。遍历字符串如果字符是左括号就直接加入stack中否则将stack 的栈顶元素与这个括号做比较如果不相等就直接返回 false。遍历结束如果stack为空返回 true。
public boolean isValid(String s){// 括号之间的对应规则HashMapCharacter, Character mappings new HashMapCharacter, Character();mappings.put(), ();mappings.put(}, {);mappings.put(], [);StackCharacter stack new StackCharacter();char[] chars s.toCharArray();for (int i 0; i chars.length; i) {if (mappings.containsKey(chars[i])) {char topElement stack.empty() ? # : stack.pop();if (topElement ! mappings.get(chars[i])) {return false;}} else {stack.push(chars[i]);}}return stack.isEmpty();
}3.2.3 反转字符串 将字符串中的每个字符先入栈再出栈就可以了。
3.2.4 维护函数调用
最后一个被调用的函数必须先完成执行符合栈的 后进先出LIFO, Last In First Out 特性。 例如递归函数调用可以通过栈来实现每次递归调用都会将参数和返回地址压栈。
3.2.5深度优先遍历
在深度优先搜索过程中栈被用来保存搜索路径以便回溯到上一层。 3.3 栈的实现
栈既可以通过数组实现也可以通过链表来实现。不管基于数组还是链表入栈、出栈的时间复杂度都为 O(1)。 下面我们使用数组来实现一个栈并且这个栈具有push()、pop()返回栈顶元素并出栈、peek() 返回栈顶元素不出栈、isEmpty()、size()这些基本的方法。
public class MyStack {private int[] storage;//存放栈中元素的数组private int capacity;//栈的容量private int count;//栈中元素数量private static final int GROW_FACTOR 2;//不带初始容量的构造方法。默认容量为8public MyStack() {this.capacity 8;this.storagenew int[8];this.count 0;}//带初始容量的构造方法public MyStack(int initialCapacity) {if (initialCapacity 1)throw new IllegalArgumentException(Capacity too small.);this.capacity initialCapacity;this.storage new int[initialCapacity];this.count 0;}//入栈public void push(int value) {if (count capacity) {ensureCapacity();}storage[count] value;}//确保容量大小private void ensureCapacity() {int newCapacity capacity * GROW_FACTOR;storage Arrays.copyOf(storage, newCapacity);capacity newCapacity;}//返回栈顶元素并出栈private int pop() {if (count 0)throw new IllegalArgumentException(Stack is empty.);count--;return storage[count];}//返回栈顶元素不出栈private int peek() {if (count 0){throw new IllegalArgumentException(Stack is empty.);}else {return storage[count-1];}}//判断栈是否为空private boolean isEmpty() {return count 0;}//返回栈中元素的个数private int size() {return count;}}
验证
MyStack myStack new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i 0; i 8; i) {System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//报错java.lang.IllegalArgumentException: Stack is empty.
4 队列
4.1 队列简介
队列是先进先出 (FIFOFirst In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现用数组实现的队列叫作 顺序队列 用链表实现的队列叫作 链式队列 。队列只允许在后端rear进行插入操作也就是入队 enqueue在前端front进行删除操作也就是出队 dequeue 队列的操作方式和堆栈类似唯一的区别在于队列只允许新数据在后端进行添加。 假设队列中有n个元素。 访问On//最坏情况 插入删除O1//后端插入前端删除元素 4.2 队列分类
4.2.1 单队列
单队列就是常见的队列, 每次添加元素时都是添加到队尾。单队列又分为 顺序队列数组实现 和 链式队列链表实现。
顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。
假设下图是一个顺序队列我们将前两个元素 1,2 出队并入队两个元素 7,8。当进行入队、出队操作的时候front 和 rear 都会持续往后移动当 rear 移动到最后的时候,我们无法再往队列中添加数据即使数组中还有空余空间这种现象就是 ”假溢出“ 。除了假溢出问题之外如下图所示当添加元素 8 的时候rear 指针移动到数组之外越界。 为了避免当只有一个元素的时候队头和队尾重合使处理变得麻烦所以引入两个指针front 指针指向对头元素rear 指针指向队列最后一个元素的下一个位置这样当 front 等于 rear 时此队列不是还剩一个元素而是空队列。——From 《大话数据结构》 4.2.2 循环队列
循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是从头开始这样也就会形成头尾相接的循环这也就是循环队列名字的由来。 还是用上面的图我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候 rear 向后移动。 顺序队列中我们说 frontrear 的时候队列为空循环队列中则不一样也可能为满如上图所示。解决办法有两种
可以设置一个标志变量 flag,当 frontrear 并且 flag0 的时候队列为空当frontrear 并且 flag1 的时候队列为满。队列为空的时候就是 frontrear 队列满的时候我们保证数组还有一个空闲的位置rear 就指向这个空闲位置如下图所示那么现在判断队列是否为满的条件就是(rear1) % QueueSizefront 。
4.2.3 双端队列
双端队列 (Deque) 是一种在队列的两端都可以进行插入和删除操作的队列相比单队列来说更加灵活。
一般来说我们可以对双端队列进行 addFirst、addLast、removeFirst 和 removeLast 操作。
4.2.4 优先队列
优先队列 (Priority Queue) 从底层结构上来讲并非线性的数据结构它一般是由堆来实现的。
在每个元素入队时优先队列会将新元素其插入堆中并调整堆。在队头出队时优先队列会返回堆顶元素并调整堆。
关于堆的具体实现可以看堆这一节。
总而言之不论我们进行什么操作优先队列都能按照某种排序方式进行一系列堆的相关操作从而保证整个集合的有序性。
虽然优先队列的底层并非严格的线性结构但是在我们使用的过程中我们是感知不到堆的从使用者的眼中优先队列可以被认为是一种线性的数据结构一种会自动排序的线性队列。
4.3 队列的常见应用场景 当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。 阻塞队列 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候出队操作阻塞当队列满的时候入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。线程池中的请求/任务队列 线程池中没有空闲线程时新的任务请求线程资源时线程池该如何处理呢答案是将这些请求放在队列中当有空闲线程的时候会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列除非系统资源耗尽比如FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了当队列满的话后面再有任务/请求就会拒绝在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。栈双端队列天生便可以实现栈的全部功能push、pop 和 peek并且在 Deque 接口中已经实现了相关方法。Stack 类已经和 Vector 一样被遗弃现在在 Java 中普遍使用双端队列Deque来实现栈。广度优先搜索BFS在图的广度优先搜索过程中队列被用于存储待访问的节点保证按照层次顺序遍历图的节点。 Linux 内核进程队列按优先级排队现实生活中的派对播放器上的播放列表;消息队列等等……
