• 链表、栈、队列


    链表

    • 在内存空间中,数组和链表都是基本的数据结构,都是【表】,或者叫【线性表】。
    • 线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点,说人话,就是有头有尾一条线。

    在这里插入图片描述
    还不明白再来一张图
    在这里插入图片描述
    代码实现:
    写链表首先要封装一个保存数据和引用的节点,我们俗称node

    public class Node {
           // 数据
        private Integer data;
           // 该节点的下一个节点
        private Node next;
    
        public Integer getData() {
            return data;
        }
    
        public void setData(Integer data) {
            this.data = data;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    public class SuperLinked {
    
        // 链表的长度
        private int size;
        // 维护一个头节点
        private Node first;
        // 维护一个尾节点
        private Node last;
    
        // 无参构造器
        public SuperLinked(){
    
        }
    
        //添加元素至链表尾部
        public boolean add(Integer data){
            Node node = new Node(data,null);
            if (first == null){
                first = node;
            } else {
                last.setNext(node);
            }
            last = node;
            size++;
            return true;
        }
    
        //在指定下标添加元素
        public boolean add(int index,Integer data){
            Node node = getNode(index);
            Node newNode = new Node(data,null);
    
            if (node != null){
                newNode.setNext(node.getNext());
                node.setNext(newNode);
            } else {
                first = newNode;
                last = newNode;
            }
    
            size++;
            return true;
        }
    
        // 删除头元素
        public boolean remove(){
            if (size < 0){
                return false;
            }
    
            if (first != null ){
                first = first.getNext();
                size--;
            }
            return true;
        }
    
        // 删除指定元素
        public boolean remove(int index){
            if (size < 0){
                return false;
            }
            if(size == 1){
                first = null;
                last = null;
            } else {
                Node node = getNode(index-1);
                node.setNext(node.getNext().getNext());
            }
            size--;
            return true;
        }
    
        // 修改指定下标的元素
        public boolean set(int index,Integer data){
            // 找到第index个
            Node node = getNode(index);
            node.setData(data);
            return true;
        }
    
        // 获取指定下标的元素
        public Integer get(int index){
            return getNode(index).getData();
        }
    
        //查看当前有多少个数字
        public int size(){
            return size;
        }
    
        //添加元素
        private Node getNode(int index){
    
            // 边界判断
            if(index <= 0){
                index = 0;
            }
            if(index >= size-1){
                index = size-1;
            }
    
            // 找到第index个
            Node cursor = first;
            for (int i = 0; i < index; i++) {
                cursor = cursor.getNext();
            }
            return cursor;
        }
    
        public static void main(String[] args) {
            SuperLinked linked = new SuperLinked();
            linked.add(1);
            linked.add(2);
            linked.add(4);
            linked.add(6);
            linked.add(3);
            linked.add(2);
            linked.add(7);
            linked.add(6);
            linked.remove();
            linked.remove(2);
            linked.set(0,3);
            for (int i = 0; i < linked.size(); i++) {
                System.out.println(linked.get(i));
            }
        }
    }
    
    • 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

    封装一个栈和队列

    栈(Stack)和队列(Queue)是两种操作受限的线性表。

    这种受限表现在:栈的插入和删除操作只允许在表的尾端进行(在栈中成为“栈顶”),满足“FILO:First In Last Out”;队列只允许在表尾插入数据元素,在表头删除数据元素,满足“First In First Out”。

    栈与队列的相同点:

    • 都是线性结构。
    • 插入操作都是限定在表尾进行。
    • 都可以通过顺序结构和链式结构实现。、

    栈与队列的不同点:

    • 队列先进先出,栈先进后出。

    /**
     * 数组实现栈称之为静态栈
     */
    public class ArrayStack {
    
         // 栈大小
        private int maxStack;
    
         // 数组用来模拟栈
        private int[] stack;
    
        // 表示栈顶所在的位置,默认情况下如果没有数据时,使用-1
        private int top;
    
        public ArrayStack(int maxStack){
            this.maxStack = maxStack;
            stack = new int[maxStack];
        }
    
        /**
         * 1. 压栈
         * 2. 弹栈
         * 3.判断是否是空栈
         * 4. 当前栈中是否是满栈
         */
    
        // 判断是否已经满栈
        public boolean isFull(){
           return this.top == this.maxStack-1;
        }
    
        // 判断是否是空栈
        public boolean isEmpty(){
            return this.top == -1;
        }
    
    
        /**
         * 压栈
         */
        public void push(int val){
            // 是否已经满栈
            if (isFull()){
                throw new RuntimeException("栈已经满了");
            }
            top++;
            stack[top] = val;
        }
    
    
        /**
         * 弹栈
         */
        public int pop(){
            // 如果栈中时空
            if (isEmpty()){
                throw new RuntimeException("空栈,未找到数据");
            }
    
            int value = stack[top];
            top--;
            return value;
        }
    
    
        /**
         * 查看栈中所有元素
         */
        public void list(){
    
            //是否是空栈
           if (isEmpty()){
               throw new RuntimeException("空栈,未找到数据");
           }
           for (int i = 0;i<stack.length;i++){
               System.out.printf("stack[%d]=%d\n",i,stack[i]);
           }
    
        }
    
        /**
         * 获取栈中元素存在的个数
         */
        public int length(){
            return this.top+1;
        }
    
    }
    
    
    • 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

    需求:使用栈判断数据是否是回文数据

    public class TestApp {
        public static void main(String[] args) {
    
            /**
             * 回文数据
             * 回文: aba,   racecar 意思就是从左往右和从右往左是一样的数据称之为回文数据
             * 需求: 通过上面以数组模拟栈来判断一个字符串是否是一个回文数据
             *
             */
            delecation("hello");
            delecation("aba");
    
    
        }
    
        public static boolean delecation(String val){
    
            /**
             * 初始化栈对向、象
             */
            ArrayStack arrayStack = new ArrayStack(10);
    
            // 获取传递进来的字符串的长度
            int length = val.length();
    
            for (int i = 0; i <length ; i++) {
                arrayStack.push(val.charAt(i));
            }
    
    
            /**
             * 获取弹出来的数据
             */
            String newVal = "";
            int length1 = arrayStack.length();
            for (int i = 0; i <length1; i++) {
                // 如果不是一个空栈
                if (!arrayStack.isEmpty()){
                    char pop =(char) arrayStack.pop();
                    newVal = newVal+pop;
                }
            }
    
            if (val.equals(newVal)){
                return true;
            }
    
            return false;
    
        }
    }
    
    
    • 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

    队列

    public class Queue {
    
        private SuperLinked superLinked = new SuperLinked();
    
        // 出队的方法
        public Integer poll(){
            if(empty()){
                return null;
            }
            Integer integer = superLinked.get(0);
            superLinked.remove();
            return integer;
        }
        
        // 返回队首,不出队
        public Integer peek(){
            if(empty()){
                return null;
            }
            return superLinked.get(0);
        }
    
        // 入队的方法
        public void add(Integer item){
            superLinked.add(item);
        }
    
        // 判断这个队列是否为空
        public boolean empty(){
            return superLinked.size() == 0;
        }
    
        public static void main(String[] args) {
            Queue queue = new Queue();
            queue.add(1);
            queue.add(2);
            queue.add(3);
    
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
        }
    
    }
    
    • 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
  • 相关阅读:
    Qt5开发从入门到精通——第五篇一节( 文本编辑器 Easy Word 开发 V1.0 详解 )
    【SEC 学习】美化 Linux 终端
    es6 正则表达式
    【Python】运算符
    安卓APP源码和设计报告——体育馆预约系统
    AtomicInteger——Java中的多线程原子计数器
    【算法合集】学习算法第一天(链表篇)
    Flutter+SpringBoot实现ChatGPT流实输出
    【简单的自动曝光】python实现-附ChatGPT解析
    《搞定音频技术》
  • 原文地址:https://blog.csdn.net/qq_45243783/article/details/125487773