双端队列

双端队列双端队列就是队列的头尾两端都能进行插入和删除的队列,而普通的队列只能在头部删除,尾部插入。双端队列的英文名是deque, double-end queue. 实现双端队列最好使用双向链表,因为在双向链表中,链表中每一个节点,都能指向它的前一个节点和后一个节点,只操作一个节点,就能进行插入和删除操作,

  双端队列就是队列的头尾两端都能进行插入和删除的队列,而普通的队列只能在头部删除,尾部插入。双端队列的英文名是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

(0)
编程小号编程小号
上一篇 2023-08-26 18:11
下一篇 2023-08-26

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注