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

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

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

引言

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

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
目录
相关文章
陌陌谣
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据，传统数据结构存在性能瓶颈。红黑树通过自平衡机制，确保查找、插入、删除操作的时间复杂度稳定在 O(log n)，适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现，并探讨其在企业监控系统中的实践价值，提升系统性能与稳定性。
陌陌谣
85 1
陌陌谣
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表（Skip List）是一种基于概率的数据结构，适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作，时间复杂度为 $O(\log n)$，优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色，具备实现简单、支持范围查询等优势，是企业网络监控中动态数据管理的理想选择。
陌陌谣
97 0
修己xj
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
204 10
算法系列之数据结构-二叉树
修己xj
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树（哈夫曼树）又称最优二叉树，是一种带权路径长度最短的二叉树，常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率，通过将频率较低的字符组合在一起，最终形成一棵树。在Huffman树中，每个叶节点代表一个字符，而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
修己xj
166 3
算法系列之数据结构-Huffman树
修己xj
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树（Binary Search Tree，简称BST）是一种常用的数据结构，它能够高效地进行查找、插入和删除操作。二叉查找树的特点是，对于树中的每个节点，其左子树中的所有节点都小于该节点，而右子树中的所有节点都大于该节点。
修己xj
219 22
ephemerals__
|
11月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
907 9
那年春天
|
11月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
234 59
hahaha无
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
67 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
4月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
78 0
RossyYan
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
356 77

热门文章

最新文章

  • 1
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 4
    率先实现后量子安全算法技术落地上车！阿里云与小鹏汽车签署后量子加密安全合作协议
  • 5
    软考中级软件设计师专项-数据结构与算法上篇
  • 6
    动态规划算法深度解析：0-1背包问题
  • 7
    从零构建短视频推荐系统：双塔算法架构解析与代码实现
  • 8
    【机器人路径规划】基于6种算法（黑翅鸢优化算法BKA、SSA、MSA、RTH、TROA、COA）求解机器人路径规划研究（Matlab代码实现）
  • 9
    从另一个视角看Transformer：注意力机制就是可微分的k-NN算法
  • 10
    DDMA-MIMO雷达多子带相干累积目标检测算法——论文阅读
  • 1
    AI是如何收集体育数据的？从摄像头到算法，揭秘赛场背后的“数字间谍网“！
    124
  • 2
    zk基础—1.一致性原理和算法
    133
  • 3
    内网实时监控中的 C# 算法探索：环形缓冲区在实时数据处理中的关键作用
    197
  • 4
    基于遗传优化ELM网络的时间序列预测算法matlab仿真
    86
  • 5
    基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
    99
  • 6
    NOMA和OFDMA优化算法分析
    252
  • 7
    基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
    84
  • 8
    基于遗传优化算法的带时间窗多车辆路线规划matlab仿真
    88
  • 9
    基于遗传算法的64QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
    91
  • 10
    基于云模型的车辆行驶速度估计算法matlab仿真
    59

    • 相关课程

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

    • 相关电子书

    更多
  • “大数据+算法”助力B2B未来商业
  • 数据+算法定义新世界
  • Apache Flink 流式应用中状态的数据结构定义升级
    • 下一篇
    阿里云无影云电脑免费使用_免费申请教程