队列(Queue)

@TOC

一:什么是队列:

队列是一种在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,进行插入操作的一端称为队尾,进行删除操作的一端称为队头

二:队列的使用:

Queue是一个接口,底层是通过双向链表实现的,在实例化的时候,一般实例化LinkedList对象.

Deque<Integer> deque=new LinkedList<>();

 *//LinkedList,ArrayDeque不仅可以当做队列,也可以当做栈
        Deque<Integer> deque=new LinkedList<>();
        Deque<Integer> deque2=new ArrayDeque<>();*

三:队列的模拟实现:

由于队列的底层是由双向链表实现的,那么其属性与双向链表相似;

 static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
    public int usedSize;

具体要实现的方法:

void offer(int val);//入队
 int poll();//出队
 int peek();//获取队头元素
 int size();//获取队列中有效元素个数
 boolean empty();//判断队列是否为空

1.入队:void offer(int val)

尾插法:通过修改指向将新插入的节点变成最后一个节点,然后让usedSize++即可;
入队一定让usedSize++

 public void offer(int val){
        ListNode node =new ListNode(val );
        if(head==null){
            head=node;
            last=node;

        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }
        usedSize++;

    }

2.出队: int poll()

首先要判断是否为空,如果队列为空,那么抛出自定义异常
由于删除的是头节点,修改头结点的指向即可.但如果只有一个节点,删除后就没有节点了,所以head=null;last=null
出一定让usedSize–;

 public int poll(){
        if(empty()){
            throw new NullException("队列为空");

        }
        int m=head.val;
        usedSize--;
        if(head.next==null){
            head=null;
            last=null;
            return m;
        }

        head=head.next;
        head.prev=null;

        return m;

    }

异常类:

public class NullException extends RuntimeException{
    public NullException() {

    }

    public NullException(String message) {
        super(message);
    }
}

3.获取队头元素:int peek()

首先要判断是否为空,如果队列为空,那么抛出自定义异常
仅仅是获取队头元素,而不是删除,直接返回头节点的数值域即可.

  public int peek(){
            if(empty()){
                throw new NullException("队列为空");

            }

            return head.val;

        }

异常类:

public class NullException extends RuntimeException{
    public NullException() {

    }

    public NullException(String message) {
        super(message);
    }
}

4.获取队列中有效元素个数: int size()

 public int size(){
        return usedSize;
    }

5.判断队列是否为空:boolean empty()

public boolean empty(){
        return head==null;
}

综上:

public class MyLinkQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
    public int usedSize;
    public void offer(int val){
        ListNode node =new ListNode(val );
        if(head==null){
            head=node;
            last=node;

        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }
        usedSize++;

    }
    public int poll(){
        if(empty()){
            throw new NullException("队列为空");

        }
        int m=head.val;
        usedSize--;
        if(head.next==null){
            head=null;
            last=null;
            return m;
        }

        head=head.next;
        head.prev=null;

        return m;

    }
public boolean empty(){
        return head==null;
}

    public int peek(){
            if(empty()){
                throw new NullException("队列为空");
            }
            return head.val;

        }
    public int size(){
        return usedSize;
    }



}