1：数据抽象

概念：

       抽象数据类型，是一种能够对使用者隐藏数据表示的数据类型，抽象数据类型之所以重要，是因为他在程序设计上支持封装。

本节目标：本节将介绍三种抽象类型，用java实现，背包，堆栈，队列等最简单的数据结构。

1. 背包   背包是一种不支持从中删除元素的集合数据类型。他的目的就是帮助用例手机元素并迭代遍历所有收集到的元素。API图示参考1.1

   

   import java.util.Iterator;import java.util.NoSuchElementException;/**
       bag数据结构的实现  后进先出 不支持删除元素
    */public class Bag<Item> implements Iterable<Item> {    private int N;    private Node<Item> first;    // helper linked list class    private static class Node<Item> {        private Item item;        private Node<Item> next;    }    /**     * Is this bag empty?     *     * @return true if this bag is empty; false otherwise     */    public boolean isEmpty() {        return first == null;    }    /**     * Returns the number of items in this bag.     *     * @return the number of items in this bag     */    public int size() {        return N;    }    /**     * Adds the item to this bag.     *     * @param item the item to add to this bag     */    public void add(Item item) {        Node<Item> oldfirst = first;        first = new Node<Item>();        first.item = item;        first.next = oldfirst;        N++;    }    /**     * Initializes an empty bag.     */    public Bag() {        N = 0;        first = null;    }    @Override    public Iterator<Item> iterator() {        return new ListIterator<Item>(first);    }    private class ListIterator<Item> implements Iterator<Item> {        private Node<Item> current;        public ListIterator(Node<Item> first) {            current = first;        }        @Override        public boolean hasNext() {            return current != null;        }        @Override        public Item next() {            if (!hasNext())                throw new NoSuchElementException();            Item item = current.item;            current = current.next;            return item;        }        @Override        public void remove() {            throw new UnsupportedOperationException();        }    }}

2. 队列 先进先出 可以联想在剧院门前排队等待入门的人
   

   先进先出的队列结构，FIFO。Code实现

   1. 

   2. package com.luochuang.demo.stdlib;import org.w3c.dom.ls.LSException;import java.util.Iterator;import java.util.NoSuchElementException;public class Queue<Item> implements Iterable<Item> {    private int N;// number of element on queue    private Node<Item> first;// beginning of queue    private Node<Item> last;// end of queue    public class Node<Item> {        private Node<Item> next;        private Item item;    }    public Item peek() {        if (isEmpty()) {            throw new NoSuchElementException();        }        return first.item;    }    /**     * add item to queue     *     * @param item the item to add     */    public void enQueue(Item item) {        Node<Item> oldlast = last;        last = new Node<Item>();        last.item = item;        last.next = null;        if (isEmpty()) {            first = last;        } else {            oldlast.next = last;        }        N++;    }    /**     * Removes and returns the item on this queue that was least recently added.     *     * @return the item on this queue that was least recently added     * @throws java.util.NoSuchElementException if this queue is empty     */    public Item deQueue() {        if (isEmpty()) {            throw new NoSuchElementException();        }        Item item = first.item;        first = first.next;        N--;        if (isEmpty()) {            last = null;        }        return item;    }    /**     * is this queue empty?     *     * @return true if this queue is empty otherwise     */    public boolean isEmpty() {        return first == null;    }    /**     * Returns the number of items in this queue.     *     * @return the number of items in this queue     */    public int size() {        return N;    }    /**     * Initializes an empty queue.     */    public Queue() {        first = null;        last = null;        N = 0;    }    @Override    public Iterator<Item> iterator() {        return null;    }    public class ListIterator implements Iterator<Item> {        private Node<Item> current;        public ListIterator(Node<Item> first) {            first = current;        }        @Override        public boolean hasNext() {            return current == null;        }        @Override        public Item next() {            if (!hasNext())                throw new NoSuchElementException();            Item item = current.item;            current = current.next;            return item;        }        @Override        public void remove() {            throw new UnsupportedOperationException();        }    }}

3. 下压栈   
   
   下压栈是一种基于后进先出的队列结构，LIFO。比如点击超级链接中的按钮，当回退之后能重新访问之前的页面，即从栈中弹出。也可以联想桌面上放的一匝便签.

package com.luochuang.demo.stdlib;import java.util.Iterator;import java.util.NoSuchElementException;public class Stack<Item> implements Iterable<Item> {    private int N;    private Node<Item> first;    /**     * Initializes an empty stack     */    public Stack() {        first = null;        N = 0;    }    /**     * Adds the item to this stack.     * @param item the item to add     */    public void push(Item item) {        Node<Item> oldfirst = first;        first = new Node<Item>();        first.item = item;        first.next = oldfirst;        N++;    }    /**     * Removes and returns the item most recently added to this stack.     *     * @return the item most recently added     * @throws java.util.NoSuchElementException if this stack is empty     */    public Item pop() {        if (isEmpty())            throw new NoSuchElementException("Stack underflow");        Item item = first.item; // save item to return        first = first.next; // delete first node        N--;        return item; // return the saved item    }    /**     * Returns (but does not remove) the item most recently added to this stack.     * @return the item most recently added to this stack     * @throws java.util.NoSuchElementException if this stack is empty     */    public Item peek() {        if (isEmpty()) throw new NoSuchElementException("Stack underflow");        return first.item;    }    public boolean isEmpty() {        return first == null;    }    public int size() {        return N;    }    private class Node<Item> {        private Node<Item> next;        private Item item;    }    /**     * Returns a string representation of this stack.     * @return the sequence of items in the stack in LIFO order, separated by spaces     */    public String toString() {        StringBuilder s = new StringBuilder();        for (Item item : this)            s.append(item + " ");        return s.toString();    }    @Override    public Iterator<Item> iterator() {        return new ListIterator(first);    }    public class ListIterator implements Iterator<Item> {        public Node<Item> current;        public ListIterator(Node<Item> first) {            first = current;        }        @Override        public boolean hasNext() {            return current == null;        }        @Override        public Item next() {            if (!hasNext()) {                throw new NoSuchElementException();            }            Item item = current.item;            current = current.next;            return item;        }        @Override        public void remove() {            throw new UnsupportedOperationException();        }    }}