• 2022-06-26 数据结构-数组、链表、栈、队列

    数据结构-数组、链表、栈、队列

    学习数据结构与算法之美记录，之前已经看数据结构与算法视频过了三遍，每次看完就结束，这次一定学习+动手，后续每天或每周抽出时间做题保持学习状态

    数组

    一段连续存储的空间，可以通过下标定位到对应位置的线性结构

    链表

    由多个节点组成，每个节点有一或两个指针指向其它节点，构成的线性结构。
    种类：

    • 单向链表
    package com.zsl.datastructalgorithm.date20220625;

import lombok.Data;

/**
 * 实现单链表反转
 *
 * @Author zsl
 * @Date 2022/6/25 22:22
 * @Email 249269610@qq.com
 */
public class SingleLinkedList<T> {

    // 头
    private Node<T> head;
    // 尾
    private Node<T> tail;
    // 大小
    private int size = 0;

    /**
     * 新增元素
     */
    public void add(T obj) {
        Node<T> node = new Node<>();
        node.obj = obj;

        if (head == null) {
            head = node;
            tail = node;
            size = 1;
        } else {
            tail.next = node;
            tail = node;
            ++size;
        }
    }

    /**
     * 获取索引元素
     */
    public T get(int index) {
        if (size == 0) {
            return null;
        }

        T obj = null;
        if (index < size) {
            Node<T> currNode = head;
            for (int i = 0; i < index; i++) {
                currNode = currNode.next;
            }
            obj = currNode.obj;
        }
        return obj;
    }

    /**
     * 移除索引元素
     */
    public boolean remove(int index) {
        // 边界处理(空链表、索引无效)
        if (size == 0 || index >= size || index < 0) {
            return false;
        }

        // 特殊处理
        if (index == 0) {
            if (size == 1) {
                head = null;
                tail = null;
                return true;
            } else {
                head = head.next;
            }
        }

        // 查找索引元素
        Node<T> prevNode = null;
        Node<T> currNode = head;
        for (int i = 0; i < index; i++) {
            prevNode = currNode;
            currNode = currNode.next;
        }

        // 移除节点
        assert prevNode != null;
        prevNode.next = currNode.next;

        // 末尾处理
        if (index == --size) {
            tail = prevNode;
        }
        return true;
    }

    /**
     * 反转
     * 遍历一遍，缺点：反转过程中get(index)会出错
     */
    public void reverse() {
        if (size < 2) {
            return;
        }

        tail = head;

        Node<T> currNode = head;
        Node<T> nextNode = currNode.next;
        head.next = null;

        for (int i = 0; i < size - 1; i++) {
            currNode = nextNode;
            nextNode = nextNode.next;
            currNode.next = head;
            head = currNode;
        }
    }

    @Override
    public String toString() {
        return "SingleList{" +
                "head=" + head +
                ", tail=" + tail +
                ", size=" + size +
                '}';
    }

    /**
     * 节点
     */
    @Data
    public static class Node<T> {
        private T obj;
        private Node<T> next;
    }



    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        list.reverse();
        System.out.println(list);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 双向链表
    • 环链表（单或双向）

    正确写出链表代码六个技巧：

    1. 理解指针或引用的含义
    2. 警惕指针丢失和内存泄漏
    3. 利用哨兵简化实现难度
    4. 重点留意边界条件处理
    5. 举例画图，辅助思考
    6. 多写多练

    栈

    LIFO后进先出，一种操作受限的线性表数据结构
    种类

    • 顺序栈：用数组实现
    package com.zsl.datastructalgorithm.date20220626;

/**
 * @Author zsl
 * @Date 2022/6/26 10:33
 * @Email 249269610@qq.com
 */
public class Stack {

    // 数组元素
    private Integer[] elements;
    // 容量
    private final int capacity;
    // 当前栈存储元素个数
    private int size;

    public Stack(int capacity) {
        this.elements = new Integer[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    /**
     * 入栈
     */
    public boolean push(Integer element) {
        // 边界处理
        if (size == capacity) {
            return false;
        }

        elements[size++] = element;
        return true;
    }

    /**
     * 出栈
     */
    public Integer pop() {
        // 边界处理
        if (size == 0) {
            return null;
        }

        return elements[--size];
    }

    /**
     * 查看栈顶元素
     */
    public Integer peek() {
        // 边界处理
        if (size == 0) {
            return null;
        }

        return elements[size - 1];
    }

    public static void main(String[] args) {
        Stack stack = new Stack(10);
        for (int i = 0; i < 16; i++) {
            System.out.println(String.format("%02d:push number: %d, 结果:%s", i, i,  stack.push(i)));
        }

        for (int i = 0; i < 16; i++) {
            Integer pop = stack.pop();
            System.out.println(String.format("%02d:pop 结果:%d", i, pop));
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 链式栈：用链表实现

    队列

    FIFO先进先出，也是一种操作受限的线性表数据结构
    种类 --> 存储形式

    • 顺序队列（单、双、环）
    package com.zsl.datastructalgorithm.date20220626;

/**
 * 素组循环队列，存储容量为 capacity - 1；达到上限直接抛弃
 *
 * @author zsl
 * @date 2022/6/26 18:46
 * @email 249269610@qq.com
 */
public class ArrayQueue {

    // 元素数组
    private Integer[] elements;
    // 头
    private int head;
    // 尾
    private int tail;
    // 容量
    private final int capacity;

    public ArrayQueue(int capacity) {
        this.elements = new Integer[capacity];
        this.head = 0;
        this.tail = 0;
        this.capacity = capacity;
    }

    /**
     * 入队
     */
    public boolean enqueue(Integer element) {
        // 判断队列是否有空闲
        if (tail + 1 == head) return false;

        elements[tail++] = element;

        // 边界处理
        if (tail == capacity) tail = 0;
        return true;
    }

    /**
     * 出队
     */
    public Integer dequeue() {
        // 判断是否有元素
        if (tail == head) return null;

        Integer element = elements[head++];

        // 边界处理
        if (head == capacity) head = 0;
        return element;
    }


    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(10);
        for (int i = 0; i < 16; i++) {
            System.out.println(String.format("%02d:enqueue element=%02d, 结果 %s", i, i, arrayQueue.enqueue(i)));
            if (i == 7) {
                System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
            }

            if (i == 14) {
                System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
            }
        }

        for (int i = 0; i < 14; i++) {
            System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 链式队列（单、双、环）

    扩展

    • 阻塞队列：应用于生产者-消费者
    • 并发队列：保障线程安全（加锁）
  • 相关阅读:
    MQTT 基础--遗嘱和遗嘱：第 9 部分
    uni-app医院智能导诊系统源码
    BUUCTF WEB PICKLE STORE
    【LeetCode-中等题】347. 前 K 个高频元素
    每日两题 131分割回文串 784字母大小写全排列（子集模版）
    JavaScript中var，let，const 的区别
    函数题37习题10-7 十进制转换二进制《C语言程序设计（第4版）》题目集
    （Transfer Learning）迁移学习在IMDB上训练情感分析模型
    Java系列 | 如何讲自己的JAR包上传至阿里云maven私有仓库【云效制品仓库】
    GBase 8c V3.0.0数据类型——时间日期操作符
  • 原文地址：https://blog.csdn.net/qq_19152901/article/details/125473878