数据结构之队列

目录

一、什么是队列Queue

二、Queue的一些方法

三、什么是双端队列Deque

四、Deque的一些方法

 五、队列Queue的实现

六、循环队列 

一、什么是队列Queue

二、Queue的一些方法

我们通常喜欢用offer()、poll()和peek()这一组。 

三、什么是双端队列Deque

双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队

四、Deque的一些方法

头部 / 尾部	头部元素（队首）		尾部元素（队尾）
错误处理	抛出异常	返回特殊值	抛出异常	返回特殊值
入队列	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
出队列	removeFirst()	pollFirst()	removeLast()	pollLast()
获取元素	getFirst()	peekFirst()	getLast()	peekLast()

注意：Deque这个接口它实现了Queue这个接口，因此也会有Queue的方法(offer()、add()默认从队尾入队,remove()、poll()默认删除队头元素)。

对于LinkedList来说，它不仅可以当做普通队列，可以当做双端队列，可以当做双向链表，也可以当做栈，我们来回忆一下这幅图：

 五、队列Queue的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，所以我们使用单链表来尝试实现它。

那么，如果是用单链表来实现它的话，哪边当队头，哪边当队尾呢？如图所示：

 所以我们在队尾处加上一个last指针指向最后一个结点，那么从队尾尾插法入队，时间复杂度为O(1),出队也是O(1)

 

class Node{
    public int val;
    public Node next;

    public Node(int val){
        this.val = val;
    }
}
public class MyQueue {
    public Node head;
    public Node last;

    public void offer(int val){
        Node node = new Node(val);
        if(this.head == null){
            head = node;
            last = node;
        }else{
            last.next = node;
            last = last.next;
        }
    }
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        int oldValue = head.val;
        this.head = head.next;
        return oldValue;
    }
    public boolean isEmpty(){
        return this.head == null;
    }
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        return head.val;
    }
}
public class TestDemo {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.peek());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

编译并运行该代码，输出如下：

六、循环队列 

 2.数组下标循环的一些方法：

（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

 （2）下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length，如：

 3.如何判断循环队列是否空和满？

（1）使用usedSize      比较usedSize和数组长度，确定是空还是满

（2）使用标志位    flag=false(初始位置标志为false),元素入队列时，每放一个元素就置为true；出队时，每出一个元素就置为false,如图所示：

 （3）保留一个空位置      每次放元素之前都先检查一下rear的下一个是不是front，如果是那么就是满的，如图所示：

 现在我们来看一条题：

代码实现如下：（我们在判断空和满时使用第三种方法）

class MyCircularQueue {

    public int[] elem;
    public int front;
    public int rear;

    public MyCircularQueue(int k) {
        this.elem = new int[k + 1];//由于我们要保留一个空位置，所以我们有3个空间时希望放3个元素时却只能放2个元素，因此我们要让k+1
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }

        this.elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front + 1) % elem.length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index = -1;
        if(rear == 0){
            index = elem.length - 1;
        }else{
            index = rear - 1;
        }
        return elem[index];
    }
    
    public boolean isEmpty() {
       return front == rear;
    }
    
    public boolean isFull() {
        if((rear + 1) % elem.length == front){
            return true;
        }
        return false;
    }
}