算法|Java算法系列3--基于链表自定义队列

1 概述 队列是一种先进先出的数据结构,本文将基于链表实现一种简单的队列,主要功能包括入队,出队。
2 代码实现

package com.niuniu.studyalgorithm; import java.util.Iterator; import java.util.Spliterator; import java.util.function.Consumer; /** * @author 002991 * 基于链表的自定义队列 */ public class ChainQueue implements Iterable { /** * 指向最早添加的节点的链接 */ private Node first; /** * 指向最近添加的节点的链接 */ private Node last; /** * 节点的数量 */ private int size; /** * 判断队列是否为空 * @return */ public boolean isEmpty(){ return first == null; }/** * 获取队列的长度 * @return */ public int size(){ return size; }/** * 向队列中添加元素 * @param item */ public void enqueue(Item item){ Node oldLast = last; last = new Node(); last.item = item; last.next = null; if(isEmpty()){ first = last; }else{ oldLast.next = last; } size++; }/** * 从队列中获取元素 * @return */ public Item dequeue(){ Item item = first.item; first = first.next; if(isEmpty()){ last = null; } size--; return item; }/** * 自定义节点 */ private class Node{ Item item; Node next; }//下面是省略Iterator的实现@Override public Iterator iterator() { return new ListIterator(); }@Override public void forEach(Consumer action) {}@Override public Spliterator spliterator() { return null; }private class ListIterator implements Iterator{ private Node current = first; @Override public boolean hasNext() { return current != null; }@Override public Item next() { Item item = current.item; current = current.next; return item; }@Override public void remove() {}@Override public void forEachRemaining(Consumer action) {} } }

3 总结 【算法|Java算法系列3--基于链表自定义队列】此种队列有以下好处:
(1)所需空间总是和集合大小成正比
(2)操作所需时间总是和集合大小无关

    推荐阅读