devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

java数据结构系列，第四篇：双端队列_java 双端队列

作者：繁依Fanyi0 | 2024-02-12 21:54:53

赞

踩

java 双端队列

双端队列（Double-ended queue，简称Deque）是一种数据结构，允许在队列的两端进行插入和删除操作。它可以被看作是一个允许元素插入和删除的线性表，但与普通队列不同，双端队列支持在队列的头部和尾部进行插入和删除操作，因此具有更加灵活的使用方式。

双端队列的特点包括：

  1. 前端插入和删除： 可以在双端队列的前端执行插入和删除操作。这使得双端队列可以像栈一样用于一些问题，比如实现逆序计算或其他需要后进先出（LIFO）操作的场景。

  2. 后端插入和删除： 同样可以在双端队列的后端执行插入和删除操作。这使得双端队列保持了队列的性质，即先进先出（FIFO）。

双端队列常见的操作包括：

  • 在前端插入元素（push_front）：将一个新元素插入到双端队列的头部。
  • 在前端删除元素（pop_front）：删除并返回双端队列的头部元素。
  • 在后端插入元素（push_back）：将一个新元素插入到双端队列的尾部。
  • 在后端删除元素（pop_back）：删除并返回双端队列的尾部元素。
  • 获取前端元素（front）：返回双端队列的头部元素，但不进行删除。
  • 获取后端元素（back）：返回双端队列的尾部元素，但不进行删除。

双端队列在很多算法和数据结构问题中都有广泛的应用，因为它的灵活性使得它可以同时满足栈和队列的需求。在编程中，许多编程语言提供了标准库中的双端队列实现，以方便开发者使用。

下面分别是用链表和数组实现双端队列：

先定义一个接口：
 

  1. public interface Deque<E>
  2. {
  3.     /**
  4.      * 从头部插入
  5.      * @param e 要插入的元素
  6.      * @return 是否插入成功
  7.      */
  8.     boolean offerFirst(E e);
  9.     /**
  10.      * 从尾部插入
  11.      * @param e 要插入的元素
  12.      * @return 是否插入成功
  13.      */
  14.     boolean offerLast(E e);
  15.     /**
  16.      * 从头部删除
  17.      * @return 被删除的元素
  18.      */
  19.     E pollFirst();
  20.     /**
  21.      * 从尾部删除
  22.      * @return 被删除的元素
  23.      */
  24.     E pollLast();
  25.     /**
  26.      * 从头部查看
  27.      * @return 被查看的元素
  28.      */
  29.     E peekFirst();
  30.     /**
  31.      * 从尾部查看
  32.      * @return 被查看的元素
  33.      */
  34.     E peekLast();
  35.     /**
  36.      * 队列是否为空
  37.      * @return 是否为空
  38.      */
  39.     boolean isEmpty();
  40.     /**
  41.      * 队列是否已满
  42.      * @return 是否已满
  43.      */
  44.     boolean isFull();
  45. }

链表实现：

  1.  
  2.  
  3. public class LinkedListDeque<E>  implements Deque<E>, Iterable<E>
  4. {
  5.     /**
  6.      * 双向链表节点类
  7.      * @param <E> 节点存储的元素类型
  8.      */
  9.     static class Node<E>
  10.     {
  11.         Node<E> prev;//前驱，表示当前节点的前一个节点
  12.         E value;//值
  13.         Node<E> next;//后继，当前节点的后一个节点
  14.         Node(final Node<E> prev,final E value,final Node<E> next)
  15.         {
  16.             this.prev = prev;
  17.             this.value = value;
  18.             this.next = next;
  19.         }
  20.     }
  21.     int capacity = Integer.MAX_VALUE;//容量
  22.     int size;//当前元素个数
  23.     Node<E> sentinel = new Node<>(null,null,null);//哨兵节点
  24.  
  25.         /**
  26.          * 构造函数
  27.          * @param capacity 容量
  28.          */
  29.     public LinkedListDeque(final int capacity)
  30.     {
  31.         this.capacity = capacity;
  32.         sentinel.prev = sentinel;
  33.         sentinel.next = sentinel;
  34.     }
  35.     /**
  36.      * 构造函数
  37.      */
  38.     public LinkedListDeque()
  39.     {
  40.         sentinel.prev = sentinel;
  41.         sentinel.next = sentinel;
  42.     }
  43.  
  44.     /**
  45.      * 迭代器
  46.      * @return 迭代器
  47.      */
  48.     @Override
  49.     public Iterator<E> iterator()
  50.     {
  51.         return new Iterator<E>() {
  52.             Node<E> p = sentinel.next;//当前节点
  53.             /**
  54.              * 是否有下一个元素
  55.              * @return 是否有下一个元素，p不等于哨兵节点时有下一个元素
  56.              */
  57.             @Override
  58.             public boolean hasNext()
  59.             {
  60.                 return p != sentinel;
  61.             }
  62.             
  63.             /**
  64.              * 获取当前元素的值，并将p指向下一个元素
  65.              * @return 当前元素的值
  66.              */
  67.  
  68.             @Override
  69.             public E next()
  70.             {
  71.                 E value = p.value;
  72.                 p = p.next;
  73.                 return value;
  74.             }
  75.         };
  76.     }
  77.  
  78.     /**
  79.      * 从头部插入
  80.      * @param e 要插入的元素
  81.      * @return 是否插入成功
  82.      */
  83.     @Override
  84.     public boolean offerFirst(final E e)
  85.     {
  86.         if (isFull())
  87.         {
  88.             return false;
  89.         }
  90.         Node<E> a = sentinel;
  91.         Node<E> b = sentinel.next;
  92.         Node<E> added = new Node<>(a,e,b);
  93.         a.next = added;
  94.         b.prev = added;
  95.         size ++;
  96.         return true;
  97.     }
  98.  
  99.     /**
  100.      * 从尾部插入
  101.      * @param e 要插入的元素
  102.      * @return 是否插入成功
  103.      */
  104.     @Override
  105.     public boolean offerLast(final E e)
  106.     {
  107.         if (isFull())
  108.         {
  109.             return false;
  110.         }
  111.         Node<E> a = sentinel.prev;
  112.         Node<E> b = sentinel;
  113.         Node<E> added = new Node<>(a,e,b);
  114.         a.next = added;
  115.         b.prev = added;
  116.         size ++;
  117.         return true;
  118.     }
  119.  
  120.     /**
  121.      * 从头部删除
  122.      * @return 被删除的元素
  123.      */
  124.     @Override
  125.     public E pollFirst()
  126.     {
  127.         if (isEmpty())
  128.         {
  129.             return null;
  130.         }
  131.         Node<E> a = sentinel;
  132.         Node<E> removed = sentinel.next;
  133.         Node<E> b = removed.next;
  134.         a.next = b;
  135.         b.prev = a;
  136.         size --;
  137.         return removed.value;
  138.     }
  139.  
  140.     /**
  141.      * 从尾部删除
  142.      * @return 被删除的元素
  143.      */
  144.     @Override
  145.     public E pollLast()
  146.     {
  147.         if (isEmpty())
  148.         {
  149.             return null;
  150.         }
  151.         Node<E> removed = sentinel.prev;
  152.         Node<E> a = removed.prev;
  153.         Node<E> b = sentinel;
  154.         a.next = b;
  155.         b.prev = a;
  156.         size --;
  157.         return removed.value;
  158.     }
  159.  
  160.     /**
  161.      * 从头部查看
  162.      * @return 被查看的元素
  163.      */
  164.     @Override
  165.     public E peekFirst()
  166.     {
  167.         if (isEmpty())
  168.         {
  169.             return null;
  170.         }
  171.         return sentinel.next.value;
  172.     }
  173.  
  174.     /**
  175.      * 从尾部查看
  176.      * @return 被查看的元素
  177.      */
  178.     @Override
  179.     public E peekLast()
  180.     {
  181.         if (isEmpty())
  182.         {
  183.             return null;
  184.         }
  185.         return sentinel.prev.value;
  186.     }
  187.  
  188.     /**
  189.      * 队列是否为空
  190.      * @return 是否为空
  191.      */
  192.     @Override
  193.     public boolean isEmpty()
  194.     {
  195.         return size == 0;
  196.     }
  197.  
  198.     /**
  199.      * 队列是否已满
  200.      * @return 是否已满
  201.      */
  202.     @Override
  203.     public boolean isFull()
  204.     {
  205.         return size == capacity;
  206.     }
  207.     
  208.     
  209.     /**
  210.      * 重写toString方法
  211.      */
  212.  
  213.     @Override
  214.     public String toString()
  215.     {
  216.         StringBuilder sb = new StringBuilder();
  217.         sb.append("[");
  218.         int i = 0;
  219.         for (E e : this)
  220.         {
  221.             i ++;
  222.             if (i == size)
  223.             {
  224.                 sb.append(e);
  225.             }
  226.             else
  227.             {
  228.                 sb.append(e);
  229.                 sb.append(",");
  230.             }
  231.         }
  232.         sb.append("]");
  233.         return sb.toString();
  234.     }
  235. }

数组实现：
 

  1.  
  2.  
  3. public class ArrayDeque1<E> implements Iterable<E>, Deque<E>
  4. {
  5.     /**
  6.      * 用于给数组下标加1，如果到达数组末尾则返回0
  7.      * @param i 当前下标
  8.      * @param length 数组长度
  9.      * return i+1    下标加1
  10.      */
  11.     static int inc(int i,int length)
  12.     {
  13.         if (i + 1 >= length)
  14.         {
  15.             return 0;
  16.         }
  17.         return i + 1;
  18.     }
  19.     
  20.     /**
  21.      * 用于给数组下标减1，如果到达数组头部则返回数组末尾下标
  22.      * @param i 当前下标
  23.      * @param length 数组长度
  24.      * return i-1    下标减1
  25.      */
  26.     static int dec(int i,int length)
  27.     {
  28.         if (i - 1 < 0)
  29.         {
  30.             return length - 1;
  31.         }
  32.         return i - 1;
  33.     }
  34.  
  35.     E[] array;//数组
  36.     int head;//头指针，代表该队列的第一个元素
  37.     int tail;//尾指针，始终置空，不存储元素，只是用来标记下一次尾部插入时，元素插入的位置
  38.  
  39.     /**
  40.      * 构造函数
  41.      * @param capacity 容量
  42.      */
  43.     public ArrayDeque1(int capacity)
  44.     {
  45.         array = (E[]) new Object[capacity + 1];
  46.     }
  47.     
  48.     /**
  49.      * 实现迭代器
  50.      */
  51.     @Override
  52.     public Iterator<E> iterator()
  53.     {
  54.         return new Iterator<E>() {
  55.             int p = head;//当前指针
  56.             /**
  57.              * 是否有下一个元素
  58.              * @return 是否有下一个元素，p不等于尾指针时有下一个元素
  59.              */
  60.             @Override
  61.             public boolean hasNext() {
  62.                 return p != tail;
  63.             }
  64.  
  65.             /**
  66.              * 获取当前元素的值，并将p指向下一个元素
  67.              * @return 当前元素的值
  68.              */
  69.             @Override
  70.             public E next() {
  71.                 E value = array[p];
  72.                 p = inc(p,array.length);
  73.                 return value;
  74.             }
  75.         };
  76.     }
  77.  
  78.     /**
  79.      * 从头部插入
  80.      * @param e 要插入的元素
  81.      * @return 是否插入成功
  82.      */
  83.     @Override
  84.     public boolean offerFirst(E e)
  85.     {
  86.         if (isFull())
  87.         {
  88.             return false;
  89.         }
  90.         head = dec(head,array.length);//头指针向前一步
  91.         array[head] = e;//在当前头指针处插入元素
  92.         return true;
  93.     }
  94.  
  95.     /**
  96.      * 从尾部插入
  97.      * @param e 要插入的元素
  98.      * @return 是否插入成功
  99.      */
  100.     @Override
  101.     public boolean offerLast(E e)
  102.     {
  103.         if (isFull())
  104.         {
  105.             return false;
  106.         }
  107.         array[tail] = e;//在当前尾指针处插入元素
  108.         tail = inc(tail,array.length);//尾指针向后一步
  109.         return true;
  110.     }
  111.  
  112.     /**
  113.      * 从头部删除
  114.      * @return 被删除的元素
  115.      */
  116.     @Override
  117.     public E pollFirst()
  118.     {
  119.         if (isEmpty())
  120.         {
  121.             return null;
  122.         }
  123.         E e = array[head];
  124.         array[head] = null;//清理内存，help GC
  125.         head = inc(head,array.length);
  126.         return e;
  127.     }
  128.  
  129.     @Override
  130.     public E pollLast()
  131.     {
  132.         if (isEmpty())
  133.         {
  134.             return null;
  135.         }
  136.         tail = dec(tail,array.length);
  137.         E e = array[tail];
  138.         array[tail] = null;//help GC
  139.         return e;
  140.     }
  141.  
  142.     /**
  143.      * 从头部查看
  144.      * @return 被查看的元素
  145.      */
  146.     @Override
  147.     public E peekFirst()
  148.     {
  149.         if (isEmpty())
  150.         {
  151.             return null;
  152.         }
  153.         return array[head];
  154.     }
  155.  
  156.     /**
  157.      * 从尾部查看
  158.      * @return 被查看的元素
  159.      */
  160.     @Override
  161.     public E peekLast()
  162.     {
  163.         if (isEmpty())
  164.         {
  165.             return null;
  166.         }
  167.         return array[dec(tail,array.length)];
  168.     }
  169.  
  170.     /**
  171.      * 队列是否为空
  172.      * @return 是否为空
  173.      */
  174.     @Override
  175.     public boolean isEmpty()
  176.     {
  177.         return head == tail;
  178.     }
  179.  
  180.     /**
  181.      * 队列是否已满，两种情况：
  182.      * 1.如果尾指针在头指针后面，则当尾指针减头指针等于数组长度减1时，队列已满
  183.      * 2.如果尾指针在头指针前面，则当头指针减尾指针等于1时，也就是头指针紧挨着尾指针，队列已满
  184.      * @return 是否已满
  185.      */
  186.     @Override
  187.     public boolean isFull()
  188.     {
  189.         if (tail > head)
  190.         {
  191.             return tail - head == array.length - 1;
  192.         }
  193.         else if (tail < head)
  194.         {
  195.             return head - tail == 1;
  196.         }
  197.         else
  198.         {
  199.             return  false;
  200.         }
  201.     }
  202. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/78797
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号