Java集合学习（一、栈和队列）

一、栈

1. 简介

栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。

2. 操作示例

（1）初始化

  Stack<Character> stack=new Stack<>();

（2）入栈

 stack.push('a');

（3）出栈

stack.pop();

（4）查看栈顶元素（不出）

stack.peek();

（5）查看栈内所有元素

System.out.println(stack);

3. 实例

import java.util.Stack;

public class Stacktest {
    public static void main(String[] args) {
        String str = "Hello World";
        Stack<Character> stack = new Stack<>();
//        将字符串的字符依次入栈
        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }
//        查看栈内所有元素
        System.out.println(stack);
//        依次打印栈中所有元素
        for(char te:stack){
            System.out.println(te);
        }
        String result = "";
        char temp = ' ';
//        将栈中"o"删除，其他字符存入result
        while (!stack.empty()) {
            temp = stack.pop();
            if (temp != 'o')
                result += temp;
        }

        System.out.println(result);
    }
}

二、队列

1. 简介

队列（Queue）是一种先进先出（LIFO：First In First Out）的数据结构。
它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：

• 把元素添加到队列末尾；
• 从队列头部取出元素。

常用方法：

2. 操作示例

（1）初始化

Queue<String> que=new LinkedList<>();
Queue<String> que1=new ArrayDeque<>();

（2）入队

  que.add("1");

（3）出队

  System.out.println("poll:"+ que.poll());

（4）查看队首元素（不出）

 System.out.println("peek:"+que.peek());

（5）查看队内所有元素

三种方法：直接查看；遍历法；出队法

//法1：直接查看
        System.out.println(que);
//法2：遍历法
        System.out.println("遍历法取元素");
        for(String s:que){
            System.out.println(s);
        }
//法3：出队法
        System.out.println("出队法取元素");
        while (!que.isEmpty()){
            System.out.println(que.poll());
        }

3. 实例

import java.util.LinkedList;
import java.util.Queue;

public class Queuetest {
    public static void main(String[] args) {
//        初始化
        Queue<String> que=new LinkedList<>();
//        添加元素至队尾
        que.add("1");
        que.add("2");
        que.add("3");
//        取队首元素看一眼，但不出队
        System.out.println("peek:"+que.peek());
//        出队
        System.out.println("poll:"+ que.poll());
//        查看队列内所有元素
//法1：直接查看
        System.out.println(que);
//法2：遍历法
        System.out.println("遍历法取元素");
        for(String s:que){
            System.out.println(s);
        }
//法3：出队法
        System.out.println("出队法取元素");
        while (!que.isEmpty()){
            System.out.println(que.poll());
        }
    }
}

三、栈的正确实现

1. 为什么不推荐使用Stack类

java官网文档推荐的栈数据结构实现接口是Deque：

 Deque<Integer> stack=new ArrayDeque<>();

Stack类的继承关系如下：这也暴露出Stack类最大的问题是继承了Vector类：

Vector是一个动态数组，继承了Vector类的同时会继承其所有公有方法，也就是说，一些在栈数据结构中的非法操作，也可以实现。比如：

Stack<Integer> st=new Stack<>();
        st.push(1);
        st.push(2);
        st.add(1,666);

上面的操作在Java中是正确的，但是对于数据结构栈来说，指定索引插入元素这个操作是非法的，破坏了这种数据结构的封装。
我们要知道，封装的意义是向用户屏蔽不需要的操作，否则用户会有意无意调用这些操作。因此Java中的Stack实现，一直被认为是非常糟糕的。
note： Vector
Vector是一个线程安全的动态数组，效率没有ArrayList高。

2. 问题出在哪里？

问题就出在Stack与Vector的关系上，他们不应该是继承关系，应该是组合关系。
继承与组合：
继承关系是is-a：
猫是一个动物，因此猫类可以继承动物类
组合关系是has-a：
汽车拥有一台发动机，因此车包含一个私有成员变量，是发动机类的对象。
下面思考栈和动态数组的关系：
栈是一个动态数组，这句话听起来没毛病，但是本质上栈不是一个动态数组，因为栈无法当做一个动态数组来使用看待。
所以一个更好的基于Vector的栈的实现，应该是这样的：

public class Stack<E>{
    private Vector<E> v=new Vector<E>();
    //实现栈的相关方法
}

3. Deque接口

（1）为什么要使用接口？

接口的最大意义之一，是为了实现更高层次的抽象：只定义了一个类应该满足哪些方法，而不对具体的实现方式做限制。
比如实现一个队列，我们可以这么写：

 Queue<Integer> q1=new LinkedList<>();
 Queue<Integer> q2=new ArrayDeque<>();

其中Queue就是一个接口，q1和q2的底层具体实现不同，一个是LinkedList，一个是ArrayDeque。但是从我们用户的角度来看，我们的q1和q2都是实现一个队列，可以执行队列的操作。
这样做就将队列这个概念和底层数据结构的具体实现解耦了：

• 底层开发人员可以随意维护LinkedList和ArrayDeque类，只要他们满足Queue的接口规定规范即可。
• 开发人员根据需求选择合适的数据结构来实现Queue；
• Queue的更上层使用者，不关心队列的实现细节，只要能调用队列的相关方法来满足上层业务需求即可。

这样做解决了继承中，子类把父类的所有方法都拿来用的问题。接口的设计相当于做了访问限制。LinkedList中有很多方法，但是当我们使用LinkedList实现Queue接口的时候，用户只能调用Queue中定义的方法。

（2）Deque接口

Deque是双端队列的意思，即在线性数据结构的两端，进行插入和删除操作。由于栈是在同一端进，同一端出，所以Deque接口完全满足栈的需求。

（3）使用Deque又引出的新问题

因为我们根据Java官方推荐的方法来声明这个Stack，虽然我们知道我们实现了一个栈，但是他实际上是一个deque，即我们对其可以进行双端插入删除操作。
这个基于Deque实现的栈中依然有我们不需要的方法，破坏了封装性，但是这已经是目前的最优解了，除非自己再做一层封装实现真正意义上的栈-限制只能从一端插入删除。
这是在网上找的具体实现：
http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/

4. 为什么选用动态数组而不是链表来实现栈

可发现Java官方文档推荐创建栈的方式使用了Deque接口，并在底层实现使用了ArrayDeque，也就是基于动态数组的实现。
动态数组是可以进行扩容操作的，在触发扩容的时候，时间复杂度$O(n)$，整体的时间复杂度为$O(1)$。基于链表的实现，不涉及到扩容问题，因此，每一次添加操作的时间复杂度都是$O(1)$。但是当数据量达到一定程度，链表的性能远远低于动态数组。因为对于链表来说，每次添加一个元素，都需要重新创建一个新的节点-Node对象，也就是进行一次new的内存操作，这是比较花费时间的。
做实验，对于两种方式实现的队列，进行1000万次入队操作，测试性能。

Queue<Integer> q1=new LinkedList<>();
Queue<Integer> q2=new ArrayDeque<>();
int n=10000000;
long start1=System.currentTimeMillis();
for(int i=0;i<n;i++){
    q1.add(i);
}
System.out.println(System.currentTimeMillis()-start1);
long start2=System.currentTimeMillis();
for(int i=0;i<n;i++){
    q2.add(i);
}
System.out.println(System.currentTimeMillis()-start2);

结果如下：

四、优先队列实现堆

1. 简介

优先队列PriorityQueue是一个基于优先级堆的无界优先级队列，默认按照自然顺序排序，也可以自定义排序方法。
方法摘要：

2. 操作示例

（1）初始化堆

小顶堆：

  PriorityQueue<Integer> minHeap=new PriorityQueue<>();

大顶堆：

 PriorityQueue<Integer> maxHeap=new PriorityQueue<>((a,b)->b-a);

（2）入队

minHeap.add(1);

（3）出队

minHeap.poll();

3. 实例

//        默认为小顶堆
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
//        改为大顶堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>((a,b)->b-a);
        maxHeap.add(1);
        maxHeap.add(3);
        maxHeap.add(2);
        System.out.println(maxHeap.poll()+" "+maxHeap.poll()+" "+maxHeap.poll());