在开始栈的实现之前, 我们再来看看关于链表的只在头部进行的增加, 删除, 查找操作, 时间复杂度均为 O(1).
一, 链表改进分析
对于队列这种数据结构, 需要在线性结构的一端插入元素, 另外一端删除元素. 因此此时基于链表来实现队列, 则有一端的时间复杂度为 O(n). 因此我们不能使用之前已经实现的链表结构, 我们需要改进我们的链表. 思路如下:
1. 参考在链表头部删除, 增加元素的时间复杂度为 O(1) 的思路, 我们在链表的尾部设立一个 Node 型的变量 tail 来记录链表的尾部在哪, 此时再 head 端和 tail 端添加元素都是及其简单的, 在 head 端删除元素也是及其简单的, 但对于在 tail 端删除元素时, 是无法在时间复杂度为 O(1) 的情况进行的, 也就是从 tail 端删除元素时不容易的.
2. 只在头部 head 删除元素 (队首), 在尾部 tail 端添加元素 (队尾).
3. 由于在基于链表实现队列时不涉及到操作链表中间元素, 此时我们改进的链表中, 不在使用虚拟头节, 因此也就可能造成在没有虚拟头节点的情况下, 链表为空.
二, 链表改进代码
前言, 在写本小节之前, 我们已经实现了一个基于静态数组的队列, 转到查看. 此处我们实现基于链表的队列.
在实现基于静态数组的队列的时候, 我们已经新建了一个 package, 此时我们在该 package 下新建一个 LinkedListQueue 类, 用来实现 Queue 接口, 目录结构为:
1.Queue 接口代码
- package Queue;
- public interface Queue<E> {
- // 获取队列中元素个数
- int getSize();
- // 队列中元素是否为空
- boolean isEmpty();
- // 入队列
- void enqueue(E e);
- // 出队列
- public E dequeue();
- // 获取队首元素
- public E getFront();
- }
2.LinkedListQueue 类
- package Queue;
- public class LinkedListQueue<E> implements Queue<E> {
- // 将 Node 节点设计成私有的类中类
- private class Node<E> {
- public E e;
- public Node next;
- // 两个参数的构造函数
- public Node(E e, Node next) {
- this.e = e;
- this.next = next;
- }
- // 一个参数的构造函数
- public Node(E e) {
- this.e = e;
- this.next = null;
- }
- // 无参构造函数
- public Node() {
- this(null, null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node<E> head, tail;
- private int size;
- // 显示初始化
- public LinkedListQueue() {
- head = null;
- tail = null;
- size = 0;
- }
- // 获取队列中节点个数
- @Override
- public int getSize() {
- return size;
- }
- // 队列中是否为空
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- // 链表尾部进队操作
- @Override
- public void enqueue(E e) {
- if (tail == null) {
- tail = new Node(e);
- head = tail;
- } else {
- tail.next = new Node(e);
- tail = tail.next;
- }
- size++;
- }
- // 链表头部出队操作
- @Override
- public E dequeue() {
- if (isEmpty()) {
- throw new IllegalArgumentException("链表为空");
- }
- Node<E> retNode = head;
- head = head.next;
- retNode.next = null;
- if (head == null) {// 当链表只有一个元素时
- tail = null;
- }
- size--;
- return retNode.e;
- }
- // 获取队首元素
- @Override
- public E getFront() {
- if (isEmpty()) {
- throw new IllegalArgumentException("链表为空");
- }
- return head.e;
- }
- // 为了便于测试, 重写 object 类 toString() 方法
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- res.append("Queue: front");
- Node<E> cur = head;
- while (cur != null) {
- res.append(cur + "->");
- cur = cur.next;
- }
- res.append("NULL tail");
- return res.toString();
- }
- }
3. 为了便于测试, 在 LinkedListQueue 类中添加一个 main 函数
- // 测试用例
- public static void main(String[] args) {
- LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
- for (int i = 0; i < 10; i++) {
- queue.enqueue(i);
- System.out.println(queue);
- if (i % 3 == 2) {// 每添加 3 个元素出队列一个
- queue.dequeue();
- System.out.println(queue);
- }
- }
- }
4. 结果为
结果分析: 每进队 3 个元素出队列一个.
关于本小节, 若您觉得还行, 还过得去, 记得给个推荐哦~, 谢谢!!
本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java
来源: https://www.cnblogs.com/wfaceboss/p/10646770.html