在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为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