数据结构——队列

目录

 

什么是队列？

如何实现队列?

---

什么是队列？

先进先出，后进后出，这就是典型的“队列”结构

支持两个操作:入队 offer(),放一个数据到队尾；出队 poll(),队首元素出队

所以和栈一样，队列也是一种操作受限的线性表

如何实现队列?

public interface Queue<T> {
    public void offer(T item); //入队
    public T poll(); //出队
    public int size(); //统计元素数量
    public boolean isEmpyt(); //是否为空
    public T peek();//获得队首元素，但不出队列
}

链表实现（链式队列）

public class MyListQueue {
    class Node {
        public int data;
        public Node next;
        public Node(int data) {
            this.data = data;
        }
    }
    public Node front;//队首
    public Node rear;//队尾
    public int usedSize;//统计元素个数

    //入队
    public void offer(int data) {
        Node node = new Node(data);
        //第一次入队
        if (this.usedSize == 0) {
            this.front = node;
            this.rear = node;
        }else {
            this.rear.next = node;
            this.rear = node;
        }
        this.usedSize++;
    }
    //出队
    public int poll() {
        if (this.usedSize == 0) {
            throw new UnsupportedOperationException("队列为空");
        }
        int value = this.front.data;
        this.front = this.front.next;
        this.usedSize--;
        return value;
    }

    public int peek() {
        if (this.usedSize == 0) {
            throw new UnsupportedOperationException("队列为空");
        }
        return this.front.data;
    }
}

循环队列（基于数组）

public class MyCircularQueue {
    public int[] elem;
    public int front;//队首下标
    public int rear;//即将入队的下标
    public int usedSize;//统计元素个数

    //创建一个可以容纳 K 个元素的队列
    public MyCircularQueue(int k) {
        //这里 new 了一个 k+1 的大小的数组   
        this.elem = new int[k+1];
        this.front = 0;
        this.rear = 0;
        this.usedSize = 0;
    }

    //入队
    public boolean offer(int value) {
        if (isFull()) {
            return false;
        }
        this.elem[this.rear] = value;
        this.usedSize++;
        this.rear = (this.rear+1)%this.elem.length;
        return true;
    }

    //出队列
    public boolean poll() {
        if (isEmpty()) {
            return false;
        }
        this.front = (this.front+1)%this.elem.length;
        this.usedSize--;
        return true;
    }

    //获得队首元素
    public int front() {
        if (isEmpty()) {
            return -1;
        }
        return this.elem[this.front];
    }

    //获得队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = this.rear == 0 ? this.elem.length-1 : this.rear-1;
        return this.elem[index];
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return this.front == this.rear;
    }

    //判断队列是否已满
    public boolean isFull() {
        return (this.rear+1)%this.elem.length == this.front;
    }

}

对于基于数组的循环队列来说，我们需要考虑的一个重点是如何判断队列是否已满；如果只是简单的认为，当 front == rear 的时候就判断是空，那当 this.front == this.rear 也可能表示队列是满的，所以我们在创建可以容纳大小为 k 的队列时选择 k+1个大小的数组

• 当 this.front == this.rear 的时候认为是队列是空
• 当 (this.rear+1)%this.elem.length == this.front 判断队列是满的

那么在每一次入队列的时候，就不能够进行++操作了，而是 this.rear = (this.rear+1)%this.elem.legnth；在出队列的时候也需要进行相应的调整，this.front 指向下一个位置即 this.front = (this.front+1)%this.elem.length

获得队尾元素

当待入队位置的索引等于0时，队尾元素的索引为 this.elem.length-1,其他的时候为 this.rear-1