【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-栈和队列
前言
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)
全部源代码已上传 github， 点击我吧 ，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
栈 Statck
- 栈也是一种线性结构
-
相比数组来说相应的操作更少，
- 栈对应的操作是数组的子集，
- 因为它的本质就是一个数组，
- 并且它有比数组更多的限制。
-
栈的本质就是一个数组
- 它将数据排开来放的，
- 添加元素的时候只能从栈的一端添加元素，
- 取出元素的时候也只能栈的一端取出元素，
- 这一端叫做栈顶，当这样的限定了数组，
- 从而形成了栈这种数据结构之后，
- 它可以在计算机世界中对于
- 组建逻辑产生非常非常重要的作用。
-
栈的操作
- 从栈顶添加元素，把元素一个一个的放入到栈中，
- 如添加值的时候为 1、2、3，
- 你取值的时候顺序则为 3、2、1，
- 因为你添加元素是只能从一端放入，
- 取出元素时也只能从一端取出，
- 而这一段就是栈顶，
- 栈的出口和入口都是同一个位置，
- 所以你只能按照先进后出、后进先出的顺序
- 添加数据或者取出数据，不存在插入和索引。
-
栈是一种后进先出的数据结构
- 也就是 Last In First Out(LIFO)，
- 这样的一种数据结构，在计算机的世界里，
- 它拥有着不可思议的作用，
- 无论是经典的算法还是算法设计都接触到
- 栈这种看似很简单但其实应用非常广泛的数据结构，
栈的简单应用
-
无处不在的 Undo 操作（撤销）
- 编辑器的撤销操作的原理就是靠一个栈来进行维护的，
- 如 将 每次输入的内容依次放入栈中 我 喜欢 你，
- 如果 你 字写错，你撤销一下，变成 我 喜欢，
- 再撤销一下 变成 我。
-
程序调用的系统栈
- 程序调用时经常会出现在一个逻辑中间
- 先终止然后跳到另外一个逻辑去执行，
- 所谓的子函数的调用就是这个过程，
- 在这个过程中计算机就需要使用一个
- 称为系统栈的一个数据结构来记录程序的调用过程。
- 例如有三个函数 A、B、C，
- 当 A 执行到一半的时候调用 B，
- 当 B 执行到一半的时候调用 C，
- C 函数可以执行运行完，
- C 函数运行完了之后继续运行未完成的 B 函数，
- B 函数运行完了就运行未完成 A 函数，
- A 函数运行完了就结束了。
function A () { 1 ...; 2 B(); 3 ...; } function B () { 1 ...; 2 C(); 3 ...; } function C () { 1 ...; 2 ...; 3 ...; } -
系统栈记录的过程是：
- A 函数执行，在第二行中断了，因为要去执行函数 B 了，
- 这时候函数信息
A2会被放入系统栈中，系统栈中显示：[A2]， - 然后 B 函数执行，在第二行也中断了，因为要去执行函数 C 了，
- 这时候函数信息 B2 会被放入系统栈中，系统栈中显示：
[A2, B2]， - 然后 C 函数执行，C 函数没有子函数可执行，那么执行到底，函数 C 执行完毕，
- 从系统栈中取出函数 B 的信息，系统栈中显示：
[A2]， - 根据从系统栈中取出的函数 B 的信息，从函数 B 原来中断的位置继续开始执行，
- B 函数执行完毕了，这时候会再从系统栈中取出函数 A 的，系统栈中显示：
[]， - 根据从系统栈中取出的函数 A 的信息，从函数 A 原来中断的位置继续开始执行，
- A 函数执行完了，系统栈中已经没有函数信息了，好的，程序结束。
- 存入系统栈中的是函数执行时的一些信息，
- 所以取出来后，可以根据这些信息来继续完成
- 原来函数未执行完毕的那部分代码。
-
2 和 3 中解释的原理 就是系统栈最神奇的地方
- 在编程的时候进行子过程调用的时候，
- 当一个子过程执行完成之后，
- 可以自动的回到上层调用中断的位置，
- 并且继续执行下去。
- 都是靠一个系统栈来记录每一次调用过程中
- 中断的那个调用的点来实现的。
-
栈虽然是一个非常简单的数据结构
- 但是它能够解决计算机领域非常复杂的一个问题，
- 这个问题就是这种子过程子逻辑的调用，
- 在编译器内部它运行实现的原理是什么，
- 深入理解这个过程，
- 甚至能够帮助你理解一些更复杂的逻辑过程，
- 比如递归这样的一个过程，你会有更加深刻的理解。
栈的实现
-
栈这种数据结构非常有用
- 但其实是非常简单的。
-
MyStack<E>void push(e) E pop() E peek() int getSize() boolean isEmpty()
-
从用户的角度看
- 只要支持这些操作就好了，
- 用户不管你要怎样 resize，
- 他只要知道你这个数组是一个动态的，
- 他可以不停的往里面添加元素，
- 并且不会出现问题就 ok，
- 其实对于栈也是这样的，
- 对于具体的底层实现，用户不关心，
- 实际底层也有多种实现方式，
- 所以用户就更加不关心了。
-
为了让代码更加的清晰，
- 同时也是为了支持面向对象的一些特性，
- 比如说支持多态性，
- 那么就会这样的去设计，
- 定义一个接口叫做 IMyStack，
- 接口中有栈默认的所有方法，
- 然后再定义一个类叫做 MyStack，
- 让它去实现 IMyStack，
- 这样就可以在 MyStack 中完成对应的逻辑，
- 这个 MyStack 就是自定义的栈。
- 会复用到之前自定义数组对象。
栈的复杂度分析
-
MyStack<E>void push(e) E pop() E peek() int getSize() boolean isEmpty()
代码示例
-
(interface: IMyStack, class: MyArray, class: MyStack, class: Main) -
IMyStack
public interface IMyStack<E> { /**
*/
void push(E e);
/**
* @return 出栈
*/
E pop();
/**
* @return 查看栈顶的元素
*/
E peek();
/**
* @return 获取栈中实际元素的个数
*/
int getSize();
/**
* @return 判断栈是否为空
*/
boolean isEmpty();
}
3. MyArray
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 获取数组中第一个元素（纯查看）
public E getFirst () {
return get(0);
}
// 获取数组中最后一个元素（纯查看）
public E getLast () {
return get(size - 1);
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
// 防止复杂度震荡 防止容量为4，size为1时，data.length / 2 为 0
if(size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append(']');
return sb.toString();
}
}
4. MyStack
public class MyStack<E> implements IMyStack<E> {
// 借用自定义个动态数组
private MyArray<E> ma;
public MyStack () {
ma = new MyArray<E>();
}
public MyStack (int capacity) {
ma = new MyArray<E>(capacity);
}
/**
* @param e
* @return 入栈
*/
@Override
public void push(E e) {
ma.addLast(e);
}
/**
* @return 出栈
*/
@Override
public E pop() {
return ma.removeLast();
}
/**
* @return 查看栈顶的元素
*/
@Override
public E peek() {
return ma.getLast();
}
/**
* @return 获取栈中实际元素的个数
*/
@Override
public int getSize() {
return ma.getSize();
}
/**
* @return 判断栈是否为空
*/
@Override
public boolean isEmpty() {
return ma.isEmpty();
}
// 返回栈的容量
public int getCapacity () {
return ma.getCapacity();
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
int size = ma.getSize();
// int capacity = ma.getCapacity();
StringBuilder sb = new StringBuilder();
// String arrInfo = "Stack: size = %d，capacity = %d/n";
// sb.append(String.format(arrInfo, size, capacity));
sb.append("Stack: [");
for (int i = 0; i < size - 1; i ++) {
sb.append(ma.get(i));
sb.append(',');
}
if (!ma.isEmpty()) {
sb.append(ma.getLast());
}
sb.append("] right is stack top !");
return sb.toString();
}
}
5. Main
public class Main {
public static void main(String[] args) {
MyStack ms = new MyStack(10);
for (int i = 1; i <= 10 ; i++) {
ms.push(i);
System.out.println(ms);
}
System.out.println(ms.peek());
// System.out.println(ms.isEmpty());
// System.out.println(ms.getSize());
// System.out.println(ms.getCapacity());
while (!ms.isEmpty()) {
ms.pop();
System.out.println(ms);
}
}
}
## 栈的应用
1. undo 操作-编辑器
2. 系统调用栈-操作系统
3. 括号匹配-编译器
### 以编程的方式体现栈的应用
1. 括号匹配-编译器
1. 无论是写表达式，这个表达式中有小括号、中括号、大括号，
2. 自然会出现括号套括号的情况发生，
3. 在这种情况下就一定会产生一个括号匹配的问题，
4. 如果括号匹配是不成功的，那么编译器会进行报错。
2. 编译器是如何检查括号匹配的问题？
1. 原理是使用了一个栈。
3. 可以通过解答 Leetcode 中的一个问题，
1. 同时来看栈在括号匹配这个问题中的应用。
2. Leetcode 是总部在美国硅谷一家
3. 非常有年头又同时有信誉度的面向 IT 公司
4. 面试这样一个在线的平台，
5. 只需要注册一个 Leetcode 用户后，
6. 就可以看到 Leetcode 上有非常多的问题，
7. 对于每一个问题会规定输入和输出之后，
8. 然后就可以编写属于自己的逻辑，
9. 更重要的是可以直接把你编写的这个程序
10. 提交给这个网站，
11. 这个网站会自动的判断你的逻辑书写的是否正确，
12. 英文网址：`leetcode.com`，
13. 2017 中文网址：`leetcode-cn.com`
4. `leetcode.com`与`leetcode-cn.com`的区别
1. `leetcode-cn.com`支持中文，
2. `leetcode-cn.com`的题目数量没有英文版的多。
3. `leetcode-cn.com`的探索栏目的内容没有英文版的多。
4. `leetcode-cn.com`中的题目没有社区讨论功能，但英文版的有。
5. leetcode 中第二十号题目：有效的括号
1. 如：`{ [ ( ) ] }`，
2. 从左往右，先将左侧的括号入栈，
3. 然后遇到右侧的括号时就查看栈顶的左侧括号进行匹配，
4. 如果可以匹配表示括号有效，否则括号无效，
5. 括号有效那么就将栈顶的左侧括号取出，
6. 然后继续从左往右，左侧括号就入栈，右侧括号就匹配，
7. 匹配成功就让左侧括号出栈，匹配失败就是无效括号。
8. 其实栈顶元素反映了在嵌套的层级关系中，
9. 最新的需要匹配的元素。
10. 这个算法非常的简单，但是也非常的实用。
11. 很多工具中都有这样的逻辑来检查括号的匹配。
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case '{':
case '[':
case '(':
stack.push(c);
break;
default: break;
}
switch (c) {
case '}':
if(stack.isEmpty() || stack.pop() != '{' ) {
System.out.println("valid error. not parentheses. in");
return false;
}
break;
case ']':
if(stack.isEmpty() || stack.pop() != '[') {
System.out.println("valid error. not parentheses. in");
return false;
}
break;
case ')':
if(stack.isEmpty() || stack.pop() != '(') {
System.out.println("valid error. not parentheses. in");
return false;
}
break;
default: break;
}
}
if (stack.isEmpty()) {
System.out.println("valid success. parentheses.");
return true;
} else {
System.out.println("valid error. not parentheses. out.");
return false;
}
}
public static void main(String[] args) {
Solution s = new Solution();
s.isValid("{ [ ( ) ] }");
s.isValid(" [ ( ] ) ");
}
}
// 7ms的
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
int cur = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case '{':
case '[':
case '(':
cur ++;
stack.push(c);
break;
default: break;
}
switch (c) {
case '}':
if(cur-- == 0 || stack.pop() != '{' ) {
return false;
}
break;
case ']':
if(cur-- == 0 || stack.pop() != '[') {
return false;
}
break;
case ')':
if(cur-- == 0 || stack.pop() != '(') {
return false;
}
break;
default: break;
}
}
return cur == 0;
}
}
6. leetcode 是一个非常好的准备面试的一个平台 1. 同时它也是算法竞赛的一个入门的地方。 2. 你可以通过题库来进行训练， 3. 题库的右边有关于这些题目的标签， 4. 你可以选择性的去练习， 5. 而且可以根据难度来进行排序这些题目， 6. 你不一定要全部答对， 7. 因为这些题目不仅仅只有一个标签。 7. 如果你想使用你自己写的类， 1. 那么你可以你自己写的自定义栈作为内部类来进行使用， 2. 例如 把自定义栈的代码放到 Solution 类中， 3. 那样也是可以使用， 4. 还样就顺便测试了你自己数据结构实现的逻辑是否正确。 ### 学习方法讨论 1. 不要完美主义。掌握好“度”。 1. 太过于追求完美会把自己逼的太紧， 2. 会产生各种焦虑的心态，. 最后甚至会怀疑自己， 3. 温故而知新，不要停止不前， 4. 掌握好这个度，不存在你把那些你认为完全掌握了， 5. 然后就成了某一个领域的专家， 6. 相反一旦你产生很浓厚的厌恶感， 7. 那么就意味着你即将会放弃或者已经选择了放弃， 8. 虽然你之前想把它做到 100 分， 9. 但是由于你的放弃让它变为 0 分。 2. 学习本着自己的目标去。 1. 不要在学的过程中偏离了自己的目标。 2. 要分清主次。 3. 难的东西，你可以慢慢的回头看一看。 1. 那样才会更加的柳暗花明， 2. 更能提升自己的收获。 ## 队列 Queue 1. 队列也是一种线性的数据结构 1. 依然就是将数据排成一排。 2. 相比数组，队列对应的操作是数组的子集。 1. 与栈只能在同一端添加元素和取出元素有所不同， 2. 在队列中只能从一端(队尾)添加元素， 3. 只能从另一端(队首)取出元素。 3. 例如你去银行取钱 1. 你需要排队，入队的人不允许插队， 2. 所以他要从队尾开始排队， 3. 而前面取完钱的会从队首离开， 4. 然后后面的人再往前移动一位， 5. 最后重复这个过程， 6. 直到没人再排队取钱了。 4. 队列是一种先进先出的数据结构（先到先得） 1. First In First Out(FIFO) 先进先出 ### 队列的实现 1. `Queue<E>` 1. `void enqueue(E)`：入队 2. `E dequeue()`：出队 3. `E getFront()`：查看队首的元素 4. `int getSize()`：获取队列中的实际元素大小 5. `boolean isEmpty()`：获取队列是否为空的 bool 值 2. 写一个接口叫做 IMyQueue 1. 让 MyQueue 实现这个接口 2. 这样就符合了面向对象的特性。 ### 代码示例 1. `(interface: IMyQueue, class: MyArray, class: MyQueue, class: Main)` 2. IMyQueue
public interface IMyQueue<E> {
/**
* @param e
* 入队
*/
void enqueue (E e);
/**
* @return e
* 出队
*/
E dequeue ();
/**
* @return e
* 查看队首的元素
*/
E getFront ();
/**
* @return number
* 获取队列中的实际元素个数
*/
int getSize ();
/**
* @return bool
* 获取队列是否为空的bool值
*/
boolean isEmpty ();
}
3. MyArray
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 获取数组中第一个元素（纯查看）
public E getFirst () {
return get(0);
}
// 获取数组中最后一个元素（纯查看）
public E getLast () {
return get(size - 1);
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
// 防止复杂度震荡 防止容量为4，size为1时，data.length / 2 为 0
if(size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
sb.append(data[size - 1]);
sb.append(']');
return sb.toString();
}
}
4. MyQueue
public class MyQueue<E> implements IMyQueue<E> {
private MyArray<E> ma;
public MyQueue () {
ma = new MyArray<E>();
}
public MyQueue (int capacity) {
ma = new MyArray<E>(capacity);
}
/**
* @param e
* 入队
*/
@Override
public void enqueue (E e) {
ma.addLast(e);
}
/**
* @return e
* 出队
*/
@Override
public E dequeue () {
return ma.removeFirst();
}
/**
* @return e
* 查看队首的元素
*/
@Override
public E getFront () {
return ma.getFirst();
}
/**
* @return number
* 获取队列中的实际元素个数
*/
@Override
public int getSize () {
return ma.getSize();
}
/**
* @return bool
* 获取队列是否为空的bool值
*/
@Override
public boolean isEmpty () {
return ma.isEmpty();
}
// 获取队列容量
public int getCapacity () {
return ma.getCapacity();
}
@Override
public String toString () {
int size = ma.getSize ();
StringBuilder sb = new StringBuilder();
sb.append("Queue: head [");
for (int i = 0; i < size - 1; i ++) {
sb.append(ma.get(i));
sb.append(',');
}
if(!isEmpty()) {
sb.append(ma.getLast());
}
sb.append("] foot. left is queue top!");
return sb.toString();
}
}
5. Main
public class Main {
public static void main(String[] args) {
MyQueue<Integer> mq = new MyQueue<Integer>(10);
for (int i = 1; i <= 10 ; i++) {
mq.enqueue(i);
System.out.println(mq);
}
System.out.println(mq.getFront());
while (!mq.isEmpty()) {
System.out.println(mq);
mq.dequeue();
}
}
}
### 队列的复杂度分析 1. `MyQueue<E>` 1. `void enqueue(E)`： `O(1)` 均摊 2. `E dequeue()`：`O(n)` 出队的性能消耗太大了 3. `E getFront()`：`O(1)` 4. `int getSize()`：`O(1)` 5. `boolean isEmpty()`：`O(1)` 2. 出队的性能消耗太大了 1. 如果有一百万条数据，每次都要操作一百万次， 2. 那么需要优化它，要让他出队的时候时间复杂度为`O(1)`， 3. 并且还要让他入队的时候时间复杂度依然是`O(1)`。 4. 可以使用循环队列的方式来解决这个问题。 ## 循环队列 1. 自定义队列的性能是有局限性的 1. 出队操作时的时间复杂度为`O(n)`， 2. 要把他变为`O(1)`。 2. 当取出队列的第一个元素后， 1. 第一个元素后面所有的元素位置不动， 2. 这样一来时间复杂度就为`O(1)`了， 3. 下一次再取元素的时候从第二个开始， 4. 取完第二个元素之后， 5. 第二个元素后面所有的元素位置也不动， 6. 入队的话直接往队尾添加元素即可。 3. 循环队列的使用 1. 你可以先用一个数字变量 front 指向队首， 2. 然后再用一个数字变量 tail 指向队尾， 3. front 指向的是队列中的第一个元素， 4. tail 指向的是队列中最后一个元素的后一个位置， 5. 当队列整体为空的时候，它们才会指向同一个位置， 6. 所以`front == tail`时队列就为空， 7. 如果有一个元素入队了， 8. front 会指向这个元素， 9. 而 tail 会指向这个元素后一个位置（也就是 tail++）， 10. 然后再有一个元素入队了， 11. front 还是指向第一个元素的位置， 12. 而 tail 会指向第二个元素的后一个位置（还是 tail++）， 13. 然后再来四个元素入队了， 14. front 还是指向第一个元素的位置， 15. 而 tail 会指向第六个元素的后一个位置（tail++四次）， 16. 之后 要出队两个元素， 17. front 会指向第三个元素的位置（也就是 front++两次）， 18. front 从指向第一个元素变成指向第三个元素的位置， 19. 因为前两个已经出队了， 20. 这时候再入队一个元素， 21. tail 会指向第七个元素的后一个位置（还是 tail++）， 22. 这时队列的容量已经满了，可能需要扩容， 23. 但是由于队列中有两个元素已经出队了， 24. 那这两个位置空出来了，这时就需要利用这两个位置的空间了， 25. 这就是循环队列了，以循环的方式重复利用空间， 26. 自定义队列使用自定义数组实现的， 27. 其实就是把数组看成一个环，数组中一共可以容纳 8 个元素， 28. 索引是 0-7，那么 7 之后的索引应该是 0，tail 应该指向 0， 29. 而不是认为整个数组的空间已经满了， 30. 应该使用 tail 对数组的容量进行求余计算， 31. tail 为 8，容量也为 8，求余之后为 0，所以 tail 应该指向 0， 32. 这时再入队一个元素，tail 指向这个元素的后一个位置，即 1， 33. 这时候如果再入队一个元素，那么此时 tail 和 front 相等， 34. 但是那并不能证明队列为空，反而是队列满了， 35. 所以需要在队列满之前进行判断，`tail+1==front`， 36. 就表示队列已满，当数组中只剩最后一个空间了， 37. 队列就算是满的，因为再入队就会让 tail 与 front 相等， 38. 而那个条件是队列已空才成立的，虽然对于整个数组空间来说， 39. 是有意识地浪费了一个空间，但是减少了很大的时间消耗， 40. 所以当`(tail+1)%c==front`时就可以扩容了， 41. 将`tail+1==front`变成`(tail+1)%c==front`是因为 42. tail 从数组的末端跑到前端是有一个求余的过程， 43. 例如 front 指向的是第一个元素，而 tail 指向的第六个元素之后的位置， 44. 那么此时 front 为 0，tail 为 7，容量为 8，还有一个浪费掉的空间， 45. 这时候`(tail+1)%c==front`，所以队列满了， 46. 这就是循环队列所有的具体实现必须遵守的规则， 47. 所有的 front 和 tail 向后移动的过程都要是这种循环的移动， 48. 例如钟表，11 点钟的下一个钟头为 12 点钟，也可以管它叫做 0 点， 49. 之后又会变成 1 点、2 点、3 点、4 点依次类推， 50. 所以整个循环队列的索引也是像钟表一样形成了一个环， 51. 只不过不一定有 12 刻度，而刻度的数量是由数组的容量(空间总数)决定的， 52. 这就是循环队列的原理。 4. 使用循环队列之后， 1. 出队操作不再是整体往前移动一位了 2. 而是通过改变 front 的指向， 3. 入队操作则是改变 tail 的指向， 4. 整个操作循环往复， 5. 这样一来出队入队的时间复杂度都为`O(1)`了。 ### 循环队列的简单实现解析 1. 循环队列 MyLoopQueue 1. 他的实现与 MyQueue 有很大的不同， 2. 所以就不使用 MyArray 自定义动态数组了。 2. 循环队列要从底层重新开始写起 1. data：一个数组。 2. front： 指向队头有效元素的索引。 3. tail： 指向队尾有效元素的后一个位置的索引。 4. size： 通过 front 和 tail 也可以做到循环。 5. 但是使用 size 能够让逻辑更加的清晰明了。 3. 循环队列实现完毕之后， 1. 你可以不使用 size 来进行循环队列的维护， 2. 而完完全全的使用 front 和 tail， 3. 这样难度会稍微的难一点， 4. 因为具体逻辑需要特别的小心， 5. 会有一些小陷阱。 6. 可以试着添加 resize 数组扩容缩容功能到极致， 7. 可以锻炼逻辑能力、程序编写调试能力等等。 ## 循环队列的实现 1. 入队前先判断队列是否已经满了 1. 判断方式 `(tail + 1) % data.length == front` 2. 判断分析 (队尾指向的索引 + 1)余以数组的容量是否为队首指向的索引， 2. 从用户的角度上来看 1. 队列里就是有这么多元素， 2. 一侧是队首一侧是队尾， 3. 其它的内容包括实际的数组的大小是用户指定的容量大小+1， 4. 这些实现细节，用户是全部不知道的，给用户屏蔽掉了， 5. 这就是封装自定义数据结构的目的所在， 6. 用户在具体使用这些自定义数据结构的时候， 7. 只需要了解接口中所涉及到的这些方法即可， 8. 至于它的内部细节用户完全可以不用关心。 ### 代码示例 `(class: MyLoopQueue, class: Main)` 1. MyLoopQueue
public class MyLoopQueue<E> implements IMyQueue<E> {
private E[] data;
private int front, tail;
private int size;
public MyLoopQueue (int capacity) {
// 这个数组的容量为 传进来的指定容量+1，
// 因为会有意识的浪费一个空间，只有+1后，
// 才能装下用户期望传进来的所有数据
data = (E[])new Object[capacity + 1];
front = tail = size = 0;
}
public MyLoopQueue () {
this(10);
}
public int getCapacity () {
return data.length - 1;
}
private void resize (int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
// 索引可能会越界，于是就要取余一下，
// 如果越界了，就从队首开始
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
/**
* @param e 入队
*/
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {
resize(getCapacity() * 2);
}
data[tail] = e;
// tail在队列中循环
tail = (tail + 1) % data.length;
size ++;
}
/**
* @return e
* 出队
*/
@Override
public E dequeue() {
if(isEmpty()) {
throw new IllegalArgumentException("can't dequeue from an empty queue.");
}
E e = data[front];
data[front] = null;
front = (front + 1) % data.length;
size -- ;
if (getCapacity() / 4 == size && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return e;
}
/**
* @return e
* 查看队首的元素
*/
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("queue is empty.");
}
return data[front];
}
/**
* @return number
* 获取队列中的实际元素个数
*/
@Override
public int getSize() {
return size;
}
/**
* @return bool
* 获取队列是否为空的bool值
*/
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
sb.append(String.format("Queue: size = %d，capacity = %d /n", size, getCapacity()));
sb.append("Queue: head [");
// 第一种遍历方式
// for (int i = 0; i < size - 1; i ++) {
// sb.append(data[(front + i) % data.length]);
// sb.append(',');
// }
// if(!isEmpty()) {
// sb.append(data[(front + size - 1) % data.length]);
// }
// 第二种遍历方式
for (int i = front; i != tail ; i = (i + 1) % data.length) {
sb.append(data[i]);
if ((i + 1) % data.length != tail) {
sb.append(',');
}
}
sb.append("] foot. left is queue top!");
sb.append("/n");
return sb.toString();
}
}
2. Main
public class Main {
public static void main(String[] args) {
// MyQueue<Integer> mq = new MyQueue<Integer>(10);
MyLoopQueue<Integer> mq = new MyLoopQueue<Integer>(10);
for (int i = 1; i <= 11 ; i++) {
mq.enqueue(i);
System.out.println(mq);
}
System.out.println(mq.getFront());
while (!mq.isEmpty()) {
System.out.println(mq);
mq.dequeue();
}
}
}
## 自定义队列两种方式的对比 1. 原来自定队列的出队时，时间复杂度为`O(n)`， 1. 使用循环队列的方式后， 2. 出队时时间复杂度为`O(1)`， 3. 复杂度的分析只是一个抽象上的理论结果， 4. 具体这个变化在性能上意味着会有一个质的飞跃， 5. 队列中元素越多，性能就更能够体现出来。 ### 自定义队列的时间复杂度对比 1. `MyQueue<E>`：数组队列，使用了自定义数组 1. `void enqueue(E)`：`O(1)` 均摊 2. `E dequeue()`：`O(n)` 出队的性能消耗太大了 3. `E getFront()`：`O(1)` 4. `int getSize()`：`O(1)` 5. `boolean isEmpty()`：`O(1)` 2. `MyLoopQueue<E>`：循环队列，没有使用自定义数组 1. `void enqueue(E)`：`O(1)` 均摊 2. `E dequeue()`：`O(1)` 均摊 3. `E getFront()`：`O(1)` 4. `int getSize()`：`O(1)` 5. `boolean isEmpty()`：`O(1)` ### 循环队列的复杂度分析 1. 通过设置循环队列底层的机制 1. 虽然稍微比数组队列要复杂一些， 2. 但是这些复杂的工作是值得的， 3. 因为他使得在数组队列中， 4. 出队本该有`O(n)`的复杂度变为了`O(1)`的复杂度， 5. 但是这个`O(1)`为均摊的时间复杂度， 6. 因为出队还是会涉及到缩容的操作， 7. 在缩容的过程中还是免不了对队列中所有的元素进行一次遍历， 8. 但是由于不可能每一次操作都会触发缩容操作来遍历所有的元素， 9. 所以应该使用均摊复杂度的分析方式，那样才更加合理。 2. 循环队列中所有的操作都是`O(1)`的时间复杂度。 3. `O(n)`的复杂度要比`O(1)`要慢， 1. 但是具体会慢多少可以通过程序来进行测试， 2. 这样就能够知道在算法领域和数据结构领域 3. 要费这么大的劲去研究更加优化的操作 4. 这背后实际的意义到底在哪里。 4. 让这两个队列进行入队和出队操作， 1. 操作的次数为 100000 次， 2. 通过在同一台机器上的耗时情况， 3. 就能够知道性能有什么不同。 5. 数据队列与循环队列十万次入队出队操作后的结果是： 1. `MyQueue，time：15.463472711s`， 2. `MyLoopQueue，time：0.009602136s`， 3. 循环队列就算操作一亿次， 4. 时间也才`MyLoopQueue，time：2.663835877s`， 5. 这个差距主要是在出队的操作中体现出来的， 6. 这个性能差距是上千倍，所以这也是性能优化的意义。 6. 测试性能时，不要只测试一次，你可以测试 100 次 1. 取平均值即可，因为这不光和你的程序相关， 2. 还会和你当前计算机的状态有关， 3. 特别是在两个算法的时间复杂度一致时， 4. 测试性能时可能出入会特别大， 5. 因为这有多方面原因、如语法、语言、编译器、解释器等等， 6. 这些都会导致你代码真正运行的逻辑机制 7. 和你理论分析的是不一样的， 8. 但是当两个算法的时间复杂度不一致时， 9. 这时候测试性能的结果肯定会有巨大的差异， 10. 如`O(1)`对`O(n)`、`O(n)`对`O(n^2)`、`O(n)`对`O(logn)`。 ### 队列的应用 1. 队列的概念在生活中随处可见 1. 所以使用计算机来模拟生活中队列， 2. 如在业务方面你需要排队， 3. 或者更加专业的一些领域， 4. 比如 网络数据包的排队、 5. 操作系统中执行任务的排队等， 6. 都可以使用队列。 2. 队列本身是一个很复杂的问题 1. 对于排队来说，队首到底怎么定义， 2. 是有多样的定义方式的，也正因为如此， 3. 所以存在广义队列这个概念， 4. 这两种自定义队列 5. 在组建计算机世界的其它算法逻辑的时候 6. 也是有重要的应用的，最典型的应用是广度优先遍历。
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
