双端队列 Deque 与 随机化队列 RandomizedQueue 的实现

双端队列,也就是栈和队列的结合,同时可以从头和尾进行进出栈 / 队列的功能,看一下他的数据结构就懂了:

public class Deque<Item> implements Iterable<Item> {
   public Deque()                           // construct an empty deque
   public boolean isEmpty()                 // is the deque empty?
   public int size()                        // return the number of items on the deque
   public void addFirst(Item item)          // add the item to the front
   public void addLast(Item item)           // add the item to the end
   public Item removeFirst()                // remove and return the item from the front
   public Item removeLast()                 // remove and return the item from the end
   public Iterator<Item> iterator()         // return an iterator over items in order from front to end
   public static void main(String[] args)   // unit testing (optional)
}

双端队列的实现还是比较简单的(虽然实际上还会是踩了一些微小的坑)。

首先,回忆一下链表和队列的数据结构,有以下几种实现:

  1. 链表实现
  2. 数组实现

链表实现和数组实现的各操作时间复杂度不用赘述,链表对于收尾操作非常轻松,对于随机访问却比较复杂,而数组访问起来简单。

对于这样一个双端队列,我们不需要考虑随机访问的操作,所以选择链表去实现明显是更为合适的。

Deque 的代码地址

之后的 RandomizedQueue 坑比较多一点:

public class RandomizedQueue<Item> implements Iterable<Item> {
   public RandomizedQueue()                 // construct an empty randomized queue
   public boolean isEmpty()                 // is the queue empty?
   public int size()                        // return the number of items on the queue
   public void enqueue(Item item)           // add the item
   public Item dequeue()                    // remove and return a random item
   public Item sample()                     // return (but do not remove) a random item
   public Iterator<Item> iterator()         // return an independent iterator over items in random order
   public static void main(String[] args)   // unit testing (optional)
}

首先我们要考虑到他需要随机删除队列中的一个数,那么删除时肯定会访问到数列中的随机一个数,因此用数组的实现更好。

在这里,我们假定是随机选择出队,所以入队操作是同样顺序的。在出队上,最初我想着 Random 第 n 个元素出队,结果遇到的麻烦是复杂度不是常数时间,而是线性的,所以我们换了一个方法,将 random 到的元素与最后一个元素交换,这样为空的就永远是最后的元素了,不需要使用循环来探测元素。

在迭代器的构件上,为了保证每个迭代器的元素都不同,我们使用了 shuffle 函数来保证独立的乱序,这样在遍历时只要顺序遍历下去就行了。

RandomizedQueue 的代码

如果您觉得文章不错,可以通过赞助支持我

标签: 知识, 算法

添加新评论