面试官问你：“队列和符号表要怎么实现？”
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;
}
}
}现在你会自己手写队列和符号表了吗？
好了，本次内容就是这些，学无止境，关注我，我们一起学习进步。如果觉得内容还可以，帮忙点个赞，点个在看呗，谢谢~我们下期见。
评论