链表
链表是一种非连续的数据结构，常见的实现有单链表和双向链表。
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 分别记录 push 和 pop 元素的位置。
这里有个问题：数组分配的空间是连续的。因此当元素按顺序放满后，又有元素弹出，那么我们需要设计一个机制来循环使用/回收这些空余的空间，即循环数组 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函数。在该栈中，min，push及pop的时间复杂度都为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();
}
}