SilverLining's Blog

链表、栈和队列

链表

链表是一种非连续的数据结构,常见的实现有单链表和双向链表。

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; this.next = next;
    }
}

class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;
    public DoubleNode(int data) {
        value = data;
    }
}

反转单链表

迭代法的基本思路:先用 next 指针记录下一个节点,然后调整当前 head 节点。然后用 pre 指针记录当前节点(这是下一个节点的 pre),然后 head 后移处理下一个。

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    while (head != null) {
        // 记住下一个位置
        next = head.next;
        // 当前位置 next 向前指
        head.next = pre;
        // pre 来到当前位置
        pre = head;
        // head 来到下一个
        head = next;
    }
    return pre;
}

反转双向链表

和反转双向链表的思路是一样的,只不过每一节点上多做一步 last 指针的调整操作。

public static DoubleNode reverseDoubleList(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        // 记录当前节点的下一个
        next = head.next;

        // 当前节点下一个指向前一个
        head.next = pre;
        // 当前节点前一个指向下一个
        head.last = next;
        // pre 指向当前节点
        pre = head;

        // head 节点处理完毕,进行下一个节点
        head = next;
    }
    return pre;
}

删除链表中的元素

对于删除的场景,先处理头结点,因为头结点可能需要删除,也可能不需要。先找到第一个不需要删除的节点,把它作为新的头结点。(对于 Java 来说,此前的节点缺少强引用将会被 GC,无需关注内存释放的问题)

然后向后遍历,同样的采用基于 “跳过” 的操作,将需要删除的前一个节点 next 指向其后一个节点即可。

public ListNode removeElements(ListNode head, int val) {
    while (head != null) {
        if (head.val != val) {
            break;
        }
        head = head.next;
    }
    // 此时 head 来到第一个不需要删除的节点
    ListNode pre = head;
    ListNode cur = head;
    while (cur != null) {
        // pre 留在上一个不需要删除的位置
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

栈和队列

栈和队列是一种逻辑上的数据结构,其底层可以分别通过双向链表有序数组来实现。

双向链表实现

首先,我们来实现一个双向链表:

class Node<T> {
    public T value;
    public Node<T> last;
    public Node<T> next;

    public Node(T data) {
        value = data;
    }
}

class DoubleEndQueue<T> {
    public Node<T> head;
    public Node<T> tail;

    public void addFromHead(T value) {
        Node<T> cur = new Node<>(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<>(value);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            tail.next = cur;
            cur.last = tail;
            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;
            head.last = null;
            cur.next = 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;
    }
}

然后分别实现栈和队列:

class MyLinkedStack<T> {
    private final DoubleEndQueue<T> queue;

    public MyLinkedStack() {
        queue = new DoubleEndQueue<T>();
    }

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

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

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

class MyLinkedQueue<T> {
    private final DoubleEndQueue<T> queue;

    public MyLinkedQueue() {
        queue = new DoubleEndQueue<T>();
    }

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

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

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

数组实现

我们先定义一个固定长度为 limit 的数组作为底层存储结构,用两个 index 分别记录 pushpop 元素的位置。

这里有个问题:数组分配的空间是连续的。因此当元素按顺序放满后,又有元素弹出,那么我们需要设计一个机制来循环使用/回收这些空余的空间,即循环数组 RingArray

FIFO 的队列的实现为例,假设初始化 pushIdx = 0; popIdx = 0,那么随着元素的放入和弹出,就会有 pushIdx 回头来追赶 popIdx 的场景,这样在判空和判满的时间上都比较麻烦。

解决方案是加一个 size 来记录当前数组中已有的元素。这样无论是 push 还是 pop 操作,只需关心 size 与 limit 的关系即可,不需要关注两个指针处在怎样的追赶状态。
class MyArrayQueue {
    private final int limit;
    private int[] arr;

    private int putIdx;
    private int getIdx;
    private int size;

    public MyArrayQueue(int limit) {
        if (limit < 0) {
            throw new IllegalArgumentException("limit must be positive integer");
        }
        this.limit = limit;
        this.arr = new int[limit];
        putIdx = 0;
        getIdx = 0;
        size = 0;
    }

    public void put(int value) {
        if (size == limit) {
            throw new UnsupportedOperationException("Queue is already full");
        }
        arr[putIdx] = value;
        size ++;
        putIdx = nextIndex(putIdx);
    }

    public int get() {
        if (size == 0) {
            throw new UnsupportedOperationException("Queue is empty");
        }
        int value = arr[getIdx];
        size --;
        getIdx = nextIndex(getIdx);
        return value;
    }

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

    public boolean isFull() {
        return size == limit;
    }

    private int nextIndex(int index) {
        return (index + 1) % limit;
    }
}

包含 min 函数的栈

LeetCode-30 使用 Stack 数据结构,设计一个能够得到栈中当前最小元素的 min 函数。在该栈中,minpushpop 的时间复杂度都为 O(1)

这题的第一思路,是用一个变量来保存栈中的最小元素,当新元素放入时,不断更新这个最小值。但是问题在于,当这个最小值的元素弹出的时候,如何知道此时当前栈中新的最小值(即弹出前栈中的次小值)呢?

所以一个最小值变量是不足以解决这个问题的,这个最小值与栈中的数据是有关联的。

因此我们可以建一个和数据栈相同大小的最小值栈,在压入数据的同时向最小值栈压入当前最小值:

class MinStackAtPush {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStackAtPush() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);

        // 压入较小值
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else if (x < minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        dataStack.pop();
        // 同时弹出最小值栈
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

这种做法是在压入数据时维护最小值栈,最小值栈和数据栈是等长的。

更强迫症一点的做法是,只在入栈的数小于等于最小值栈栈顶时,才同时将这个数压入最小值栈,把判断逻辑延后到弹出数据时去做,理想情况下可以节省一点最小值栈的空间开销。

class MinStackAtPop {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStackAtPop() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);

        // 只在压入值比最小值栈栈顶更小时入栈
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else if (x <= minStack.peek()) {
            // 注意这里是小于等于,相等的条件用于弹出数据
            minStack.push(x);
        }
    }

    public void pop() {
        int popValue = dataStack.pop();
        // 弹出的数等于最小值栈栈顶时,同时弹出最小值栈
        if (popValue == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

用两个栈实现队列

栈的特点是 FILO,而要实现 FIFO 的队列,容易想到将当前的栈 Stack 1 中的数全部弹出,再全部压入另一个栈 Stack 2,那么 Stack 2 重的顺序就倒正回来了。

需要注意的是,在 Stack 1 元素未全部弹出前,不能再将数倒入 Stack 2,否则会破坏 Stack 2 的弹出顺序,此时应当继续压入 Stack 1 。而当 Stack 2 为空时,必须把 Stack 1 的数全部压入 Stack 2,才能保证顺序的一致。

public class L232_TwoStackImplementQueue {

    /** Initialize your data structure here. */
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public L232_TwoStackImplementQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    private void dumpPushStackToPopStack() {
        // 只有 popStack 为空时
        if (popStack.empty()) {
            // 一次性倒光所有数
            while (! pushStack.empty()) {
                popStack.push(pushStack.pop());
            }
        }
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        pushStack.push(x);
        dumpPushStackToPopStack();
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (this.empty()) {
            throw new UnsupportedOperationException("Queue is empty");
        }
        dumpPushStackToPopStack();
        return popStack.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (this.empty()) {
            throw new UnsupportedOperationException("Queue is empty");
        }
        dumpPushStackToPopStack();
        return popStack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return pushStack.empty() && popStack.empty();
    }
}

用两个队列实现栈

用一个队列来保存数据,另一个辅助队列用来颠倒数的顺序。(一个队列也可实现,弹出再重复入一次队列)

public class L225_TwoQueueImplementStack {

    /** Initialize your data structure here. */
    public Queue<Integer> queue;
    public Queue<Integer> help;

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

    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        int value = queue.poll();

        Queue<Integer> tmp = queue;
        queue = help;
        help = tmp;

        return value;
    }

    /** Get the top element. */
    public int top() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        int value = queue.poll();
        // 保证 queue 被清空
        help.offer(value);

        Queue<Integer> tmp = queue;
        queue = help;
        help = tmp;

        return value;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}