集合介绍：

可以看到集合类的基本接口是Collection接口，而Collection接口继承了ITerable接口,这个接口内部只有一个方法public abstract Iterator iterator()，而这个迭代器对象用于依次访问集合中的元素

接下来让我跟你们介绍一下迭代器Iterator：

1.hasnext()方法：集合中有元素的时候返回true，否则返回false；

2.next()方法：首先迭代器指向第一个元素的前面的空白部分，调用next后迭代器越过下一个元素，并且返回这个元素的引用；

3.remove()方法：删除上次next返回的元素，他们互相依赖，所以next（）方法应用在remove（）方法的前面；

接下来介绍Collection集合

Collection

所包含的方法	说明
boolean add(E e)	将元素 e 放入集合中
void clear()	删除集合中的所有元素
boolean iSEMpty()	判断集合是否没有任何元素，俗称空集合
boolean remove(Object e)	如果元素 e 出现在集合中，删除其中一个
int size()	返回集合中的元素个数
Object[] toArray()	返回一个装有所有集合中元素的数组

Collection作为基本接口，其中的方法能被所实现了的子类所使用

List集合是线性表，区别于Set，Set不能出现重复的元素

实现List接口的类：

1.Stack

方法	说明
E push(E item)	入栈
E pop()	出栈
E PEek()	返回栈顶元素
boolean empty()	判断栈是否为空

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则

实现Stack：

import java.util.Arrays;
public class MyStack<T> {
    PRivate T[] elem;//数组
    private int top;//栈顶指针

    public MyStack() {
        this.elem = (T[])new Object[10];
    }

    public void push(T item) {
        //1、判断当前栈是否是满
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.top++] = item;
    }

    public boolean isFull(){
        return this.elem.length == this.top;
    }

    public T pop() {
        if(empty()) {
            throw new UnsupportedoperationException("栈为空！");
        }
        T ret = this.elem[this.top-1];
        this.top--;
        return ret;
    }
    public T peek() {
        if(empty()) {
            throw new UnsupportedOperationException("栈为空！");
        }
        return this.elem[this.top-1];
    }
    public boolean empty(){
        return this.top == 0;
    }
}
 public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.peek());//3
        System.out.println(myStack.pop());//3
        System.out.println(myStack.pop());//2
        System.out.println(myStack.pop());//1
        System.out.println(myStack.empty());//true
}

动画演示：

2.Queue

方法	说明
void offer()	向队尾插入一个元素
int poll()	删除队头元素
int peek(）	获取队头元素
boolean isEmpty()	判断队列是否为空

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点

进行插入操作的一端称为队尾

进行删除操作的一端称为队头

实现：

class Node {
    private int val;
    private Node next;
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    private Node First;
    private Node last;
    //入队
    public void offer(int val) {
        //判断是不是第一次插入
        Node node = new Node(val);
        if(this.first == null) {
            this.first = node;
            this.last = node;
        }else {
            this.last.setNext(node);//last.next = node;
            this.last = node;
        }
    }
    //出队
    public int poll() {
        //判断是否为空的
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        //this.first = this.first.next;
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;
    }
    //得到队头元素
    public int peek() {
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        return this.first.getVal();
    }
    //队列是否为空
    public boolean isEmpty() {
        return this.first == null;
    }
public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);

        System.out.println(myQueue.peek());//1
        System.out.println(myQueue.poll());//1
        System.out.println(myQueue.poll());//2
        System.out.println(myQueue.poll());//3
		while(myQueue!=null){
			System.out.println(myQueue.poll());
		}
        System.out.println(myQueue.isEmpty());//true
    }
}

循环队列

循环队列由front队头指针和rear队尾指针分别来删除元素和@R_777_2021@

循环队列的特点： 1.在rear等于front的时候队列空 2.rear+1==front的时候队满 3.大小为size的队列实际用到的只有size-1个空间

循环队列的一个好处是我们可以利用这个队列之前用过的空间

代码实现：

class MyCircularQueue {
    public int front;
    public int rear;
    public int length;
    public int []elem;
    public MyCircularQueue(int k) {
        elem=new int[k+1];
        rear=0;
        front=rear;
        length=k+1;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear]=value;
        rear=(rear+1)%length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front=(front+1)%length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return elem[((rear-1)+length)%length];
    }
    
    
    public boolean isEmpty() {
        if(rear==front)
        return true;
        else{
            return false;
        }
    }
    
    public boolean isFull() {
        if((rear+1)%length==front){
          return true;  
        }else{
            return false;
        }
    }
}

3.ArrayList

底层是数组： 缺点： ①数组长度固定,超过数组大小需要扩容并且元素拷贝，返回一个新的数组，效率低下

②插入(删除)元素慢：往数组的中插入(删除)一个元素，要把数组中那个新增元素后面的元素往后面（前面）挪动一位，消耗时间多，效率低

优点： ①随机访问，查找修改快，@R_28_1304@为O(1)

主要方法	说明
boolean add()	表尾添加一个元素
boolean addAll(Collection<? extends E> c)	按照集合的顺序，将指定集合中的所有元素追加到列表尾
E get(int index)	返回Index位置的元素
boolean remove(Object o)	删除指定元素的第一个出现元素(如果存在)

// 默认容量

private static final int DEFAULT_CAPACITY = 10;

//空数组，容量为0调用
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空数组，传入容量时使用，添加第一个元素的时候会扩展为默认容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存储元素的数组
transient Object[] elementData; // non-private to simplify nested class access

// 集合中元素的个数

private int size;

(1).add:

添加元素到队尾位置，平均时间复杂度为O(1)

public boolean add(E e) {
       // 检查是否扩容
       ensureCapacityInternal(size + 1);  
       elementData[size++] = e;
       return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是为才创建的是空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//返回10与所需大小较大的一个
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //否则返回所需大小
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果所需大小比数组大小更大就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//扩容
}
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
       	//1.5倍扩容
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩容量后发现比需要的容量还小，则返回需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建新容量的数组并把老数组拷贝到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

(2).void add(int index, E element):

public void add(int index, E element) {
        rangeCheckForAdd(index);//检查index位置是否合理
		//是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 把插入索引位置后的元素都往后挪一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在插入索引位置放置插入的元素
        elementData[index] = element;
        size++;
}
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

(3).addAll()：

public boolean addAll(Collection<? extends E> c) {
	//将集合转化为数组
    Object[] a = c.toArray();
    int numNew = a.length;
	//是否扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
	//拷贝到表尾
    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

}

(4.)get():

//获取指定索引位置的元素：
public E get(int index) {

    rangeCheck(index);
    return elementData(index);

}
E elementData(int index) {

    return (E) elementData[index];

}

(5).E remove(int index):

public E remove(int index) {

    rangeCheck(index);
    modCount++;

    E oldValue = elementData(index);
	//移动元素次数
    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;

}

(6).boolean remove(Object o)：

//找到第一个等于指定元素值的元素；
public boolean remove(Object o) {

    if (o == null) {

        for (int index = 0; index < size; index++)

            if (elementData[index] == null) {

                fastRemove(index);
                return true;
            }

    } else {

        for (int index = 0; index < size; index++)

            if (o.equals(elementData[index])) {

                fastRemove(index);
                return true;
            }

    }
    return false;

}

private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // clear to let GC do its work

}

4.LinkedList

底层是双向链表，由于既实现了List有实现了Queue，所以可以作为队列或者栈来使用

优点： 不用扩容，增删元素方便

.缺点： 查改元素消耗时间多

慎用get(int index)这个方法，需要遍历链表，虽然get方法优化在前size/2在从头开始遍历，否则从尾开始遍历，但是当元素非常多的时候，遍历的所花的时间是非常多的