面試官問你：“隊(duì)列和符號(hào)表要怎么實(shí)現(xiàn)？”

1 隊(duì)列

概述

隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，在一端進(jìn)行插入，另一端進(jìn)行刪除的特殊線性表，按照先進(jìn)先出的原則進(jìn)行數(shù)據(jù)存取，最先進(jìn)入的數(shù)據(jù)，最先被讀取。

隊(duì)列的實(shí)現(xiàn)

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;
        }
    }

    //定義結(jié)點(diǎn)類
    static class Node<T>{
        private T ele;
        private Node<T> next;

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

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

    /**
     * 獲取隊(duì)列大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 入隊(duì)
     * @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++;
    }

    /**
     * 出隊(duì)
     * @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 符號(hào)表

符號(hào)表存儲(chǔ)的數(shù)據(jù)元素是一對(duì)鍵值對(duì)，可以根據(jù)鍵來找值。

符號(hào)表中，鍵具有唯一性。

應(yīng)用：字典，圖書索引，網(wǎng)絡(luò)搜索。

符號(hào)表實(shí)現(xiàn)

類圖

//代碼實(shí)現(xiàn)
public class SymbolTable<K,V> {
    //記錄頭結(jié)點(diǎn)
    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;
    }

    /**
     * 插入鍵值對(duì)
     * @param key
     * @param value
     */
    public void put(K key,V value){
        if(key == null){
            throw new IllegalArgumentException("key 不能為空！");
        }
        //符號(hào)表中已經(jīng)存在鍵為key的鍵值對(duì)，只需要找到該結(jié)點(diǎn)替換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++;
    }

    /**
     * 根據(jù)鍵獲取值
     * @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;
        }
    }
}

有序符號(hào)表實(shí)現(xiàn)

上述的符號(hào)表我們稱為無序符號(hào)表，插入的時(shí)候沒有考慮到鍵值對(duì)的順序，而有時(shí)候我們需要根據(jù)鍵的大小進(jìn)行排序，這就需要用到我們的有序符號(hào)表了。

限定K繼承Comparable接口，這樣就可以使用compareTo方法進(jìn)行比較了，我們只需要在原來符號(hào)表的實(shí)現(xiàn)修改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;
    }

    /**
     * 插入鍵值對(duì)
     * @param key
     * @param value
     */
    public void put(K key,V value){
       //定義兩個(gè)變量，記錄當(dāng)前結(jié)點(diǎn)和上一個(gè)結(jié)點(diǎn)
        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相等，則替換對(duì)應(yīng)的值
        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++;
    }

    /**
     * 根據(jù)鍵獲取值
     * @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;
        }
    }
}

現(xiàn)在你會(huì)自己手寫隊(duì)列和符號(hào)表了嗎？

好了，本次內(nèi)容就是這些，學(xué)無止境，關(guān)注我，我們一起學(xué)習(xí)進(jìn)步。如果覺得內(nèi)容還可以，幫忙點(diǎn)個(gè)贊，點(diǎn)個(gè)在看唄，謝謝~我們下期見。