Java中的数据结构 0.接口介绍

0. Queue接口

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

LinkedList类实现了Queue接口

Queue接口中主要有以下方法

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

element和peek返回前端而不删除

可以通过继承AbstractQueue来实现Queue中大多数方法

Queue接口的使用示例

package com.hyh0.learning.collections;

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

public class GeneralTest {

	public static void main(String[] args) {
		Queue<String> list = new LinkedList<>();
		list.offer("hello");
		list.offer(" ");
		list.offer("world");
		
		while(list.peek() != null) {
			System.out.print(list.poll());
		}
		System.out.println();
	}

}

1. Iterator接口

Iterator接口有三个方法

public interface Iterator<E>;
{
    E next();
    boolean hasNext();
    default void remove(); 
}

PS: 这里的remove()使用了jdk1.8的default关键字定义了默认实现，如果不重载就使用会抛出UnsupportedOperationException异常，所以实现接口时应该重载这个方法(?)

next方法会返回下一个元素

hasNext返回是否有下一个元素

remove会删除上一次next()返回的元素（每一次使用remove前都必须调用过next方法）

用Iterator可以遍历元素

2. Iterable接口

Iterable接口有一个方法，其返回一个Iterator

public interface Iterable<E>;
{
    Iterator<E> iterator();
}

实现了Iterable接口的对象都可以使用 for – each 循环

3. ListIterator接口

ListIterator继承自Iterator

除了Iterator中的方法，ListIterator接口中还有add方法在当前位置后添加元素

除此之外，还有previous与hasPrevious方法

使用add在原有LinkedList中间插入” “的示例

public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<>();
    list.add("hello");
    list.add("world");

    ListIterator<String> it = list.listIterator();
    it.next();
    it.add(" ");

    it.previous(); //添加了元素后迭代器后移
    it.previous(); //所以需要后移两次

    while (it.hasNext()) {
        System.out.print(it.next());
    }
    System.out.println();
}

4. Deque接口

Deque接口与Queue接口类似，但不同于Queue只能在尾部添加头部读取，Deque可以选择在头部或者尾部进行操作

ArrayDeque和LinkedList实现了Deque接口