本文实现了基于java链表实现队列。分享给大家供大家参考,具体如下:

1.Queue接口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public interface Queue<E> { //获取队列中元素个数 int getSize(); //队列中元素是否为空 boolean isEmpty(); //入队列 void enqueue(E e); //出队列 public E dequeue(); //获取队首元素 public E getFront(); } |
2.实现类LinkedListQueue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
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.测试函数
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//测试用例 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.结果

0