抽象数据类型（ADT，abstract data type）

• 抽象数据类型是带有一组操作的一些对象的集合。
• 抽象数据类型可以用以下的三元组来表示：
  ADT抽象数据类型名{
  数据对象：<数据对象的定义>
  数据关系：<数据关系的定义>
  基本操作：<基本操作的定义>
  } ADT抽象数据类型名
• 抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。
• 参考：http://c.biancheng.net/view/7526.html

表ADT

• 表的定义
  形如的一组元素集合，我们称之为表，大小为N。N为0的表，我们称之为空表。
  我们说的后继为，前驱为。
• 表的一般操作
  printList，makeEmpty，find（返回某一项首次出现的位置），insert/remove（从表的某个位置插入和删除某个元素），findKth（返回某个位置上的元素）
• 表的简单数组实现
  虽然数组由固定容量创建，但在需要的时候可以用双倍容量扩展。
  1）printList操作：线性时间，即O(N)时间复杂度
  2）findKth操作：常数时间，由下标直接索引，即O(1)时间复杂度；
  3）插入和删除操作：和发生的位置有关，最坏情况下，如在位置0插入元素或者删除元素，花费O(N)时间复杂度。但在末尾删除或者添加，花费O(1)时间。
• 简单链表
  为了避免插入和删除操作的线性开销，我们需要保证表可以不连续存储，否则表的每个部分都可能需要整体移动。
  链表由一系列节点组成，这些节点不必再内存中相连。每一个节点均含有表元素和后继节点的链（link）。我们称之为next链，最后一个单元的next链引用为null。
  1）printList操作：线性时间，需要从第一个节点遍历到最后一个节点
  2）find(x)操作：线性时间，需要从第一个节点遍历到最后一个节点
  3）findKth操作：O(K)，也是线性时间，但可以通过一次遍历可获取findKth(1)，findKth(2)，findKth(n)所有答案。
  4）插入和删除操作：单链表只维持了头部节点的引用，对于头部插入的操作，花费O(1)时间，对于其他位置的插入，花费线性时间定位到该位置，插入操作或删除操作本身只涉及常数个节点链的改变，总体时间还是为线性时间；双链表维持头部和尾部两个节点的引用，所于头部和尾部的插入删除操作，只花费O(1)的常数时间。

Java Collections API中的表

Collection接口

Collection接口扩展了Iterable接口，实现了Iterable接口的那些类可以使用增强for循环：

Iterator接口
实现Iterator接口的集合必须提供一个iterator()方法，返回一个Iterator类型的对象。

使用Iterator的remove方法，相比使用Collection的remove方法的优点：
1）Collection的remove方法必须首先找到要被删除的项。在实现诸如在集合中每隔一项删除一项的功能，Iterator很容易实现，并且效率更高。
2）如果对正在被迭代的集合进行结构上的改变（add，remove，clear等），我们更愿意使用迭代器的remvoe方法，如果使用Collection的remove方法会抛出ConcurrentModificationException。

List接口、ArrayList类和LinkedList类
List接口继承了Collection接口，并且增加了额外的一些方法。

List接口中的add和remvoe支持指定位置的增加和删除，和Collection接口中指定元素的增加和删除不一样。get和set可以访问或者改变由位置索引idx给定的表中指定位置上的项。

List ADT有两种流行的实现方式：

• ArrayList类
  1）实现：可增长数组
  2）优点：对get和set的调用花费常数时间，因为通过数组的下标直接定位。
  3）缺点：对新项的插入和现有项的删除代价昂贵，花费线性时间，除非插入和删除在ArrayList的末端进行。
• LinkedList类
  1）实现：双链表
  2）优点：新项的插入和现有项的删除开销都很小，这里假设变动项的位置已知。如果变动项的位置不知，那么仍然花费线性时间定位到变动项位置，然后花费常数时间进行插入操作；但是对于开头和结尾位置的删除和插入只花费常数时间。所以LinkedList额外提供了addFirst和removeFirst，addLast和removeLast
  3）缺点：不容易操作索引，因此对get的调用是昂贵的
• 共通点
  对搜索而言，ArrayList和LinkedList都是低效的，对Collection的contains和remove（以AnyType为参数）的调用都花费线性时间。

例子：remove方法对LinkedList类的使用
例子：将表中所有的值为偶数的项删除。
办法：使用LinkedList，并且使用迭代器进行遍历。

ArrayList的类实现

package com.corp.qiyun.datastruct;

public class MyArrayList<AnyType> implements Iterable<AnyType> {

    private static final int DEFAULT_CAPACITY = 10;

    private AnyType[] theItems;
    private int theSize; // 元素个数, 保持最后元素的位置

    /**
     * Construct an empty ArrayList.
     */
    public MyArrayList() {
        doClear();
    }

    /**
     * Returns the number of items in this collection.
     *
     * @return the number of items in this collection.
     */
    public int size() {
        return theSize;
    }

    /**
     * Returns true if this collection is empty.
     *
     * @return true if this collection is empty.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Returns the item at position idx.
     *
     * @param idx the index to search in.
     * @throws ArrayIndexOutOfBoundsException if index is out of range.
     */
    public AnyType get(int idx) {
        if (idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
        return theItems[idx];
    }

    /**
     * Changes the item at position idx.
     *
     * @param idx    the index to change.
     * @param newVal the new value.
     * @return the old value.
     * @throws ArrayIndexOutOfBoundsException if index is out of range.
     */
    public AnyType set(int idx, AnyType newVal) {
        if (idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
        AnyType old = theItems[idx];
        theItems[idx] = newVal;

        return old;
    }

    @SuppressWarnings("unchecked")
    public void ensureCapacity(int newCapacity) {
        if (newCapacity < theSize)
            return;

        AnyType[] old = theItems;
        theItems = (AnyType[]) new Object[newCapacity];
        for (int i = 0; i < size(); i++)
            theItems[i] = old[i];
    }

    /**
     * Adds an item to this collection, at the end.
     *
     * @param x any object.
     * @return true.
     */
    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    /**
     * Adds an item to this collection, at the specified index.
     *
     * @param x any object.
     * @return true.
     */
    public void add(int idx, AnyType x) {
        if (theItems.length == size())
            ensureCapacity(size() * 2 + 1);

        for (int i = theSize; i > idx; i--)
            theItems[i] = theItems[i - 1];

        theItems[idx] = x;
        theSize++;
    }

    /**
     * Removes an item from this collection.
     *
     * @param idx the index of the object.
     * @return the item was removed from the collection.
     */
    public AnyType remove(int idx) {
        AnyType removedItem = theItems[idx];

        for (int i = idx; i < size() - 1; i++)
            theItems[i] = theItems[i + 1];
        theSize--;

        return removedItem;
    }

    /**
     * Change the size of this collection to zero.
     */
    public void clear() {
        doClear();
    }

    private void doClear() {
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    /**
     * Obtains an Iterator object used to traverse the collection.
     *
     * @return an iterator positioned prior to the first element.
     */
    public java.util.Iterator<AnyType> iterator() {
        return new ArrayListIterator();
    }

    /**
     * Returns a String representation of this collection.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");

        for (AnyType x : this)
            sb.append(x + " ");
        sb.append("]");

        return new String(sb);
    }

    /**
     * This is the implementation of the ArrayListIterator.
     * It maintains a notion of a current position and of
     * course the implicit reference to the MyArrayList.
     */
    private class ArrayListIterator implements java.util.Iterator<AnyType> {
        private int current = 0;
        private boolean okToRemove = false;

        public boolean hasNext() {
            return current < size(); // 这里相当于MyArrayList.this.size()，前面外部类引用可省略
        }


        public AnyType next() {
            if (!hasNext())
                throw new java.util.NoSuchElementException();

            okToRemove = true;
            return theItems[current++]; // 即MyArrayList.this.theItems[current++]
        }

        public void remove() {
            if (!okToRemove)
                throw new IllegalStateException();
            // 编译器自动为非静态内部类添加一个成员变量， 这个成员变量就是指向外部类对象的引用；这里没有省略MyArrayList.this是因为java.util.Iterator声明了remove方法，为了防止歧义，这里必须加上
            MyArrayList.this.remove(--current); 
            okToRemove = false;
        }
    }

}

class TestArrayList {
    public static void main(String[] args) {
        MyArrayList<Integer> lst = new MyArrayList<>();

        for (int i = 0; i < 10; i++)
            lst.add(i);
        for (int i = 20; i < 30; i++)
            lst.add(0, i);

        lst.remove(0);
        lst.remove(lst.size() - 1);

        System.out.println(lst);
    }
}

如果将ArrayListIterator类声明为static，那么调用方式就不一样了。

public class MyArrayList<AnyType> implements Iterable<AnyType> {

    private static final int DEFAULT_CAPACITY = 10;
    private AnyType[] theItems;
    ...

    public java.util.Iterator<AnyType> iterator() {
        return new ArrayListIterator(this); // 传入外部类对象引用
    }

     // 静态内部类
     private static class ArrayListIterator implements java.util.Iterator<AnyType> {
        private int current = 0;
        private boolean okToRemove = false;
        private MyArrayList<Anytype> theList; // 定义一个外部类成员变量
        
        public ArrayListIterator (MyArrayList<Anytype> list){
                theList = list; // 接受外部类对象初始化成员变量
        }

        public boolean hasNext() {
            return current < theList.size();  // 用外部类对象调用外部类的方法
        }


        public AnyType next() {
            if (!hasNext())
                throw new java.util.NoSuchElementException();
            okToRemove = true;
            return theList.theItems[current++]; // 用外部类对象调用外部类的成员变量
        }

        public void remove() {
            if (!okToRemove)
                throw new IllegalStateException();
            
            theList.remove(--current); 
            okToRemove = false;
        }
    }
    

LinkedList类的实现

• 维持一个头结点和一个尾结点
• 表的大小
• modCount：代表自从构造以来对链表所改变的次数。每次对add或者remove的调用都将更新modCount。其用处是，当一个迭代器对象被建立时，它将存储集合的modCount，对迭代器调用remove操作，将更新modCount，同时链表的modCount也会同时被更新。这样每次对迭代器方法next或者remove的调用都将验证该链表内的当前modCount和迭代器内存储的modCount是否一致，如果不一致，那么将抛出ConcurrentModificationException。

package com.corp.qiyun.datastruct;

/**
 * LinkedList class implements a doubly-linked list.
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    /**
     * Construct an empty LinkedList.
     */
    public MyLinkedList( )
    {
        doClear( );
    }
    
    private void clear( )
    {
        doClear( );
    }
    
    /**
     * Change the size of this collection to zero.
     */
    public void doClear( )
    {
        beginMarker = new Node<>( null, null, null );
        endMarker = new Node<>( null, beginMarker, null );
        beginMarker.next = endMarker;
        
        theSize = 0;
        modCount++;
    }
    
    /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size()
    {
        return theSize;
    }
    
    public boolean isEmpty( )
    {
        return size() == 0;
    }
    
    /**
     * Adds an item to this collection, at the end.
     * @param x any object.
     * @return true.
     */
    public boolean add( AnyType x )
    {
        add( size(), x );   
        return true;         
    }
    
    /**
     * Adds an item to this collection, at specified position.
     * Items at or after that position are slid one position higher.
     * @param x any object.
     * @param idx position to add at.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
     */
    public void add( int idx, AnyType x )
    {
        addBefore( getNode( idx, 0, size() ), x );
    }
    
    /**
     * Adds an item to this collection, at specified position p.
     * Items at or after that position are slid one position higher.
     * @param p Node to add before.
     * @param x any object.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
     */    
    private void addBefore( Node<AnyType> p, AnyType x )
    {
        Node<AnyType> newNode = new Node<>( x, p.prev, p );
        newNode.prev.next = newNode;
        p.prev = newNode;         
        theSize++;
        modCount++;
    }   
    
    
    /**
     * Returns the item at position idx.
     * @param idx the index to search in.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public AnyType get( int idx )
    {
        return getNode( idx ).data;
    }
        
    /**
     * Changes the item at position idx.
     * @param idx the index to change.
     * @param newVal the new value.
     * @return the old value.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public AnyType set( int idx, AnyType newVal )
    {
        Node<AnyType> p = getNode( idx );
        AnyType oldVal = p.data;
        
        p.data = newVal;   
        return oldVal;
    }
    
    /**
     * Gets the Node at position idx, which must range from 0 to size() - 1.
     * @param idx index to search at.
     * @return internal node corresponding to idx.
     * @throws IndexOutOfBoundsException if idx is not between 0 and size() - 1, inclusive.
     */
    private Node<AnyType> getNode( int idx )
    {
        return getNode( idx, 0, size() - 1 );
    }

    /**
     * Gets the Node at position idx, which must range from lower to upper.
     * @param idx index to search at.
     * @param lower lowest valid index.
     * @param upper highest valid index.
     * @return internal node corresponding to idx.
     * @throws IndexOutOfBoundsException if idx is not between lower and upper, inclusive.
     */    
    private Node<AnyType> getNode( int idx, int lower, int upper )
    {
        Node<AnyType> p;
        
        if( idx < lower || idx > upper )
            throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size() );
            
        if( idx < size() / 2 )
        {
            p = beginMarker.next;
            for( int i = 0; i < idx; i++ )
                p = p.next;            
        }
        else
        {
            p = endMarker;
            for( int i = size(); i > idx; i-- )
                p = p.prev;
        } 
        
        return p;
    }
    
    /**
     * Removes an item from this collection.
     * @param idx the index of the object.
     * @return the item was removed from the collection.
     */
    public AnyType remove( int idx )
    {
        return remove( getNode( idx ) );
    }
    
    /**
     * Removes the object contained in Node p.
     * @param p the Node containing the object.
     * @return the item was removed from the collection.
     */
    private AnyType remove( Node<AnyType> p )
    {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        
        return p.data;
    }
    
    /**
     * Returns a String representation of this collection.
     */
    public String toString( )
    {
        StringBuilder sb = new StringBuilder( "[ " );

        for( AnyType x : this )
            sb.append( x + " " );
        sb.append( "]" );

        return new String( sb );
    }

    /**
     * Obtains an Iterator object used to traverse the collection.
     * @return an iterator positioned prior to the first element.
     */
    public java.util.Iterator<AnyType> iterator( )
    {
        return new LinkedListIterator( );
    }

    /**
     * This is the implementation of the LinkedListIterator.
     * It maintains a notion of a current position and of
     * course the implicit reference to the MyLinkedList.
     */
    private class LinkedListIterator implements java.util.Iterator<AnyType>
    {
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        
        public boolean hasNext( )
        {
            return current != endMarker;
        }
        
        public AnyType next( )
        {
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( );
            if( !hasNext( ) )
                throw new java.util.NoSuchElementException( ); 
                   
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }
        
        public void remove( )
        {
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( );
            if( !okToRemove )
                throw new IllegalStateException( );
                
            MyLinkedList.this.remove( current.prev );
            expectedModCount++;
            okToRemove = false;       
        }
    }
    
    /**
     * This is the doubly-linked list node.
     */
    private static class Node<AnyType>
    {
        public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
        {
            data = d; prev = p; next = n;
        }
        
        public AnyType data;
        public Node<AnyType>   prev;
        public Node<AnyType>   next;
    }
   
}

class TestLinkedList
{
    public static void main( String [ ] args )
    {
        MyLinkedList<Integer> lst = new MyLinkedList<>( );

        for( int i = 0; i < 10; i++ )
                lst.add( i );
        for( int i = 20; i < 30; i++ )
                lst.add( 0, i );

        lst.remove( 0 );
        lst.remove( lst.size() - 1 );

        System.out.println( lst );

        java.util.Iterator<Integer> itr = lst.iterator( );
        while( itr.hasNext( ) )
        {
                itr.next( );
                itr.remove( );
                System.out.println( lst );
        }
    }
}

栈ADT

栈模型
栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。对栈的基本操作有进栈（push）和出栈（pop）。栈的特性是后进先出。
栈的单链表实现
栈的第一种实现是使用单链表。通过在链表的顶端插入来实现push，通过删除表顶端元素来实现pop。top操作只是考察表顶端元素并返回它的值。

 public class MyStack<T> {

    private LinkNode<T> top; // 栈顶指针
    private Integer size;// 栈的当前大小

    public MyStack() {
        size = 0;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int getSize() {
        return this.size;
    }

    public void push(T data) {
        if(top == null){
            top = new LinkNode<>(data);
            size++;
            return;
        }
        LinkNode<T> newNode = new LinkNode<T>(data);
        newNode.setNext(top);
        top = newNode;
        size++;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) top.getDate();
    }

    public T pop() {
        T data = peek();
        size--;
        top = top.next;
        return data;
    }

    public static class LinkNode<T> {
        private T date;
        private LinkNode next;

        public LinkNode(T data){
            date = data;
        }

        public T getDate() {
            return date;
        }

        public void setDate(T date) {
            this.date = date;
        }

        public LinkNode getNext() {
            return next;
        }

        public void setNext(LinkNode next) {
            this.next = next;
        }
    }

}

栈的数组实现
栈的数组实现是更流行的解决方案。由于模仿ArrayList的add操作，因此相应的实现方法非常简单。

public class MyStack<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private T[] array;
    private int size;

    public MyStack(Class<T> type) {
        // 泛型数组的实例化方法
        array = (T[]) Array.newInstance(type, DEFAULT_CAPACITY); // 由于泛型擦除, 不能使用 new T[];
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void enlarge() {
        array = Arrays.copyOf(array, array.length * 2);
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[size - 1];
    }

    public T pop() {
        T top = peek();
        size--;
        return top;
    }

    public void push(T element) {
        if (size == array.length) {
            enlarge();
        }
        array[size++] = element;
    }

    public static void main(String[] args) {
        MyStack stack = new MyStack(Integer.class);
        System.out.println(stack.isEmpty());
        for(int i=0; i<10; i++){
            stack.push(i);
        }
        stack.push(10);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(22);
        System.out.println(stack.pop());
    }

应用

• 平衡符号
  举例说明："[()]"是合法的，"[(])"是非法的。
  算法：做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号，则将其推入栈中。如果字符是一个封闭符号，则当栈是空时报错，否则将栈顶元素出栈，如果弹出的栈顶元素不是对应的开放符号，则报错。在文件结尾，如果栈非空则报错。
• 中缀到后缀的转换
  中缀表达式：a + b * c + (d * e + f) * g
  后缀表达式：a b c * + d e * f + g * +
  转换算法：1）遍历中缀表达式，遇到操作数直接输出；2）遇到操作符，入栈，入栈前将依次弹出栈中所有优先级比即将入栈的操作符的优先级高或者相等的操作符；3）特例：左括号优先级最高，但左括号只有在遍历到右括号时才会出栈；当遍历到右括号时，弹出栈顶至左括号之间的所有操作符；4）左、右括号出栈时，不输出；所以遍历到右括号，只需按规则出栈元素即可，右括号本身不需入栈。
  后缀表达式的作用：通过后缀表达式，利用栈，可以很容易计算出对应中缀表达式的值。
• 后缀表达式
  利用后缀表达式计算值的算法：使用栈；遇到一个操作数，将其入栈；遇到一个运算符，从栈顶弹出两个操作数，计算之后，将结果入栈；遍历完成之后，栈中只剩一个数，即最后的结果。
  优点：计算一个后缀表达式花费的时间是O(N)，并且在计算时，只需遵循上面的算法，没有必要知道任何优先的规则，计算非常简单。
• 方法调用
  方法调用的过程，就是栈帧入栈和出栈的过程。

队列ADT

队列模型
队列也是表，使用队列时，插入在一端进行而删除则在另一端进行。队列的基本操作是入队（enqueue）和出队（dequeue）；入队即在表的末端（队尾rear）插入一个元素，出队即删除并返回在表的开头（队头front）的元素。
队列的数组实现

• 循环数组：head或者tail每次加1之后需要对array.length取模
• head出队列，tail入队列，初始化时，tail要比head索引小1。
• 以下队列不支持动态扩容，不支持多线程

public class MyCircularQueue<T> {

    private T[] array;
    private int head;
    private int tail;
    private int size;

    public MyCircularQueue(Class<T> type, int capacity) {
        array = (T[]) Array.newInstance(type, capacity);
        head = 0;
        tail = array.length - 1; // or tail = -1
        size = 0;
    }

    public boolean poll(T value) {
        if (isFull()) {
            return false;
        }
        tail = (tail + 1) % array.length;
        array[tail] = value;
        size++;
        return true;
    }

    public T add() {
        if (isEmpty()) {
            return null;
        }
        T element = array[head];
        head = (head + 1) % array.length;
        size--;
        return element;
    }

    public T front() {
        if (isEmpty() == true) {
            return null;
        }
        return array[head];
    }

    public T rear() {
        if (isEmpty() == true) {
            return null;
        }
        return array[tail];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == array.length;
    }

}

队列的单链表实现

• 维护一个dummyHead哑节点，指向头元素的前一个节点；维护一个tail节点，指向尾元素；
• 加入节点，成为tail的next节点，tail再指向加入的新节点；
• 移除节点，返回dummyHead节点的next节点元素（即头元素），然后将dummyHead.next指向dummyHead.next.next节点；注意，如果dummyHead.next.next节点为null，即刚刚删除的元素为最后一个元素，需要将tail指向dummyHead。

public class MyQueue<T> {

    private LNode dummyHead;
    private LNode tail;
    private Integer size;

    public MyQueue() {
        dummyHead = new LNode<T>(); // dummyHead指向首元素的前一个节点
        tail = dummyHead; // tail指向尾元素, 当tail == dummyHead时, 说明队列为空
        size = 0;
    }

    public MyQueue clearQueue() {
        tail = dummyHead;
        size = 0;
        return this;
    }

    public Boolean isEmpty() {
        return tail == dummyHead; // 或者 return size == 0;
    }

    public Integer getSize() {
        return size;
    }

    public T getDummyHead() {
        return (T) dummyHead.getNext().getData();
    }

    public Boolean add(T e) {
        //入队 从队尾入
        LNode newNode = new LNode<>(e, null);
        tail.setNext(newNode);
        tail = newNode;
        size++;
        return Boolean.TRUE;
    }

    public T DeQueue() {
        // 删除的时候, 如果是最后一个元素, 这个时候尾指针需要调整为指向头节点
        if (dummyHead.getNext().getNext() == null) {
            T e = (T) dummyHead.getNext().getData();
            dummyHead.setNext(null);
            tail = dummyHead;
            return e;
        }
        T e = (T) dummyHead.getNext().getData();
        dummyHead.setNext(dummyHead.getNext().getNext());
        size--;
        return e;
    }

    static class LNode<T> {
        private T data;
        private LNode next;

        public LNode() {

        }

        public LNode(T data, LNode next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public LNode getNext() {
            return next;
        }

        public void setNext(LNode next) {
            this.next = next;
        }
    }


    public static void main(String[] args) {
        MyQueue<Integer> linkedQueue = new MyQueue<>();
        linkedQueue.add(1);
        linkedQueue.add(2);
        linkedQueue.add(3);
        Integer size = linkedQueue.size;
        for (Integer integer = 0; integer < size; integer++) {
            System.out.println(linkedQueue.DeQueue());
        }
        System.out.println(linkedQueue.isEmpty());
    }
}

队列应用
广度优先算法可使用队列实现；
深度优先算法可使用栈实现；