1 队列

概述

队列是一种先进先出的数据结构，在一端进行插入，另一端进行删除的特殊线性表，按照先进先出的的与原则进行数据存取，最先进入的数据，最先被读取。

队列的实现

public class Queue<T> implements Iterable {

    private int size;
    private Node<T> head;
    private Node<T> last;

    @Override
    public Iterator iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator{

        Node<T> node;

        public QIterator(){
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node!=null;
        }

        @Override
        public Object next() {
            Object t = node.ele;
            node = node.next;
            return t;
        }
    }

    //定义结点类
    static class Node<T>{
        private T ele;
        private Node<T> next;

        public Node(T ele,Node<T> next){
            this.ele = ele;
            this.next = next;
        }
    }

    /**
     * 构造方法
     */
    public Queue(){
        this.size = 0;
        this.head = null;
        this.last = null;
    }

    /**
     * 获取队列大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 入队
     * @param ele
     */
    public void enqueue(T ele){
        Node<T> node = new Node<>(ele,null);
        if(isEmpty()){
            head = node;
            last = node;
            size++;
            return;
        }
        last.next = node;
        last = node;
        size++;
    }

    /**
     * 出队
     * @return
     */
    public T dequeue(){
        if(isEmpty()){
            return null;
        }
        Node<T> node = head;
        head = head.next;
        size--;
        return node.ele;
    }

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

2 符号表

符号表存储的数据元素是一对键值对，可以根据键来找值。

符号表中，键具有唯一性。

应用：字典，图书索引，网络搜索。

符号表实现

类图

//代码实现
public class SymbolTable<K,V> {
		//记录头结点
    private Node<K,V> head;
    private int size;

    static class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable(){
        this.head = new Node<>(null,null,null);
        this.size = 0;
    }

    public int size(){
        return size;
    }

    /**
     * 插入键值对
     * @param key
     * @param value
     */
    public void put(K key,V value){
        if(key == null){
            throw new IllegalArgumentException("key 不能为空！");
        }
        //符号表中已经存在键为key的键值对，只需要找到该结点替换value
        Node<K,V> node = head;
        while (node.next!=null){
            node = node.next;
            //遍历，判断key是否相同
            if(node.key.equals(key)){
                node.value = value;
                return;
            }
        }
        //key不相同，则添加
        Node<K, V> newNode = new Node<>(key, value, null);
        Node<K,V> oldFirst = head.next;
        head.next = newNode;
        newNode.next = oldFirst;
        size++;
    }

    /**
     * 根据键获取值
     * @param key
     * @return
     */
    public V get(K key){
        Node<K,V> node = head.next;
        while (node != null){
            if(node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 移除指定键的元素
     * @param key
     */
    public void remove(K key){
        Node<K,V> curr = head;
        while (curr.next!=null){
            if(curr.next.key.equals(key)){
                curr.next = curr.next.next;
                size--;
                return;
            }
            curr = curr.next;
        }
    }
}

有序符号表实现

上述的符号表我们称为无序符号表，插入的时候没有考虑到键值对的顺序，而有时候我们需要根据键的大小进行排序，这就需要用到我们的有序符号表了。

限定K继承Comparable接口，这样就可以使用compareTo方法进行比较了，我们只需要在原来符号表的实现修改put方法即可。

public class OrderSymbolTable<K extends Comparable<K>,V> {

    private Node<K,V> head;
    private int size;

    static class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable(){
        this.head = new Node<>(null,null,null);
        this.size = 0;
    }

    public int size(){
        return size;
    }

    /**
     * 插入键值对
     * @param key
     * @param value
     */
    public void put(K key,V value){
       //定义两个变量，记录当前结点和上一个结点
        Node<K,V> curr = head.next;
        Node<K,V> pre = head;

        while (curr!=null && key.compareTo(curr.key)>0){
            pre = curr;
            curr = curr.next;
        }

        //如果curr的key和key相等，则替换对应的值
        if(curr!=null && curr.key.compareTo(key) == 0){
            curr.value = value;
            return;
        }
        //如果curr的key和key不相等，则插入
        Node<K, V> newNode = new Node<>(key, value, curr);
        pre.next = newNode;
        size++;
    }

    /**
     * 根据键获取值
     * @param key
     * @return
     */
    public V get(K key){
        Node<K,V> node = head.next;
        while (node != null){
            if(node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 移除指定键的元素
     * @param key
     */
    public void remove(K key){
        Node<K,V> curr = head;
        while (curr.next!=null){
            if(curr.next.key.equals(key)){
                curr.next = curr.next.next;
                size--;
                return;
            }
            curr = curr.next;
        }
    }
}