Java学习手册+面试指南:https://javaxiaobear.cn
队列是一种基于先进先出(FIFO)的数据结构,是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表,它按照先进先出的原则存储数据,先进入的数据,在读取数据时先读被读出来。
1、队列的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:记录最后一个结点 |
public class Queue<T> implements Iterable<T>{
private int size;
private Node head;
private Node last;
public Queue() {
size = 0;
head = new Node(null,null);
last = null;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
/**
* 插入元素到队列
* @param t
*/
public void enqueue(T t){
//如果链尾都为空
if(null == last){
last = new Node(t,null);
head.next = last;
}else {
//如果链尾不为空
Node pre = last;
last = new Node(t, null);
pre.next = last;
}
size++;
}
/**
* 取出元素
* @return
*/
public T dequeue(){
if (isEmpty()){
return null;
}
Node oldHead = head.next;
head.next = oldHead.next;
size--;
if (isEmpty()){
last = null;
}
return oldHead.item;
}
/**
* 节点类
*/
private class Node{
public T item;
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
@Override
public Iterator<T> iterator() {
return new QIterator();
}
public class QIterator implements Iterator<T>{
private Node n = head;
@Override
public boolean hasNext() {
return n.next != null;
}
@Override
public T next() {
Node node = n.next;
n = n.next;
return node.item;
}
}
}