对象将数据和操作打包在一起 ,类描述了这一切
用构造器创建(实例化)对象
类和类之间的关系
关联(组合、聚集)
泛化
Comparable接口
Comparator接口
Cloneable接口
Serializable接口
public class Teacher {
private String name;
private int ability;
private Student[] students;
}public class Student {
protected String name;
public int getAge() {
return age;
}
protected int age;
protected int ability;
private Teacher teacher;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public void study() {
ability++;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
", ability=" + ability +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return name.equals(student.name);
}
@Override
public int hashCode() {
return name.hashCode();
}
public static void main(String[] args) {
Student stu1 = new Student("唐僧", 200);
Student stu3 = new Student("唐僧", 200);
Student stu2 = new Student("悟空", 600);
stu1.study();
stu1.study();
stu2.study();
System.out.println(stu1.toString());
System.out.println(stu2.toString());
System.out.println(stu1.equals(stu3));
}
}public class CleverStudent extends Student {
public CleverStudent(String name, int age) {
super(name, age);
}
@Override
public void study() {
// super.study();
// super.study();
ability += 2;
}
public void study(int s) {
ability += s;
}
}数据元素( data element )
数据对象( data object )
集合:元素罗列在一起
线性结构:元素前后相继(一一对应)
树形结构:元素存在一对多的关系
图结构或网状结构:元素之间存在多对多关系
顺序存储:地址连续，用数组
链式存储:地址不连续，用指针(引用，面向对象)
为了某种特殊需求，专门设计的数据存储方式
定义列表接口
用数组实现列表-MyArrayList
实现链表(单链表、双链表)
迭代器
泛型
import java.util.*;
public class ListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list = new LinkedList<>();
list.add("adnda");
list.add("xyz");
list.add("def");
list.remove("");
// ......
Collections.sort(list);//可以直接排序，api已经定义字符串比较
List<Student> list1 = new ArrayList<>();
list1.add(new Student("zhangsan", 10));
list1.add(new Student("lsii", 20));
list1.add(new Student("wangwu", 40));
list1.add(new Student("wangsu", 30));
Collections.sort(list1, (o1, o2) -> {//这里可以在Student中实现Comparable接口，后者给Collections第二个参数传比较器
return o1.getAge() - o2.getAge();
});
Iterator<Student> iterator = list1.iterator();//迭代器.hasNext()和.next()
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}package org.lanqiao.algo.elementary.datastructure;
/**
* 简单单向链表的节点
*/
public class LinkedNode {
public int value;
public LinkedNode next;
public LinkedNode(int value) {
this.value = value;
}
}package org.lanqiao.algo.elementary._03sort;
import org.assertj.core.api.Assertions;
import org.lanqiao.algo.elementary.datastructure.LinkedNode;
import org.lanqiao.algo.util.Util;
import java.util.Arrays;
/**
* 桶排序<br />
* 思路：见http://www.cs.usfca.edu/~galles/visualization/BucketSort.html<br />
* 工作的原理是将数组分到有限数量的桶子里。<br />
* 每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。<br />
* 桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。<br />
* 但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。<br />
*
* 时间复杂度： O(N+C)，其中C=N*(logN-logM)<br />
* 空间复杂度：N+M，M为桶的个数<br />
* 非原址排序<br />
* 稳定性：稳定<br />
*
* 桶排序假设数据会均匀入桶，在这个前提下，桶排序很快！
*/
public class _9BucketSort {
// 根据桶的个数来确定hash函数，这份代码适合桶的个数等于数组长度
private static int hash(int element, int max, int length) {
return (element * length) / (max + 1);
}
public static void main(String[] args) {
int[] arr = Util.getRandomArr( 10, 1, 100 );
System.out.println( "begin..." + Arrays.toString( arr ) );
new _9BucketSort().sort( arr );
System.out.println( "final..." + Arrays.toString( arr ) );
Assertions.assertThat( Util.checkOrdered( arr, true ) ).isTrue();
}
private void sort(int[] arr) {
int length = arr.length;
LinkedNode[] bucket = new LinkedNode[length]; // 桶的个数=length
int max = Util.maxOf(arr);//求max
// 入桶
for (int i = 0; i < length; i++) {
int value = arr[i];//扫描每个元素
int hash = hash( arr[i], max, length ); // 桶的下标
if (bucket[hash] == null) {
bucket[hash] = new LinkedNode( value ); // 初始化链表表头
} else {
insertInto( value, bucket[hash], bucket, hash ); // 插入链表
}
}
int k = 0; // 记录数组下标
//出桶，回填arr
for (LinkedNode node : bucket) {
if (node != null) {
while (node != null) {
arr[k++] = node.value;
node = node.next;
}
}
}
}
private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
LinkedNode newNode = new LinkedNode( value );
//小于头节点，放在头上
if (value <= head.value) {
newNode.next = head;
// 替换头节点
bucket[hash] = newNode;
return;
}
/*往后找第一个比当前值大的节点，放在这个节点的前面*/
LinkedNode p = head;
LinkedNode pre = p;
while (p != null && value > p.value) {
pre = p;
p = p.next;
}
if (p == null) { // 跑到末尾了
pre.next = newNode;
} else { // 插入pre和p之间
pre.next = newNode;
newNode.next = p;
}
}
}编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]提示：
public static ListNode removeDuplicateNodes(ListNode head) {
ListNode p=head;
ListNode pre=null;
Set<Integer> set=new HashSet<Integer>();
while(p!=null){
if(set.contains(p.val)){//如果存在就删除，前面的next指向后面的
pre.next=p.next;//此时pre不动
}else {
pre=p;//pre变为当前
set.add(p.val);
}
p=p.next;//两种情况都要p指向后面，
}
return head;
}实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4说明：
给定的 k 保证是有效的。
public static int kthToLast(ListNode head, int k) {
//由于题目中k保证有效，如果不保证开头要设置
ListNode pre=head;
ListNode now=head;
int count=1;
while(count<k){//now指针不断后移动,移动k-1次
now=now.next;
count++;
}
//此时pre指向第一个元素，now指向第k个元素
while(now.next!=null){//如果now.next为null,倒数k个元素就为第一个元素
pre=pre.next;//否则两者共同往后移动
now=now.next;
}
return pre.val;
}实现一种算法，删除单向链表中间的某个节点（除了第一个和最后一个节点，不一定是中间节点），假定你只能访问该节点。
示例：
输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->fpublic static void deleteNode(ListNode node) {
node.val=node.next.val;//后面元素的值覆盖当前元素,后面的元素成为当前元素
node.next=node.next.next;//当前元素的next指向后面的后面元素
}编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针ListNode node，请返回重新排列后的链表的头指针。
注意：分割以后保持原来的数据顺序不变。
示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->2->1->5->8->5->10/* 将链表头节点和其节点值传递到分割链表 */
public static ListNode partition(ListNode node, int x) {
ListNode beforeStart = null;//前半部分
ListNode beforeEnd = null;//前半部分最后一个元素
ListNode afterStart = null;//后半部分
ListNode afterEnd = null;//后半部分最后一个元素
/* 分割链表 */
while (node != null) {
ListNode next = node.next;//先保存当前节点的next
node.next = null;
if (node.val < x) {
/* 将节点插入到before 链表尾部 */
if(beforeStart == null){//没有节点
beforeStart = node;//前半部分头为node
beforeEnd = beforeStart;//前半部分尾为node
}else{
beforeEnd.next = node;
beforeEnd = node;
}
}else{
/* 将节点插入到after 链表尾部 */
if(afterStart == null) {
afterStart = node;
afterEnd = afterStart;
}else{
afterEnd.next = node;
afterEnd = node;
}
}
node = next;
}
if (beforeStart == null) {
return afterStart;
}
/* 合并after 链表和before 链表 */
beforeEnd.next = afterStart;
return beforeStart;
}给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912进阶：假设这些数位是正向存放的，请再做一遍。
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912public static ListNode addTwoNumbers(ListNode l1, ListNode l2,int value) {
if(l1==null&&l2==null&&value==0){
return null;
}
int sum=value;
if(l1!=null){//不为空时才加入
sum+=l1.val;
}
if(l2!=null){//不为空时才加入
sum+=l2.val;
}
ListNode list=new ListNode(sum%10);
list.next=addTwoNumbers(l1==null?null:l1.next,l2==null?null:l2.next,sum/10);
//这里需要判断是否l1和l2是否为空
return list;
}
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwoNumbers(l1,l2,0);
}给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。示例：
输入：A -> B -> C -> D -> E -> C（C 节点出现了两次）
输出：C
如果有环路返回环路节点，如果没有环路返回null
第1部分：检测链表是否存在环路
检测链表是否存在环路，有一种简单的做法叫FastRunner/SlowRunner法。FastRunner一次移动两步，而SlowRunner一次移动一步。这就好比两辆赛车以不同的速度绕着同一条赛道前进，最终必然会碰到一起。
细心的读者可能会问：FastRunner会不会刚好“越过”SlowRunner，而不发生碰撞呢？绝无可能。假设FastRunner真的越过了SlowRunner，且SlowRunner处于位置i，FastRunner处于位置i+1。那么，在前一步，SlowRunner就处于位置i-1，FastRunner处于位置((i+1)-2)或i-1，也就是说，两者碰在一起了。
FastPointer的移动速度是SlowPointer的两倍。当SlowPointer走了k个节点进入环路时，FastPointer已进入链表环路k个节点，也就是说FastPointer和SlowPointer相距LOOP_SIZE-k个节点。
接下来，若SlowPointer每走一个节点，FastPointer就走两个节点，每走一次，两者的距离就会更近一个节点。因此，SlowPointer走LOOP_SIZE-k步，FastPointer走2*(LOOP_SIZE-k)后，它们就会碰在一起。这时两者距离环路起始处有k个节点。
链表首部与环路起始处也相距k个节点。因此，若其中一个指针保持不变，另一个指针指向链表首部，则两个指针就会在环路起始处相会。
根据第1、2、3部分，就能直接导出下面的算法。
(1)创建两个指针：FastPointer和SlowPointer。
(2)SlowPointer每走一步，FastPointer就走两步。
(3)两者碰在一起时，将SlowPointer指向LinkedListHead，FastPointer则保持不变。
(4)以相同速度移动SlowPointer和FastPointer，一次一步，然后返回新的碰撞处。
public static ListNode detectCycle(ListNode head) {
ListNode p=head;
HashSet set=new HashSet();
while(true){
if(set.contains(p)||p==null){//如果head为null，p刚开始就为null，直接返回null
//或者p已经在集合中
return p;
}else{
set.add(p);
if(p.next==null){//p已经是最后一个了，直接返回null
return null;
}
p=p.next;
}
}
}ListNode detectCycle2(ListNode head) {
ListNode slow = head;
ListNode fast = head;
/* 找到相汇处。LOOP_SIZE - k 步后会进入链表 */
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 碰在一起
break;
}
}
/* 错误检查——若无相汇处，则无环路 */
if (fast == null || fast.next == null) {
return null;
}
/* 将慢的移动至头节点。两者均距离起始处k 步。
* 若两者以相同速度移动，则必然在环路起始处相遇 */
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
/* 两者均指向环路起始处 */
return fast;
}编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2
输出： false 示例 2：
输入： 1->2->2->1
输出： true 解法1：反转并比较
第一种解法是反转整个链表，然后比较反转链表和原始链表。若两者相同，则该链表为回文。
注意，在比较原始链表和反转链表时，其实只需比较链表的前半部分。若原始链表和反转链表的前半部分相同，那么，两者的后半部分肯定相同。
public static ListNode reverse(ListNode node){
ListNode head=null;//保存投的引用
while(node!=null){
ListNode n=new ListNode(node.val);//创建新的头
//往前插入
n.next=head;//由于依次往前插入，新的头的next为原来的头head
head=n;//n变为新的头
node=node.next;//指向下一个元素
}
return head;//如果本来就为null，head也为null
}
public static boolean isEqual(ListNode l1,ListNode l2){
while(l1!=null&&l2!=null){
if(l1.val!=l2.val){
return false;
}
l1=l1.next;//下一个为null时候，循环判断会结束
l2=l2.next;
}
return l1==null&&l2==null;//如果一开始两个都为空，返回true，否则false
}
public static boolean isPalindrome(ListNode head) {
ListNode t=reverse(head);
return isEqual(t,head);
}解法2：迭代法
要想检查链表的前半部分是否为后半部分反转而成，该怎么做呢？只需将链表前半部分反转，可以利用栈来实现。
需要将前半部分节点入栈。根据链表长度已知与否，入栈有两种方式。
若链表长度已知，可以用标准for 循环迭代访问前半部分节点，将每个节点入栈。当然，要小心处理链表长度为奇数的情况。
若链表长度未知，可以利用本章开头描述的快慢runner 方法迭代访问链表。在迭代循环的每一步，将慢速runner 的数据入栈。在快速runner 抵达链表尾部时，慢速runner 刚好位于链表中间位置。至此，栈里就存放了链表前半部分的所有节点，不过顺序是相反的。接下来，只需迭代访问链表余下节点。每次迭代时，比较当前节点和栈顶元素，若完成迭代时比较结果完全相同，则该链表是回文序列。
public static boolean isPalindrome2(ListNode head) {
ListNode fast=head;
ListNode slow=head;
Stack<Integer> stack=new Stack<Integer>();
while(fast!=null&&fast.next!=null){
stack.push(slow.val);
slow=slow.next;
fast=fast.next.next;
}
//若个数为奇数，fast在最后一个元素。slow在最中间。例如1,2,3移动一次后
//若个数为偶数，fast为null,slow在中间偏右一个 ，例如1,2,3,4移动两次后
if(fast!=null){
slow=slow.next;
}
while(slow!=null){
if(slow.val!=stack.pop()){
return false;
}
slow=slow.next;
}
return true;
}栈( stack) 又称堆栈,它是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。
表中进行插入、删除操作的一端称为栈顶( top ) , 栈顶保存的元素称为栈顶元素。相对的,表的另一-端称为栈底 ( bottom )。
当栈中没有数据元素时称为空栈;向一一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。
由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈，所以又把堆栈称为后进先出表( Last In First Out ,简称LIFO )。
队列( queue) , 它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。 在队列中把插入数据元素的一端称为队尾,删除数据元素的一端称为队首
向队尾插入元素称为进队或入队,新元素入队后成为新的队尾元素;从队列中删除元素称为离队或出队,元素出队后,其后续元素成为新的队首元素
由于队列的插入和删除操作分别在队尾和队首进行,每个元素必然按照进入的次序离队,也就是说先进队的元素必然先离队,所以称队列为先进先出表( First In First Out,简称FIFO )。队列结构与日常生活中排队等候服务的模型是一致的,最早进入队列的人,最早得到服务并从队首离开;最后到来的人只能排在队列的最后,最后得到服务并最后离开
三合一。描述如何只用一个数组来实现三个栈
和许多问题一样，这个问题的解法基本上取决于你要对栈支持到什么程度。若每个栈分配的空间大小固定，就能满足需要，那么照做便是。不过，这么做的话，有可能其中一个栈的空间不够用了，其他的栈却几乎是空的。
另一种做法是弹性处理栈的空间分配，但这么一来，这个问题的复杂度又会大大增加。
请设计一个栈，除了pop 与push 函数，还支持min函数，其可返回栈元素中的最小值。执行push、pop 和min 操作的时间复杂度必须为O (1)。
push(5); // 栈为{5}，最小值为5
push(6); // 栈为{6, 5}，最小值为5
push(3); // 栈为{3, 6, 5}，最小值为3
push(7); // 栈为{7, 3, 6, 5}，最小值为3
pop(); // 弹出7，栈为{3, 6, 5}，最小值为3
pop(); // 弹出3，栈为{6, 5}，最小值为5
注意观察，当栈回到之前的状态（{6, 5}）时，最小值也回到之前的状态（5），这就导出了我们的第二种解法。
只要记下每种状态的最小值，获取最小值就是小菜一碟。实现方式很简单，每个节点记录当前最小值即可。这么一来，要找到min，直接查看栈顶元素就能得到最小值。当一个元素入栈时，该元素会记下当前最小值，将min 记录在自身数据结构的min 成员中。
static class MinStack {
Stack<Integer> stack;
int minV=Integer.MAX_VALUE;
Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
stack=new Stack<Integer>();
min=new Stack<Integer>();//当当前最小值改变时，记录最小值
}
public void push(int x) {
if(x<=minV||stack.empty()){//若压入的元素小于等于最小元素，压入min，或者为空时
min.push(x);
minV=x;
}
stack.push(x);
}
public void pop() {
if(stack.peek()==minV){//弹出最小元素可能改变最小值
min.pop();
if(min.empty()){
minV=Integer.MAX_VALUE;
}else{
minV=min.peek();//重新设置最小元素
}
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.
示例1:
输入：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
输出：
[null, null, null, 2, 1, -1]示例2:
输入：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, 3]class StackOfPlates {
private List<Stack<Integer>> stackList;
private int cap;//初始状态含有栈的数量
public StackOfPlates(int cap) {
stackList = new ArrayList<Stack<Integer>>();
this.cap = cap;
}
public void push(int val) {
if (cap <= 0) {
return;
}
if (stackList.isEmpty() || stackList.get(stackList.size() - 1).size() == cap) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(val);
stackList.add(stack);
return;
}
stackList.get(stackList.size() - 1).push(val);
}
public int pop() {
return popAt(stackList.size() - 1);
}
public int popAt(int index) {
if (index < 0 || index >= stackList.size()) {
return -1;
}
Stack<Integer> stack = stackList.get(index);//传来是引用
if (stack.isEmpty()) {
return -1;
}
int res = stack.pop();
if (stack.isEmpty()) {
stackList.remove(index);
}
return res;
}
}实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false说明：
push to top, peek/pop from top, size 和 is empty 操作是合法的。class MyQueue {
private Stack<Integer> numStack;
private Stack<Integer> helpStack;
public MyQueue() {
numStack = new Stack<Integer>();
helpStack = new Stack<Integer>();
}
public void push(int x) {
numStack.push(x);
}
public void move(){//numStack中的元素全部取出压入到helpStack中
while (!numStack.isEmpty()) {
helpStack.push(numStack.pop());
}
}
public int pop() {
if(helpStack.isEmpty()){//若helpStack为空
move();
}
return helpStack.pop();
}
public int peek() {
if(helpStack.isEmpty()){
move();
}
return helpStack.peek();
}
public boolean empty() {
return helpStack.isEmpty() && numStack.isEmpty();
}
}栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1:
输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]示例2:
输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]说明:
static class SortedStack {
Stack<Integer> stack;
Stack<Integer> help;
public SortedStack() {
stack=new Stack<Integer>();
help=new Stack<Integer>();
}
public void push(int val) {
if(stack.empty()||val<=stack.peek()){//为空或者插入元素比底下小
stack.push(val);
}else{
while (!stack.empty()&&val>stack.peek()){//注意不要忘记stack不为空的时候区元素
help.push(stack.pop());
}
stack.push(val);
while(!help.empty()){
stack.push(help.pop());
}
}
}
public void pop() {
if(!stack.empty()) {//注意不为空时弹出
stack.pop();
}
}
public int peek() {
if(!stack.empty()) {//注意不为空时
return stack.peek();
}else {
return -1;
}
}
public boolean isEmpty() {
return stack.isEmpty();
}
}动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1:
输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]示例2:
输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：
[null,null,null,null,[2,1],[0,0],[1,0]]说明:
按猫狗两个类，分成两个LinkedList
对于dequeueAny，按题意，序号是给定的，序号越小，进入收容所的时间越长，越应该出队
catId == dogId(因为如果空返回int最大值)，这时返回{-1, -1}class AnimalShelf {
private List<LinkedList<int[]>> data;
private int[] initAnimal = {-1, -1};
public AnimalShelf() {
data = new ArrayList<>();
data.add(new LinkedList<>());
data.add(new LinkedList<>());
}
public void enqueue(int[] animal) {
data.get(animal[1]).addLast(animal);
}
public int[] dequeueAny() {
int catId = data.get(0).isEmpty()? Integer.MAX_VALUE : data.get(0).peekFirst()[0];
int dogId = data.get(1).isEmpty()? Integer.MAX_VALUE : data.get(1).peekFirst()[0];
if(catId < dogId){
return data.get(0).pollFirst();
}else if(dogId < catId){
return data.get(1).pollFirst();
}else{
return initAnimal;
}
}
public int[] dequeueDog() {
if(data.get(1).isEmpty()) return initAnimal;
return data.get(1).pollFirst();
}
public int[] dequeueCat() {
if(data.get(0).isEmpty()) return initAnimal;
return data.get(0).pollFirst();
}
}原文：https://www.cnblogs.com/cxynb/p/12540538.html