CodeSky 代码之空

随手记录自己的学习过程

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

2017-02-03 17:00分类: Java评论: 1

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

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

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

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

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

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

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

Deque 的代码地址

之后的 RandomizedQueue 坑比较多一点:

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

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

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

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

RandomizedQueue 的代码

评论 (1)

quange2022年4月25日 12:00

最近在学java,有帮助