队列之单向链表与双向链表的模拟实现

队列：只允许在一端进行插入的操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则！！

进行插入操作的一端称为对胃！

进行删除操作的一端称为对头！

经过上面的一些讲解，那么我们可以来用单链表来实现一个队列了吧！！

因此，有着一些局限：只能从尾巴插入，头部删除！（找到尾巴节点，头部节点）

有着上述分析，开始用单链表实现链式队列吧！！

单链表实现队列

public class MyQueue {
    //用单链表实现链式队列
    static class Node{
        //单链表
        public int val;
        public Node next;
        
        //构造方法
        public Node(int val){
            this.val=val;
        }
    }
    
    public Node head;//头
    public Node last;//尾
    public int usedSize;
    
    //入队
    public void offer(int val){
        Node node=new Node(val);
        if (head==null){
            head=node;
            last=node;
        }else {
            last.next=node;
            last=node;
        }
        usedSize++;
    }
    
    //出队
    public int poll(){
        if (empty()){//判断是否为空
            throw new EmptyException("队列为空");
        }
        int ret=head.val;//想要出队的值
        head=head.next;//头节点，走一步，删除原来的节点
        if (head==null){
            //只有一个节点
            last=null;
        }
        usedSize--;
        return ret;
    }
    
    //判断是否为空
    public boolean empty(){
        return usedSize==0;
    }
    
    //偷看头节点
    public int peek(){
        if (empty()){
            throw new EmptyException("对列为空");
        }
        return head.val;
    }
    
    public int getUsedSize(){
        return usedSize;
    }
}

抛异常的代码为：

public class EmptyException extends RuntimeException {
    public EmptyException() {
    }
    public EmptyException(String message) {
        super(message);
    }
}

Main方法的代码为：

public class Test {
    public static void main(String[] args) {
        MyQueue myQueue=new MyQueue();
        myQueue.offer(12);
        myQueue.offer(23);
        myQueue.offer(34);
        myQueue.offer(45);
        myQueue.offer(45);
 
        System.out.println(myQueue.peek());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
    }
}

代码的运行结果为：

双向链表实现队列

用双向链表来实现一个栈的前提，是我们需要知道栈的底层是一个双向链表！！

public class Queue {
    //用双向链表实现一个队列
    public static class ListNoode{
        //双向链表的各个节点
        ListNoode next;//下一个
        ListNoode prev;//上一个
        int val;
    }
 
    ListNoode first;//对头
    ListNoode last;//队尾
    int size=0;
 
    //入队列，向双向链表位置插入新的节点
    public void offer(int e){
        ListNoode newNode=new ListNoode();
        if (first==null){
            first=newNode;
            last=newNode;
        }else {
            last.next=newNode;
            newNode.prev=last;
            last=newNode;
        }
        size++;
    }
 
    //出队列，将双向链表的第一个节点删除掉
    public int poll(){
        //1.队列为空
        //2，队列只有一个元素——》链表中只有一个节点——》直接删除
        //3，队列中有多个元素——》链表中有多个节点——》将第一个节点删除
        int value=0;
        if (first==null){
            return null;
        }else if (first==last){
            last=null;
            first=null;
        }else {
            value=first.val;
            first=first.next;
            first.prev.next=null;
            first.prev=null;
        }
        --size;
        return value;
    }
 
    //获取对头元素——》获取链表中第一个节点的值域
    public int peek(){
        if (first==null){
            return null;
        }
        return first.val;
    }
 
    public int size(){
        return size;
    }
 
    public boolean isEmpty(){
        return first==null;
    }
 
}