用Java实现双端队列

Question

用Java实现双端队列，并完成以下操作:
1.addFirst(o):将对象o插入到队列的前面
2.addLast(o):将对象o插入到队列的后面
3.removeFirst():返回并删除队列前面的元素，如果deque为空，则抛出EmptyDequeException
4.removeLast():返回并删除队列后面的元素，如果deque为空，则抛出EmptyDequeException

Answer 1

class ListNode {
    //数据域
    public int val;
    //指针
    public ListNode next;
    //初始化值
    public ListNode(int val) {
        this.val = val;
    }
}
 
public class Deque {
    public ListNode head;//头结点
    public ListNode last;//尾节点
 
    public void addFirst(int val) {
        //创建对象初始化值建立新节点
        ListNode node = new ListNode(val);
        //判断尾节点是否为空
        if (this.last == null) {
            //若为空就是头结点尾节点都是这个新创建的节点
            this.head = node;
            this.last = node;
        }
        //node成为新的头节点
        node.next = this.head;
        this.head = node;
    }
    
    public void addLast(int val) {
        //创建对象初始化值建立新节点
        ListNode node = new ListNode(val);
        //判断尾节点是否为空
        if (this.last == null) {
            //若为空就是头结点尾节点都是这个新创建的节点
            this.head = node;
            this.last = node;
        }
        //node成为新的尾节点
        this.last.next = node;
        this.last = node;
    }
 
    //从头结点那边拿出Deque的一个节点
    public int removeFirst() throws Exception {
        //判断头节点是否为空，如果是就输出！
        if (this.head == null) {
            throw new Exception("EmptyDequeException");
        }
        //如果不为空，把头结点指向的值拿出来
        int oldValue = this.head.val;
        //判断头结点尾节点是否重合，如果重合就表明双端队列为空
        if (this.head == this.last) {
            this.head = null;
            this.last = null;
        } else {
            //没有重合就接着找下一个节点变成新的头结点
            this.head = this.head.next;
        }
        return oldValue;
    }
 
    //从尾结点那边拿出Deque的一个节点
    public int removeLast() throws Exception {
        //判断尾节点是否为空，如果就输出！
        if (this.last == null) {
            throw new Exception("EmptyDequeException");
        }
        // //如果不为空，把尾结点指向的值拿出来
        int oldValue = this.last.val;
        //判断头结点尾节点是否重合，如果重合就表明双端队列为空
        if (this.head == this.last) {
            this.last = null;
            this.head = null;
        } else {
            //遍历找到新的尾节点
            ListNode cur = this.head;
            while (cur.next != last) {
                cur = cur.next;
            }
            //把找到的最后一个节点做为尾节点
            this.last = cur;
            //尾节点.next=null
            this.last.next = null;
        }
        return oldValue;
    }
 
    //获取Deque处第一个节点的值
    public int peekFirst() {
        //判断头结点是否为空，是就输出！
        if (this.head == null) {
            System.out.println("!");
            return -1;
        }
        //返回头结点值
        return this.head.val;
    }
 
    //获取Deque上最后一个节点的值
    public int peekLast() {
        //判断尾结点是否为空，是就输出！
        if (this.last == null) {
            System.out.println("!");
            return -1;
        }
        //返回尾结点值
        return this.last.val;
    }
 
    //Check whether the Deque is empty
    public boolean empty() {
        return this.head == null;
    }
 
    public void display(){
        ListNode cur =head;
        while (cur!=last) {
            System.out.print(cur.val);
            cur = cur.next;
        }
        System.out.print(cur.val);
    }
    
    public static void main(String[] args) {
        try {
            Deque deque=new Deque();
            deque.addFirst(1);
            deque.addFirst(2);
            deque.addFirst(3);
            System.out.print("在队列前面插入了数据后的结果：");
            deque.display();
            System.out.println();
            deque.addLast(4);
            deque.addLast(5);
            deque.addLast(6);
            System.out.print("在队列后面插入了数据后的结果：");
            deque.display();
            System.out.println();
            deque.removeFirst();
            System.out.print("在队列前面删除了数据后的结果：");
            deque.display();
            System.out.println();
            deque.removeLast();
            System.out.print("在队列后面删除了数据后的结果：");
            deque.display();
            System.out.println();
        }catch(Exception e) {
            e.printStackTrace();
        }
        
    }
    
}