AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

算法与数据结构全阶班-左程云版（二）基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表（上）

2022-11-24 147
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文主要介绍了一些常用的数据结构，包括链表、栈、队列、递归、哈希表和有序表。

引言

本文主要介绍了一些常用的数据结构，包括链表、栈、队列、递归、哈希表和有序表。

1.链表结构

单链表节点结构：

class Node {
      public int value;
      public Node next;
      public Node(int data) {
          value = data;
      }
  }

双向链表节点结构：

class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;
    public DoubleNode(int data) {
        value = data;
    }
}

简单练习：

1）单链表和双链表如何反转

2）把给定值都删除


实现如下：

// 反转单链表
public static Node reverseLinkedList(Node head) {
    Node pre = null;
    Node next = null;
    while (null != head) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
// 反转双向链表
public static DoubleNode reverseDoubleList(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (null != head) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}
// 删除单链表元素
public static Node removeValue(Node head, int num) {
    // 跳过链表头部值为num的部分
    while (head != null) {
        if (head.value != num) {
            break;
        }
        head = head.next;
    }
    // 头节点为第一个值不为num的节点
    Node pre = head;
    Node cur = head;
    while (cur != null) {
        // pre始终保持其值不等于num
        if (num == cur.value) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
// 删除双向链表元素
public static DoubleNode removeValue(DoubleNode head, int num) {
    // 跳过头节点
    while (head != null) {
        if (head.value != num) {
            break;
        }
        head = head.next;
    }
    if (head != null) {
        head.last = null;
    }
    DoubleNode cur = head, pre = head;
    while (cur != null) {
        if (cur.value == num) {
            pre.next = cur.next;
            cur.last = null;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

Java和C++在垃圾回收方面存在区别：


当一块内存空间所对应的变量或引用不存在时，就会自动释放这块内存，Java存在内存泄漏的原因是因为变量的生命周期不同，例如一个生命周期较短的方法中对一个生命周期更长的数据结构进行了操作，但是调用结束时并没有恢复，简单来说，内存空间找不到对应变量或引用就会被释放，否则就不会被释放；


C++ 内存泄漏是因为声明的变量忘记释放，必须手动调用函数释放。

2.栈和队列

栈：数据先进后出，犹如弹匣；

队列：数据先进先出，好似排队。

栈和队列的实现：

（1）基于双向链表

package structure02;
/**
 * @author Corley
 * @date 2021/10/7 14:02
 * @description LeetCodeAlgorithmZuo-structure02
 */
public class LinkedListQueueStack {
    /*
    自定义节点
     */
    static class Node<T> {
        public Node<T> last;
        public Node<T> next;
        public T value;
        public Node(T value) {
            this.value = value;
        }
    }
    /*
    自定义双向链表
     */
    static class DoubleLinkedList<T> {
        public Node<T> head;
        public Node<T> tail;
        public void addFromHead(T value) {
            Node<T> cur = new Node<>(value);
            if (null == head) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }
        public void addFrombottom(T value) {
            Node<T> cur = new Node<>(value);
            if (null == head) {
                head = cur;
                tail = null;
            } else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }
        public T popFromHead() {
            if (null == head) {
                return null;
            }
            T res = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            return res;
        }
        public T popFromBottom() {
            if (null == head) {
                return null;
            }
            T res = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            return res;
        }
        public boolean isEmpty() {
            return null == head;
        }
    }
    /*
    自定义栈
     */
    static class Stack<T> {
        private final DoubleLinkedList<T> stack;
        public Stack() {
            stack = new DoubleLinkedList<>();
        }
        public void push(T value) {
            stack.addFromHead(value);
        }
        public T pop() {
            return stack.popFromHead();
        }
        public boolean isEmpty() {
            return stack.isEmpty();
        }
    }
    /*
    自定义队列
     */
    static class Queue<T> {
        private final DoubleLinkedList<T> queue;
        public Queue() {
            queue = new DoubleLinkedList<>();
        }
        public void push(T value) {
            queue.addFromHead(value);
        }
        public T pop() {
            return queue.popFromBottom();
        }
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }
}

（2）基于数组

使用数组时，需要考虑数组的大小问题，这里选择使用固定长度的数组来实现。

其中，数组实现较麻烦，如下：

2345_image_file_copy_104.jpg

实现如下：

package structure02;
/**
 * @author Corley
 * @date 2021/10/7 14:50
 * @description LeetCodeAlgorithmZuo-structure02
 * 使用环形数组RingBuffer的思想实现队列
 */
public class ArrayQueueStack {
    static class Queue {
        private final int[] arr;
        private int pushi;          // 加元素的下标
        private int pulli;          // 取元素的下标
        private int size;
        private final int limit;    // 队列大小
        public Queue(int limit) {
            arr = new int[limit];
            pushi = 0;
            pulli = 0;
            size = 0;
            this.limit = limit;
        }
        public void push(int num) {
            if (size == limit) {
                throw new RuntimeException("队列已满，不能再添加元素！");
            }
            size++;
            arr[pushi] = num;
            pushi = nextIndex(pushi);
        }
        public int pull() {
            if (isEmpty()) {
                throw new RuntimeException("队列已空，不能再取元素！");
            }
            size--;
            int res = arr[pulli];
            pulli = nextIndex(pulli);
            return res;
        }
        public boolean isEmpty() {
            return 0 == size;
        }
        private int nextIndex(int index) {
            return index < (limit - 1) ? (index + 1) : 0;
        }
    }
    class Stack {
        int[] arr;
        int size;
        int limit;
        public Stack(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }
        public void push(int num) {
            if (size == limit) {
                throw new RuntimeException("栈已满，不能再添加元素！");
            }
            arr[size++] = num;
        }
        public int pop() {
            if (0 == size) {
                throw new RuntimeException("栈已空，不能再取元素！");
            }
            return arr[--size];
        }
    }
}

既然语言都提供了这些结构和API，为什么还需要手写代码：


1）算法问题无关语言；

2）语言提供的API是有限的，当有新的功能是API不提供的就需要改写；

3）任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的。


实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

1)pop: push、getMin操作的时间复杂度都是O(1)；

2)设计的栈类型可以使用现成的栈结构。


实现思路1如下：


维护两个栈，一个栈保存数据，另一个栈保存到当前高度的最小值，如下：


2345_image_file_copy_106.jpg

实现如下：

static class MinStack1 {
    private final Stack<Integer> stackData;
    private final Stack<Integer> stackMin;
    public MinStack1() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }
    public void push(int num) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(num);
        } else if (num < this.stackMin.peek()) {
            this.stackMin.push(num);
        } else {
            this.stackMin.push(this.stackMin.peek());
        }
        this.stackData.push(num);
    }
    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty!");
        }
        stackMin.pop();
        return stackData.pop();
    }
    public int getMin() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty!");
        }
        return  stackMin.peek();
    }
}

实现思路2如下：


维护两个栈，一个栈保存数据，一个栈保存到当前高度的最小值，但是只有当当前要入栈的数≤之前（栈下面）的最小值时才入最小栈，会节省一些空间，但是会增加时间，因为增加了逻辑判断，如下：

2345_image_file_copy_107.jpg

实现如下：

static class MinStack2 {
    private final Stack<Integer> stackData;
    private final Stack<Integer> stackMin;
    public MinStack2() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }
    public void push(int num) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(num);
        } else if (num <= this.stackMin.peek()) {
            this.stackMin.push(num);
        }
        this.stackData.push(num);
    }
    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty!");
        }
        int res = stackData.pop();
        if (res == getMin()) {
            stackMin.pop();
        }
        return res;
    }
    public int getMin() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty!");
        }
        return  stackMin.peek();
    }
}

栈和队列的常见面试题：

1)如何用栈结构实现队列结构；

2)如何用队列结构实现栈结构。


用队列实现栈：

用两个队列来实现，包括原始队列和辅助队列，如下：


2345_image_file_copy_108.jpg

两个队列角色互相切换。


实现如下：

static class TwoQueueStack<T> {
    private Queue<T> queue;
    private Queue<T> help;
    public TwoQueueStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }
    public void push(T value) {
        queue.offer(value);
    }
    public T pop() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        T res = queue.poll();
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return res;
    }
    public T peek() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        T res = queue.poll();
        help.offer(res);
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return res;
    }
    public boolean isEmpty() {
        return queue.isEmpty();
    }
}


文章标签：
Java
C++
API
算法
关键词：
数据结构算法
算法数据结构
数据结构链表队列
链表栈队列
链表栈
游客lp5523v766t2y
目录
相关文章
龙大吉
|
18天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
39 5
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
23 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
35 2
dlwlrma-晴子
|
2月前
|
存储 缓存 算法
经典算法之链表篇（三）
经典算法之链表篇（三）
dlwlrma-晴子
74 4
dlwlrma-晴子
|
2月前
|
算法
经典算法之链表篇（二）
经典算法之链表篇（二）
dlwlrma-晴子
55 4
dlwlrma-晴子
|
2月前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
dlwlrma-晴子
23 4
Codelinghu
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
Codelinghu
33 0
软件算法开发
|
11天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化，以提高数据分类的准确性。通过MATLAB2022A实现，展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为，动态调整SVDD参数，如惩罚因子C和核函数参数γ，以寻找最优参数组合，增强模型的鲁棒性和泛化能力。
软件算法开发
53 31
简简单单做算法
|
17天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法（WOA）优化支持向量机（SVM）参数，针对乳腺癌早期诊断问题，通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤，并附有详细中文注释及操作视频。实验结果显示，WOA-SVM在提高分类精度和泛化能力方面表现出色，为乳腺癌的早期诊断提供了有效的技术支持。
简简单单做算法
58 26
软件算法开发
|
5天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测，包括模型训练与预测两部分。在MATLAB2022A上运行，通过计算状态转移和观测概率预测未来值，并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析，能够有效捕捉隐藏状态及其转换规律，为金融预测提供有力工具。
软件算法开发
19 6

热门文章

最新文章

  • 1
    【数据结构7】查找
  • 2
    学数据结构，只需要基本的编程体验
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    R语言学习笔记（一）数据结构
  • 5
    数据结构学习笔记——链式存储结构实现队列（链队）
  • 6
    数据结构学习笔记——链式存储结构实现栈（链栈）
  • 7
    基于OHCI的USB主机 —— UFI数据结构2
  • 8
    初学python数据结构-切片
  • 9
    数据结构示例——堆排序过程
  • 10
    大数据开发基础的数据结构和算法的数据结构的字符串
  • 1
    刷题训练之链表
    28
  • 2
    【数据结构OJ题】链表分割
    34
  • 3
    【数据结构OJ题】链表的回文结构
    45
  • 4
    【数据结构OJ题】合并两个有序链表
    43
  • 5
    【数据结构OJ题】链表中倒数第k个结点
    39
  • 6
    【数据结构OJ题】链表的中间结点
    28
  • 7
    【数据结构OJ题】反转链表
    28
  • 8
    【数据结构OJ题】移除链表元素
    45
  • 9
    链表的遍历方式
    47
  • 10
    链表的时间复杂度和空间复杂度
    372

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云对象存储OSS收费标准：存储、流量和请求等多个计费项详解