用Java实现双端队列

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

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();
        }
        
    }
    
}

用LinkedList集合来做。
方法：
void addFirst(Object o)：将对象o添加到列表的开头
void addLast(Object o)：将对象o添加到列表的结尾
Object removeFirst()：删除并且返回列表开头的元素
Object removeLast()：删除并且返回列表结尾的元素

import java.util.LinkedList;
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList link=new LinkedList();
        System.out.println("将对象 abc 插入到队列的前面");
        link.addFirst("abc");
        System.out.println("当前队列内容：");
        System.out.println(link);
        System.out.println("将对象 def 插入到队列的后面");
        link.addLast("def");
        System.out.println("当前队列内容：");
        System.out.println(link);

        if (link.isEmpty()){
            throw new EmptyDequeException();
        }
        System.out.println("返回并删除队列前面的元素:"+link.removeFirst());
        if (link.isEmpty()){
            throw new EmptyDequeException();
        }
        System.out.println("返回并删除队列后面的元素:"+link.removeLast());
    }
}

class EmptyDequeException extends RuntimeException{
    public EmptyDequeException(){
        super("队列为空！");
    }
}

/**
 * 双向链表
 *
 * @author 26568
 * @date 2022-09-22 12:01
 */
public class MyLinkedList {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        for (int i = 5; i > 0; i--) {
            myLinkedList.addFirst(i);
        }
        myLinkedList.display();
        for (int i = 8; i < 11; i++) {
            myLinkedList.addLast(i);
        }
        myLinkedList.display();
        for (int i = 0; i < 5; i++) {
            myLinkedList.removeFirst();
            myLinkedList.display();
        }
        for (int i = 0; i < 4; i++) {
            myLinkedList.removeLast();
            myLinkedList.display();
        }
    }

    // 打印双向链表
    public void display() {
        ListNode cur = this.head;
        if (cur == null) {
            System.out.println("双向链表为空");
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

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

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

    public ListNode head;// 头节点
    public ListNode tail;// 尾节点

    // 求链表长度
    private int size() {
        ListNode cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 头插法
    public int addFirst(int val) {
        ListNode node = new ListNode(val);
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
        return 1;
    }

    // 尾插法
    public int addLast(int val) {
        ListNode node = new ListNode(val);
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        return size();
    }

    public void removeFirst() {
        if (size() == 0) {
            throw new EmptyDequeException();
        }
        if (this.head.next != null) {
            this.head.next.prev = null;
            this.head = this.head.next;
        } else {
            this.head = null;
            this.tail = null;
        }
    }

    public void removeLast() {
        if (size() == 0) {
            throw new EmptyDequeException();
        }
        if (this.tail.prev != null) {
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
        } else {
            this.head = null;
            this.tail = null;
        }
    }

}

class EmptyDequeException extends RuntimeException {

}

class EmptyDequeException extends Exception {}

class ListNode {
    public int value;
    public ListNode next;

    public ListNode(int value) {
        this.value = value;
    }
}

public class Deque {
    public ListNode first;
    public ListNode last;

    public void addFirst(int val) {
        ListNode node = new ListNode(val);
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }
        node.next = this.first;
        this.first = node;
    }

    public void addLast(int val) {
        ListNode node = new ListNode(val);
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }
        this.last.next = node;
        this.last = node;
    }

    public int removeFirst() throws EmptyDequeException {
        if (this.first == null) {
            throw new EmptyDequeException();
        }
        int oldValue = this.first.value;
        if (this.first == this.last) {
            this.first = null;
            this.last = null;
        } else {
            this.first = this.first.next;
        }
        return oldValue;
    }

    public int removeLast() throws EmptyDequeException {
        if (this.last == null) {
            throw new EmptyDequeException();
        }
        int oldValue = this.last.value;
        if (this.first == this.last) {
            this.last = null;
            this.first = null;
        } else {
            ListNode cur = this.first;
            while (cur.next != last) {
                cur = cur.next;
            }
            this.last = cur;
            this.last.next = null;
        }
        return oldValue;
    }
}

这是比较基础的数据结构操作题，建议自己操作下，
在操作过程中，如果有遇到问题，我们可以交流交流。
这样对你，对大家都比较合适。

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632