Java双向链表实现队列

将双向链表做简单的改造，即可实现一个FIFO(First Input First Out)队列,

该队列只在头节点出队，尾节点入队。

一般来说定义节点类只需一个后驱节点next即可。

这里保留pre节点，模拟一个已经入队的节点，如果需要取消，这样pre节点就是一个优势。

定义节点类：

/**

 * 队列元素

 */

public class Node

{

    private int data;//数据域

    private Node pre;//指向上一个节点

    private Node next;//指向下一个节点

    public int getData() {

        return data;

    }

    public void setData(int data) {

        this.data = data;

    }

    public Node getPre() {

        return pre;

    }

    public void setPre(Node pre) {

        this.pre = pre;

    }

    public Node getNext() {

        return next;

    }

    public void setNext(Node next) {

        this.next = next;

    }

    //构造函数

    public Node(int data, Node pre, Node next){

        this.data = data;

        this.pre = pre;

        this.next = next;

    }

    public Node(int data){

        this(data,null,null);

    }

    public Node(){

        this(0,null,null);

    }

}

队列实现：

 1 /**

 2  * Java双向链表实现队列（FIFO）

 3  * Author：hangwei

 4  * 2022/11

 5  */

 6 public class DQueue {

 7     private Node head;

 8     private Node tail;

 9     private int size;

10     public Node getHead() {

11         return head;

12     }

13     public Node getTail() {

14         return tail;

15     }

16     public DQueue(){

17         tail = head = null;

18         size = 0;

19     }

20

21     //尾部入队

22     public void add(Node target){

23         if(target == null)

24             return;

25         if (size == 0) {

26             target.setPre(target);

27             target.setNext(target);

28             tail = head = target;

29         } else{

30             tail.setNext(target);//尾节点的下一个节点是新节点

31             target.setPre(tail);//新节点的上一个节点是尾节点

32             //标记新的尾节点

33             tail = target;

34         }

35         size++;

36     }

37

38     //头节点出队or取消某个已入队节点

39     public void romove(Node target){

40         if(size == 0){

41             System.out.println("null linked list ,can not delete.");

42             return;

43         }

44         else if(size == 1){

45             head = tail = null;

46         }

47         else if(target == null || target.equals(head)) {//target为空或头节点，则头出队

48             head = head.getNext();

49             head.setPre(null);

50         }

51         else {//移除队列中指定的元素

52             target.getPre().setNext(target.getNext());

53             target.getNext().setPre(target.getPre());

54             if(target.equals(tail))//如果出队是尾节点

55                 tail=target.getPre();//标记新的尾节点

56         }

57         size--;

58     }

59

60     //打印队列

61     public void print(){

62         Node node = new Node();

63         node = head;

64         while (node.getNext() != head && node.getNext() != null){//遍历

65             System.out.print(node.getData());

66             System.out.print("<->");

67             node = node.getNext();

68         }

69         System.out.print(node.getData());//补充打印循环体的最后一个节点

70         System.out.println();

71     }

72 }

测试：

public class Main {

    public static void main(String[] args) {

        DQueue dq = new DQueue();

        dq.add(new Node(111));

        dq.add(new Node(222));

        dq.add(new Node(333));

        dq.add(new Node(444));

        dq.add(new Node(555));

        dq.print();

        dq.romove(null);

        dq.print();

        dq.romove(dq.getHead().getNext());

        dq.print();

    }

}

执行结果：

*重点：使用双指针链表实现队列，可以很方便的移除队列中某个不需要的元素。

Java双向链表实现队列的相关教程结束。