万字长文带你漫游数据结构世界（五）队列

企业微信服务商
腾讯云授权服务中心

万字长文带你漫游数据结构世界（五）队列

发布日：2022-01-19 12:58 阅读数：

既然前面有先进后出的数据结构，那我们必定也有先进先出的数据结构，疫情的时候，排队估计大家都有测过核酸，那排队老长了，排在前面先测，排在后面后测，这道理大家都懂。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的特点是先进先出，以下是例子：

一般只要说到先进先出（FIFO）,全称First In First Out,就会想到队列，但是如果你想拥有队列即可以从队头取出元素，又可以从队尾取出元素，那就需要用到特殊的队列（双向队列），双向队列一般使用双向链表实现会简单一点。

下面我们用Java实现简单的单向队列：

class Node<T> {
    public T data;
    public Node next;

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

public class MyQueue<T> {
    private Node<T>  head;
    private Node<T>  rear;
    private int size;

    public MyQueue() {
        size = 0;
    }

    public void pushBack(T element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            head = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public T popFront() {
        if (isEmpty()) {
            throw new NullPointerException("队列没有数据");
        } else {
            Node<T> node = head;
            head = head.next;
            size--;
            return node.data;
        }
    }

    public void dispaly() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data +" -> ");
            temp = temp.next;
        }
        System.out.println("");
    }
}

测试代码如下：

public class MyStackTest {
    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.display();

        System.out.println(myStack.pop());

        myStack.display();

    }
}