双端队列就是队列的头尾两端都能进行插入和删除的队列,而普通的队列只能在头部删除,尾部插入。双端队列的英文名是deque, double-end queue.
实现双端队列最好使用双向链表,因为在双向链表中,链表中每一个节点,都能指向它的前一个节点和后一个节点,只操作一个节点,就能进行插入和删除操作,
因此使用双向链表实现队列时,只要队列中知道头尾两个节点,就可以在队列的两端进行插入和删除操作。
双端队列中,使用双向链表,所以可以声明一个内部类DLNode表示链表中的每一个节点,因为节点中有数据,前一个节点的引用和后一个节点的引用,所以它有三个属性data, next 和previous, 又因为双端队列中要知道链表中头尾两个节点的引用,所以还要声明两个属性firstNode, lastNode.
public class DEuqeu<T> { private class DLNode { T data; DLNode next; DLNode previous; DLNode(T data) { this.data = data; } } private DLNode firstNode; // 指向双向链表的头节点 private DLNode lastNode; // 指向双向 }
向队列(链表)尾部添加元素,就是创建一个新节点,如果链表为空,直接让firstNode和lastNode指向这个新节点,如果链表不为空,lastNode.next指向新节点,新节点的previous 指向lastNode,最后,lastNode指向新节点
public boolean isEmpty() { return firstNode == null; } public void addToBack(T newEntry) { DLNode newNode = new DLNode(newEntry); newNode.previous = lastNode; if (isEmpty()) firstNode = lastNode = newNode ; else { lastNode.next = newNode; lastNode = newNode; } }
向队列(链表)头部插入一个元素,就是创建一个新元素,它的lnext要指向firstNode, firstNode的previous指向新节点,然后firstNode 指向新节点
public void addToFront(T newEntry) { DLNode newNode = new DLNode(newEntry); newNode.next = firstNode; if (isEmpty()) firstNode =lastNode = newNode; else { firstNode.previous =newNode; firstNode = newNode; } }
从队列(链表)头部,删除一个元素,如果链表为空,抛出异常,如果链表不为空,firstNode = firstNode.next; 同时iirstNode 的 previous只为null。如要只有一个元素,删除之后,firstNode 为null,那lastNode也为null。
public T removeFront() { if(isEmpty()) { throw new RuntimeException("队列为空"); } DLNode front = firstNode; firstNode = firstNode.next; if (firstNode == null) lastNode = null; else firstNode.previous = null; return front.data; }
从队列(链表)尾部删除一个元素,就是通过lastNode, 找到它的前一个节点,前一个节点的next 为null,就可以。
public T removeBack() { if(isEmpty()) { throw new RuntimeException("队列为空"); } DLNode last = lastNode; lastNode = lastNode.previous; if (lastNode == null) firstNode = null; else lastNode.next = null; return last.data; }
今天的文章双端队列分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/56461.html