链表结构、栈、队列 - 《数据结构与算法(基础)》

单向链表的结构

单链表反转
设置pre前节点（反转最终指向）
记录下一个节点的值（当前.next）
原下一个节点指向前一个节点
前一个节点pre向后滑动指向当前节点（head）；为之后下一个节点指向前一个节点准备
下一个节点成为头节点（head 滑倒下一个节点）

双向链表反转
next指针指前一个 last指针指后一个

一个单链表给定头节点一个额外的输入参数 num= 3 将链表中所有值为 3的删掉

public static Node removeValue(Node head, int num) {
        // head来到第一个不需要删的位置
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }
        // 1 ) head == null
        // 2 ) head != null
        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == num) {
                           //这个过程是指针重连节点(跳过要删的节点)
                           //cur可以理解为引导节点(探索是否要删)
                           //连到了cur命中了pre最近的不等于num的位置
                pre.next = cur.next;
            } else {
                           //pre相当于上一个不等于num的位置
                pre = cur;
            }
                   //相当于head.next 之后 cur值才变
                   //并且cur相当于是head的下一个(与头节点建立了联系)
            cur = cur.next;
        }
        return head;
    }

**Java 会产生内存泄露
因为变量的生命周期
JVM释放空间现在正在生存的变量指向某一个正在使用的内存 JVM是不会释放的
找不到活着引用的空间 JVM会释放掉

单向链表中虽然只记录了 head节点但后面的节点都不会被释放
因为后面的节点都会被一个生存着的 head节点引用
没有被引用的节点 JVM会自动释放掉

栈

双向链表的节点类型

链表实现队列
初始化链表结构

public static class DoubleEndsQueue<T> {
        public Node<T> head;
        public Node<T> tail;

头部加入节点

public void addFromHead(T value) {
            Node<T> cur = new Node<T>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                            //当前节点的下一个节点指向原来的头
                cur.next = head;
                            //头的前指针指向当前节点
                head.last = cur;
                           //当前节点做头
                head = cur;
            }
        }

尾部加入节点（原理同头部）

public void addFromBottom(T value) {
            Node<T> cur = new Node<T>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }

头部弹出

public T popFromHead() {
            if (head == null) {
                return null;
            }
            Node<T> cur = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                cur.next = null;
                head.last = null;
            }
            return cur.value;
        }

尾部弹出

public T popFromBottom() {
            if (head == null) {
                return null;
            }
            Node<T> cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.value;
        }

验证是否为空只要判断头是否为空

public boolean isEmpty() {
            return head == null;
        }

栈结构利用队列只头部加入头部弹出

public static class MyStack<T> {
        private DoubleEndsQueue<T> queue;

        public MyStack() {
            queue = new DoubleEndsQueue<T>();
        }

        public void push(T value) {
            queue.addFromHead(value);
        }

        public T pop() {
            return queue.popFromHead();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }

    }

队列的实现（头部进尾部出）

public static class MyQueue<T> {
        private DoubleEndsQueue<T> queue;

        public MyQueue() {
            queue = new DoubleEndsQueue<T>();
        }

        public void push(T value) {
            queue.addFromHead(value);
        }

        public T poll() {
            return queue.popFromBottom();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }

    }

队列和栈都属对双链表的调整
时间复杂度都是 O(1)
因为都是对 head 和 tail 的操作部牵扯到遍历

数组实现栈和队列
一般都是实现固定大小的栈或队列
给定一个总大小（限定结构最多能存在多少个数）
可以接受一次接收最大容量值但超出就报错（动态的变化要一直正确）

数组实现队列
维护两个指针
一个弹出指针(索引) 一个放入指针(索引)
一个已装入数量变量 size 一个固定不变的限制 limit
整个过程
相当于两个索引指针循环整个数组没有固定的头和尾头和尾都由指针来维护（环形数组）

public class Code04_RingArray {

    public static class MyQueue {
        private int[] arr;
        private int pushi;// end
        private int polli;// begin
        private int size;
        private final int limit;

        public MyQueue(int limit) {
            arr = new int[limit];
            pushi = 0;
            polli = 0;
            size = 0;
            this.limit = limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("队列满了，不能再加了");
            }
            size++;
            arr[pushi] = value;
            pushi = nextIndex(pushi);
        }

        public int pop() {
            if (size == 0) {
                throw new RuntimeException("队列空了，不能再拿了");
            }
            size--;
            int ans = arr[polli];
            polli = nextIndex(polli);
            return ans;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        // 如果现在的下标是i，返回下一个位置
        private int nextIndex(int i) {
            return i < limit - 1 ? i + 1 : 0;
        }
    }
}

过程图解

准备两个栈一个正常的data栈一个最小min栈
第一个数 data栈和 min栈都加
第二个数 data栈正常加
min栈：当前的数和min栈的栈顶（最后压栈的数）相比谁小加谁（存在重复加）
弹出的时候同步弹出 min栈弹出不反回
获取最小值任何时候弹出min栈栈顶就是最小值

public static class MyStack2 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack2() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum < this.getmin()) {
                this.stackMin.push(newNum);
            } else {
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

第二种思路省一点空间费一点时间
思路图解

data栈正常压入 min栈第一个正常压入
之后的数据 data栈正常压入 min栈压入的时候发现当前数比最小栈的栈顶大不压入
只有当前数小于等于 min栈栈顶的时候才压入
弹出的时候 data栈正常弹出 min栈弹出需要和data栈弹出数据比较只有相等的时候才弹出

用队列结构实现栈
图解

两个队列一个data队列一个help辅助队列
data队列数据正常放入
弹出的时候将1234 导入help队列中 data对列只保留最后一个数据返回
下次弹出两个队列功能交换 help保留最后一个数据返回之前的数据导入data库

public static class TwoQueueStack<T> {
        public Queue<T> queue;
        public Queue<T> help;

        public TwoQueueStack() {
            queue = new LinkedList<>();
            help = new LinkedList<>();
        }

        public void push(T value) {
            queue.offer(value);
        }

        public T poll() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }

        public T peek() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            help.offer(ans);
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }

    }

用栈结构实现队列
过程图解

两个栈一个push栈一个pop栈
push栈正常放数据取数据的时候正常弹出放入pop栈
放入pop栈前提条件
1）导入前 pop栈为空 2）push栈要一次性全部导入pop栈

public static class TwoStacksQueue {
        public Stack<Integer> stackPush;
        public Stack<Integer> stackPop;

        public TwoStacksQueue() {
            stackPush = new Stack<Integer>();
            stackPop = new Stack<Integer>();
        }

        // push栈向pop栈倒入数据
        private void pushToPop() {
            if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
        }

        public void add(int pushInt) {
            stackPush.push(pushInt);
            pushToPop();
        }

        public int poll() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            pushToPop();
            return stackPop.pop();
        }

        public int peek() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            pushToPop();
            return stackPop.peek();
        }
    }