（JAVA）队列和符号表两种数据结构的实现

1. 队列

1.1 队列的概述

队列是一种基于先进先出（FIFO）的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表。

它按照先进先出的原则存储数据，先进入的数据，在读取时先被读出来

在这里插入图片描述

1.2 队列的API设计

类名	Queue
构造方法	Queue()：创建Queue对象
成员方法	1. public boolean isEmpty()：判断队列是否为空，时返回true，否返回false 2. public int size()：获取队列中元素的个数 3. public T dequeue()：从队列中拿出一个元素 4. public void enqueue(T t)：往队列中插入一个元素
成员变量	1. private Node head：记录首节点 2. private int N：当前栈的元素个数 3. private Node last：记录最后一个节点
成员内部类	private class Node：节点类

1.3 队列的实现

package com.renexdemo.linear;import java.util.Iterator;// 队列
public class Queue<T> implements Iterable<T> {private Node head;private Node last;private int N;// 节点类private static class Node<T>{public T item;// 存储元素public Node next;// 指向下一个节点public Node(T item, Node next) {this.item = item;this.next = next;}}// 初始化构造public Queue() {this.head = new Node(null,null);this.last = null;this.N = 0;}// 判断为空public boolean isEmpty(){return N==0;}// 获得队列的长度public int size(){return N;}// 填入一个元素public void enqueue(T t){// 当前尾结点last为nullif (last == null){last = new Node(t,null);head.next = last;}else{// 当前尾结点last不为nullNode oldLast = last;last = new Node<>(t, null);oldLast.next = last;}// 元素个数+1N++;}// 取出一个元素public T dequeue(){if (isEmpty()){return null;}Node oldFirst = head.next;head.next = oldFirst.next;N--;// 如果队列中没有元素了，那么需要重置last=nullif (isEmpty()){last = null;}return (T) oldFirst.item;}@Overridepublic Iterator<T> iterator() {return new QIterable();}private class  QIterable implements Iterator{private  Node n;public QIterable() {this.n = head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next() {n = n.next;return n.item;}}}

2. 无序符号表

2.1 符号表的概述

符号表最重要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值，说白了，就是以键值对形式存储

在这里插入图片描述

符号表中，键具有唯一性

符号表在实际生活中的使用常见是非常广泛的，见下表：

应用	查找目的	键	值
字典	找出单次的释义	单词	释义
图书索引	找出某个术语相关的页码	术语	一串页码
网络搜索	找出某个关键字对应的网页	关键字	网页名称

2.2 符号表API设计

节点类：

类名	Node<Key,Value>
构造方法	Node(Key key,Value value,Node next)：创建Node对象
成员变量	1. public Key key：存储键 2. public Value value：存储值 3. public Node next：存储下一个节点

符号表：

类名	SymbolTable<Key,Value>
构造方法	SymbolTable()：创建SymbolTable对象
成员方法	1. public Value get(Key key)：根据键key找到对应的值 2. public void put(Key key,Value value)：向符号表中插入一个键值对 3. public void delete(Key key)：删除键为key的键值对 4. public int size()：获取符号表的大小
成员变量	1. private Node head：记录首节点 2. private int N：记录符号表中键值对的个数

3. 有序符号表

当需要实现排序功能时，那么无序符号表将无法实现，这时就需要有序符号表

在这里插入图片描述

3.1 实现代码

package com.renexdemo.symbol;// 有序符号表
public class OrderSymbolTable<Key extends Comparable<Key>,Value> {private Node head;private int N;// 节点类private class Node{public Key key;public Value value;public Node next;public Node(Key key, Value value, Node next) {this.key = key;this.value = value;this.next = next;}}// 初始化类public OrderSymbolTable() {this.head = new Node(null,null,null);this.N = 0;}// 获得当前符号表中元素的个数public int size(){return N;}// 往符号表中添加键值对public void put(Key key,Value value){// 定义两个Node变量，分别记录当前节点和当前节点的上一个节点Node curr = head.next;Node pre = head;while (curr != null && key.compareTo(curr.key)>0){// 变换当前节点和前一个节点即可pre = curr;curr = curr.next;}// 如果当前节点curr的key和要插入的key一样，则替换if (curr != null && key.compareTo(curr.key) ==0){curr.value = value;return;}// 如果不一样，把新节点插入到curr之前Node node = new Node(key, value, curr);pre.next = node;// 元素个数+1N++;}// 删除符号表中键位key的键值对public void delete(Key key){// 找到键位key的节点，把该节点从链表中删除Node n = head;while (n.next != null){// 判断n节点的键是否为key，如果是则替换if (n.next.key.equals(key)){n.next = n.next.next;N--;return;}// 变换nn = n.next;}}// 从符号表中获得键位key的对应值public Value get(Key key){// 找到键位key的节点，把该节点从链表中删除Node n = head;while (n.next != null){// 变换nn = n.next;// 判断n节点的键是否为key，如果是则替换if (n.key.equals(key)){return n.value;}}return null;}
}