前言：

上一篇我们已经讲了栈，大家一直说栈，队，看来这两个东西是经常一起出现的，那讲了栈，岂有不讲队的道理。

目录

1.队列的概念

2.队列的模拟实现

2.1：队列模拟构造

 2.2：入队列 

2.3:出队列

3.队列的使用

4.循环队列

4.1：代码加注解

 5.编程题

5.1：用队列实现栈

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行数据操作的特殊线性表。队列具有先进先出(First in First out)----跟排队一样，先到先得。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操纵的一端称为对头。

在java中，Queue是一个接口，底层是通过链表实现的。

2.队列的模拟实现

2.1：队列模拟构造

 2.2：入队列 

public  void  offer(int val){
        ListNode node=new ListNode(val);
        if(head==null){//头节点为空的时候，说明此时是空队
            head=node;
            tail=node;
        }else{
            tail.next=node;
            tail=tail.next;
        }
        usedSize++;//有效元素个数加加
    }

2.3:出队列

public int pop(){
        //要先判断队是否为空
        if (isEmpty()){
            throw new QueueEmptyExption("队空,无法删除");
        }//不为空，进行删除
        
        if(head==null){//把尾指针置null
            tail=null;
        }
        int tmp=head.val;
        head=head.next;
        usedSize--;
        return  tmp;

    }
    public boolean isEmpty(){
        return usedSize==0;
    }

3.队列的使用

接下来，我们学一个不一样的东西，叫做循环队列。

4.循环队列

循环队列是一种顺序表示的队列，用数组依次存放从队头到队尾的元素。由于队列中队头和队尾的位置是动态的，就要设front表示队头，rear表示队尾。初始化队列时，front=rear=0。

4.1：代码加注解

public class CircularQueue {
    //循环队列的底层是数组
    int [] elem;
    int front=0;//队头
    int rear=0;//队尾
    //开辟k个空间
    public  void creatQueue(int k){
        this.elem=new int[k];
    }
    //入队列
    public boolean enQueue(int value) {
        //判断循环队列是否满了
        if(isFull()){//满了就扩容
            this.elem= Arrays.copyOf(this.elem,
                    2*this.elem.length);
        }//没满，就入队
        this.elem[rear]=value;
        rear=(rear+1)%elem.length;//这样保证，rear的取值都在
         return true;                         // 0-elem.length-1
    }
    protected boolean isFull(){
        return (rear+1)%elem.length==front;
    }
    //出队列
    public boolean deQueue() {
        //先判断循环队列是否为空
        if(isEmpty()){//空的
            System.out.println("循环队列为空");
            return false;
        }//不为空，出队列
        front=(front+1)%elem.length;//就是front往前走一步
        return true;
    }
   protected boolean isEmpty(){
        return rear==front;//因为初始都是0
   }
   //获取队头元素
    public int getFront(){
        //判断循环队列是否为空
        if (isEmpty()){
            throw new QueueEmptyExption("此循环队列为空,无法偷看");
        }//不为空，查看
        return this.elem[front];
    }
    //获取有效元素个数
    public int size(){
       if(rear-front>0){
           return rear-front;
       }//如果队尾的值小于队头
       return rear-front+elem.length;
    }
    //查看队尾元素
    public  int getRear(){
        if (isEmpty()){
            throw new QueueEmptyExption("此循环队列为空，无法查看");
        }
        int index=rear==0?elem.length-1:rear-1;
        //这是害怕rear到了初始位置0，0-1=-1；就会数组越界。
        return elem[index];
    }
}

 5.编程题

5.1：用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

class MyStack {
      protected Queue<Integer> queue1;
      protected Queue<Integer> queue2;
    public MyStack() {
     queue1=new LinkedList<>();//入队
     queue2=new LinkedList<>();
    }
    public void push(int x) {
        if(empty()) {//这里是queue1和queue2都为空
            queue1.offer(x);//入队queue1
        }else{
            if(!queue1.isEmpty()){
                queue1.offer(x);
            }else{
                queue2.offer(x);
            }
        }
    }
    
    public int pop() {
        if(empty()){//都为空，返回-1
            return -1;
        }else if (!queue1.isEmpty()){
                int len=queue1.size();
                for (int i = 0; i <len-1 ; i++) {
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }else{
            int len=queue2.size();
            for (int i = 0; i <len-1 ; i++) {
                queue1.offer(queue2.poll());
            }
               return queue2.poll();
            }
        }
    public int top() {
        int ret=-1;
        if(empty()){
            return -1;
        }else if(!queue1.isEmpty()){
            int len=queue1.size();
            for (int i = 0; i <len ; i++) {
                ret=queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        }else{
            int len=queue2.size();
            for (int i = 0; i <len ; i++) {
                ret=queue2.poll();
                queue1.offer(ret);
            }
            return ret;
        }

    }
    
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return true;
        }
      return false;
    }
}

总结：

以上就是我总结的队相关的知识点和习题，若有错误，希望各位铁子可以指点一二，若感觉不错，请一键三连，接下来一篇就来到了二叉树