本文作者：程序员飞云

本站地址：https://www.flycode.icu

队列的基本概念

队列的特点是元素的入队出队满足先进先出(FIFO)的特点，即先入对的元素先出队，和栈相反。

队列和栈一样有两种实现方式，数组和链表。

队列分为单端队列和双端队列，

队列的实现

链表实现

  1. 初始化队头和队尾
// 队头
private Node front;
// 队尾
private Node rear;
// 队列大小
private int size;


public LinkQueue() {
    this.front = new Node(0);
    this.rear = new Node(0);
}
  1. 入队操作

直接在原来的队尾上添加新的节点就可以

/**
 * 入队
 *
 * @param data
 */
public void push(int data) {
    Node newNode = new Node(data);
    Node temp = front;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
    rear = newNode;
    size++;
}
  1. 出队操作

既然满足先进先出，那么肯定是头节点出队

image-20240129112646373
image-20240129112646373

/**
 * 出队
 *
 * @return
 */
public int pop() {
    if (front.next == null) {
        return -1;
    }
    Node firstNode = front.next;
    front.next = firstNode.next;
    size--;
    return firstNode.data;
}

完整代码

public class LinkQueue {
    // 队头
    private Node front;
    // 队尾
    private Node rear;
    // 队列大小
    private int size;


    public LinkQueue() {
        this.front = new Node(0);
        this.rear = new Node(0);
    }


    /**
     * 入队
     *
     * @param data
     */
    public void push(int data) {
        Node newNode = new Node(data);
        Node temp = front;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        rear = newNode;
        size++;
    }


    /**
     * 出队
     *
     * @return
     */
    public int pop() {
        if (front.next == null) {
            return -1;
        }
        Node firstNode = front.next;
        front.next = firstNode.next;
        size--;
        return firstNode.data;
    }




    /**
     * 遍历队列
     */
    public void traverse() {
        Node temp = front.next;
        while (temp != null) {
            System.out.print(temp.data + "\t");
            temp = temp.next;
        }
    }
}


class Node {
    int data;
    Node next;


    public Node(int data) {
        this.data = data;
    }
}