目录

一、队列的定义

二、列表的实现

 三、LeetCode

1、Num225

2、Num225加强版

3、Num232

 四、循环队列

 五、双端队列

 六、相关代码

一、队列的定义

队列是先进先出的数据结构(FIFO)，元素从队尾添加到队列，元素从队首出列（就类似于现实生活中的排队）

 

二、列表的实现

基于数组实现的队列-顺序队列，基于链表实现的队列-链式队列

对于队列来说，出队操作只能在队列的头部操作，如果是基于数组的话，那么每次出队一个元素就要搬移其他元素，就会比较麻烦，而基于链表的队列就不会这么麻烦

package queue.impl;

import queue.Queue;

import java.util.NoSuchElementException;


class Node{
    E val;
    Node next;

    public Node(E val) {
        this.val = val;
    }
}

public class LinkedQueue implements Queue {
    //当前队列的元素个数
    private int size;
    //头节点
    private Node head;
    //队尾元素
    private Node tail;

    
    @Override
    public void offer(E val) {
       Node node=new Node<>(val);
       if (head==null){
           head=tail=node;
       }else {
           tail.next=node;
           tail=node;
       }
       size++;
    }

    
    @Override
    public E poll() {
        if (isEmptty()){
            throw new NoSuchElementException("Queue is Empty!cannot is poll!");
        }
        E val= head.val;
        Node node=head;
        head=head.next;
        node.next=node=null;
        size--;
        return val;
    }

    
    @Override
    public E peek() {
        if (isEmptty()){
            throw new NoSuchElementException("Queue is Empty!cannot is peek!");
        }
        return head.val;
    }

    
    @Override
    public boolean isEmptty() {
        return size==0;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        for (Node x=head;x!=null;x=x.next) {
            sb.append(x.val);
            if (x.next!=null){
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

 三、LeetCode

1、Num225

package queue.Leetcode;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;


public class Num225 {
    // q1永远是保存元素的队列
    private Queue q1 = new LinkedList<>();
    // q2作为辅助队列，新元素直接入q2
    private Queue q2 = new LinkedList<>();
    public void push(int x) {
        // 新元素直接入q2
        q2.offer(x);
        // 将老元素依次出队1，入队2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        // 交换q1和q2的名称
        Queue temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

2、Num225加强版

使用一个队列实现栈

package queue.Leetcode;

import java.util.LinkedList;
import java.util.Queue;


public class Num225Plus {
    private Queue queue=new LinkedList<>();

    public void push(int x) {
         //记录当前队列的元素个数
        int size=queue.size();

        queue.offer(x);

        for (int i = 0; i  
3、Num232 
 
package queue.Leetcode;

import java.util.Stack;

public class Num232 {
    // s1永远是保存元素的栈，就对应队列
    private Stack s1 = new Stack<>();
    // s2作为辅助，s1的栈顶元素就会弹出压入s2的栈底 => 交换顺序
    private Stack s2 = new Stack<>();

    public void push(int x) {
        // 1.先让s1的所有元素弹出压入s2中，交换先后顺序
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        // 2.s1为空，新元素直接入s1，就变为了栈底元素，就是队尾
        s1.push(x);
        // 3.再把s2中的所有元素依次弹回s1
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }

    public int pop() {
        return s1.pop();
    }

    public int peek() {
        return s1.peek();
    }

    public boolean empty() {
        return s1.isEmpty();
    }

}
 
 四、循环队列 
 
 
循环队列基本是使用长度固定的数组来实现，数组在实现队列时，若从数组头部删除元素需要频繁的移动到后面的元素带来的效率很低
 
 
出队和入队操作，使用head和tail引用，添加元素在尾部添加，删除元素就只需要移动head引用指向的地址（逻辑上删除），数组优先元素是[head,tail)
 
 
 
 
package queue.impl;

import queue.Queue;

import java.util.NoSuchElementException;


public class LoopQueue implements Queue {
    //长度固定的数组
    private Integer[] data;
    //队首元素
    private int head;
    //指向队尾元素的下一个索引
    private int tail;

    
    public LoopQueue(int size){
        //因为循环队列需要浪费一个空间来判断队列是否已满
        data=new Integer[size+1];
    }


    @Override
    public void offer(Integer val) {
        if (isFull()){
            throw new ArrayIndexOutOfBoundsException("LoopQueue is full!cannot offer");
        }
        data[tail]=val;
        tail=(tail+1)% data.length;
    }

    @Override
    public Integer poll() {
       if (isEmptty()){
           throw new NoSuchElementException("LoopQueue is empty!cannot poll!");
       }
       //移动队首元素
        Integer val=data[head];
       head=(head+1)% data.length;
       return val;
    }

    @Override
    public Integer peek() {
        if (isEmptty()){
            throw new NoSuchElementException("LoopQueue is empty!cannot peek!");
        }
        return data[head];
    }

    
    @Override
    public boolean isEmptty() {
        return head==tail;
    }

    
    public boolean isFull(){
        return (tail+1)% data.length==head;
    }

    
    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        int lastIndex=tail==0? data.length -1:tail-1;
        for (int i = head; i < tail;) {
            sb.append(data[i]);

            if(i !=lastIndex){
                sb.append("， ");
            }
            i=(i+1)% data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }
}
 
 五、双端队列 
 
 
Deque->时 Queue的子接口
 
 
这个队列既可以尾插，头出
 
 
也可以头插，尾出
 
 
 
 
 
 
在以后的使用中，如果需要栈或者队列，统一使用双端队列，效率高
 
 
 //此时需要的是栈
        Deque stack=new LinkedList<>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);
        System.out.println(stack);
        stack.poll();
        System.out.println(stack);
        //此时需要的是队列
        Deque queue=new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue);
        queue.poll();
        System.out.println(queue);
 
 六、相关代码 
任枭雄/rocket_class_ds - Gitee.comhttps://gitee.com/ren-xiaoxiong/rocket_class_ds/tree/master/src/queue