队列 | 如何使用数组和链表来实现“队列”

田维常

发布于 2020-05-05 22:20:51

1.5K0

发布于 2020-05-05 22:20:51

文章被收录于专栏：Java后端技术栈cwnaitJava后端技术栈cwnait

如何使用数组和链表来实现“队列”

与栈一样，队列（Queue）也是一种数据结构，它包含一系列元素。但是，队列访问元素的顺序不是后进先出（LIFO)，而是先进先出（FIFO）。

实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

数组实现

分析

下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一个位置。

入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear++，出队列的时候只需要执行front++即可。

代码实现

/**
 * 数组实现队列
 *
 * @author tian
 * @date 2020/4/26
 */
public class MyArrayQueueDemo {
    public static void main(String[] args) {
        MyQueueDemo<Integer> myQueueDemo = new MyQueueDemo<>();

        myQueueDemo.enQueue(1);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(2);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(3);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(4);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());

        System.out.println("---------------------------");
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
    }
}

class MyQueueDemo<T> {
    private List<T> arrayList = new ArrayList<>();

    private int front;
    private int rear;

    public MyQueueDemo() {
        this.front = 0;
        this.rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public int size() {
        return rear - front;
    }

    //获取对手元素
    public T getFront() {
        if (isEmpty()) {
            return null;
        }
        return arrayList.get(front);
    }

    //获取队列尾部元素
    public T getBack() {
        if (isEmpty()) {
            return null;
        }
        return arrayList.get(rear - 1);
    }

    //删除队列中头部元素
    public void deQueue() {
        if (rear > front) {
            front++;
        } else {
            System.out.println("队列已经不存在元素了");
        }
    }

    //把新元素添加到队列中（队列尾部）
    public void enQueue(T item) {
        arrayList.add(item);
        rear++;
    }
}

运行结果

OK，自此，使用数组实现队列已经搞定。

问题

出队列后数组前半部分的空间不能够充分地利用，解决这个问题的方法为把数组看成一个环状的空间（循环队列）。当数组最后一个位置被占用后，可以从数组首位置开始循环利用。

链表实现

分析

采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。

在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中（1）和（2）两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要（3）这一步，改变pHead指针使其指向pHead→next，此外也需要考虑结点所占空间释放的问题。

代码实现

/**
 * @author tian
 * @date 2020/4/26
 */
class QueueNode<T> {
    T data;
    QueueNode<T> next;

}

class MyNodeQueue<T> {
    private QueueNode<T> head;
    private QueueNode<T> end;
   //初始化队列
    public MyNodeQueue() {
        end = head = null;
    }

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

    int size() {
        int size = 0;
        QueueNode<T> temp = head;
        while (temp != null) {
            temp = temp.next;
            size++;
        }
        return size;
    }
   //入队
    void enQueue(T t) {
        QueueNode<T> temp = new QueueNode<>();
        temp.data = t;
        temp.next = null;
        if (head == null) {
            head = end = temp;
        } else {
            end.next = temp;
            end = temp;
        }
    }
  //出队
    void deQueue() {
        if (head == null) {
            System.out.println("不存在元素，出队失败");
            return;
        }
        head = head.next;
        if (head == null) {
            end = null;
        }
    }
  //获取队首元素
   T getFront() {
        if (head == null) {
            System.out.println("队列中不存在元素，获取为空");
            return null;
        }
        return head.data;
    }
   //获取队尾元素    T getBack() {        if (end == null) {
            System.out.println("队列中不存在元素，获取失败");
            return null;
        }
        return end.data;
    }
}

public class MyNodeQueueDemo {
    public static void main(String[] args) {
        MyNodeQueue<Integer> queue = new MyNodeQueue<>();
        queue.enQueue(1);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(2);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(3);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(4);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());

        System.out.println("------------------");

        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
    }
}

运行结果

OK，使用链表实现队列到此就搞定。

总结

显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链表尾元素可以非常容易地找到链表的首结点。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

数据结构

本文分享自 Java后端技术栈微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

数据结构

登录后参与评论

0 条评论

热度