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

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

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

引言

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

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
目录
相关文章
糜终
|
30天前
|
存储 算法 搜索推荐
探索常见数据结构：数组、链表、栈、队列、树和图
探索常见数据结构：数组、链表、栈、队列、树和图
糜终
85 64
java冯坚持
|
23天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二：希尔排序、快速排序（递归、好理解）、归并排序（递归、难理解）
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
java冯坚持
15 1
努力学习的小廉
|
27天前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
努力学习的小廉
16 1
是店小二呀
|
1月前
【初阶数据结构】打破递归束缚：掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚：掌握非递归版快速排序与归并排序
是店小二呀
19 4
1897697198172439
|
5月前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
1897697198172439
38 0
java冯坚持
|
23天前
|
算法 定位技术
数据结构与算法学习九：学习递归。递归的经典实例：打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式，并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
java冯坚持
29 0
睡觉待开机
|
3月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
睡觉待开机
40 1
chian-ocean
|
3月前
【数据结构】遍历二叉树（递归思想）--＞赋源码
【数据结构】遍历二叉树（递归思想）--＞赋源码
chian-ocean
50 4
睡觉待开机
|
3月前
|
算法
【算法】递归总结：循环与递归的区别？递归与深搜的关系？
【算法】递归总结：循环与递归的区别？递归与深搜的关系？
睡觉待开机
71 0
睡觉待开机
|
3月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介
睡觉待开机
27 0

热门文章

最新文章

  • 1
    [剑指offer] 复杂链表的复制
  • 2
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 3
    LeetCode 21：合并两个有序链表 Merge Two Sorted Lists
  • 4
    《C语言及程序设计》实践参考——改造链表
  • 5
    [LeetCode] Rotate List 旋转链表
  • 6
    线性表概述及单链表的Java实现
  • 7
    从尾到头打印链表
  • 8
    IAM页，IAM链表，分配单元
  • 9
    【转】数据结构链表操作之双链表的基本操作
  • 10
    单链表的实现与常见接口的详细图解剖析
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    81
  • 2
    【redis源码学习】持久化机制，java程序员面试算法宝典pdf
    70
  • 3
    对标腾讯T9架构师的 Android 面试题新鲜出炉，算法真的太重要了
    48
  • 4
    【机器学习】K-means算法与PCA算法之间有什么联系？
    240
  • 5
    【机器学习】维度灾难问题会如何影响K-means算法？
    278
  • 6
    【数据结构与算法 11，高并发系统基础篇
    39
  • 7
    sass 公用10个mixins代码块，算法太TM重要了，前端开发要求
    42
  • 8
    前端开发者必知的缓存淘汰策略：LRU算法解析与实践
    191
  • 9
    2024最新Android算法相关面试大全，请查收
    35
  • 10
    【机器学习】聚类算法中，如何判断数据是否被“充分”地聚类，以便算法产生有意义的结果？
    134

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • “大数据+算法”助力B2B未来商业
  • 数据+算法定义新世界
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月