数据结构与算法_02_队列

介绍完数组，本文介绍另一个数据结构——队列。

1. 队列理论基础

1.1 队列

数组是一组数据，且可以根据下标来访问元素数据。为了更加严格一点，要求不能根据任意下标来访问数据，只能从数组的“尾端”访问元素，只能从数组的“头部”插入元素。这种新的数据结构就是队列。

简单地说，队列就是“先进先出”，即先进入队列的数据，最先出去。向队列中插入元素，只能从尾部插入（入队）；访问队列中的元素或者删除队列中的元素，只能从头部元素一个个访问，然后删除（出队）。

队列这种数据结构还是比较简单的，提供的方法主要有入队、出队、访问元素（不出队）、获取队列长度（元素个数）等等。

1.2 队列的Java实现

既然队列是在数组的基础上加了限制，那么可以先用数组实现一下队列；另外栈也是可以实现队列的；同时Java中也提供了队列这种数据结构。

1.2.1 数组实现队列

实现代码如下，为了存储多种类型数据，这里采用了Object父类，即多态：

class Queue{
    private Object[] array;
    private int tailIndex;
    private int headIndex;

    public Queue(){}

    public Queue(int num){
        this.array = new Object[num];
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    public void push(Object obj){
        if(this.tailIndex >= this.array.length){
            System.out.println("入队失败，队列已满！");
        }else{
            this.array[this.tailIndex] = obj;
            this.tailIndex++;
        }
    }

    public Object pop(){
        if(this.headIndex >= this.array.length || this.headIndex >= this.tailIndex){
            System.out.println("出队失败，队列已空！");
            return null;
        }else{
            Object obj = this.array[this.headIndex];
            this.headIndex ++;
            int tempLength = this.getCurrentLength();
            
            // 为了保证队列的循环性，所以此处对数组重新赋值。
            for (int i = 0; i < tempLength; i++) {
                this.array[i] = this.array[this.headIndex];
                this.headIndex ++;
            }
            this.headIndex = 0;
            this.tailIndex = tempLength;
            return obj;
        }
    }

    public Object get(){
        if(this.headIndex >= this.array.length || this.headIndex >= this.tailIndex){
            System.out.println("队列已空，没有数据");
            return null;
        }
        return this.array[this.headIndex];
    }

    public int getCurrentLength(){
        return this.tailIndex - this.headIndex;
    }

    // set 和 get 方法就不写了，写了之后感觉封装性不是很好。
}

1.2.2 栈实现队列

除了用数组实现队列之外，用栈也是可以实现队列的。因为队列是先进先出，而栈是后进先出，所以单凭一个栈是无法实现的，这里需要用到两个栈，一个栈用于保存入队数据，另一个栈用于保存出队数据。

即入队的时候，将数据存储在栈A中。当需要出队的时候，将A栈中的数据依次出栈并入栈到另一个栈B中，该栈B的的出栈顺序就是队列的出队顺序。

实现代码如下：

class QueueByStack{
    private Stack<String> stackIn;  // 保存入队信息
    private Stack<String> stackOut; // 保存出队信息

    public QueueByStack(){

        this.stackIn = new Stack<String>();
        this.stackOut = new Stack<String>();
    }

    public void push(String strs){
        this.stackIn.push(strs);
    }

    public String pop(){

        if(this.stackOut.isEmpty()){
            // 如果出队栈空，那么就需要将当前入队栈中的数据全部移动到出队栈中。
            if(!this.stackIn.isEmpty()){
                // 判断入队栈中是否空
                while(!this.stackIn.isEmpty()){
                    this.stackOut.push(this.stackIn.pop());
                }
                return this.stackOut.pop();
            }else{
                System.out.println("出队失败，队列已空！");
                return null;
            }
        }else{
            // 如果出队栈非空，直接出队栈弹栈即可
            return this.stackOut.pop();
        }
    }

    public int size(){
        return this.stackIn.size() + this.stackOut.size();
    }

}

1.2.3 Java提供的队列

Java中提供了队列的接口java.util.Queue，也提供了实现该队列接口的几个类，如java.util.LinkedList。

import java.util.LinkedList;

public class QueueTest02 {

    public static void main(String[] args) {

        Queue<String> queue = new LinkedList<String>();

        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");

        for (String q: queue) {
            System.out.println(q);
        }

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

        System.out.println("poll=" + queue.poll());     // 返回第一个元素，并在队列中删除

        for (String q: queue) {
            System.out.println(q);
        }

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

        System.out.println("element=" + queue.element());       // 返回第一个元素，注意不会删除该元素。

        for (String q: queue) {
            System.out.println(q);
        }

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

        System.out.println("peek=" + queue.peek());     // 返回第一个元素，注意不会删除该元素

        for (String q: queue) {
            System.out.println(q);
        }

        System.out.println(queue.size());
    }
}

2. 队列经典题目

无。

3. 备注

部分参考代码随想录 (programmercarl.com)。