算法练习(42): 随机队列(1.3.35-1.3.36)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 链表节点增删查改
• Fisher–Yates洗牌算法

题目

1.3.35 随机队列。随机队列能够存储一组元素并支持下表中的 API。

API for a generic random queue
编写一个 RandomQueue 类来实现这份 API。编写一个用例，使用 RandomQueue 在桥牌中发牌。

---

1.3.35 Random queue. A random queue stores a collection of items and supports the following API: Write a class RandomQueue that implements this API. Hint : Use an array representation (with resizing). To remove an item, swap one at a random position (indexed 0 through N-1) with the one at the last position (index N-1). Then delete and return the last ob- ject, as in ResizingArrayStack. Write a client that deals bridge hands (13 cards each) using RandomQueue<Card>.

分析

跟随机背包差不多，还是要熟练使用作者提供的StdRandom库

API for our library of static methods for random numbers

答案

public class RandomQueue<Item> implements Iterable<Item> {
    private Item[] a;
    private int N;

    public RandomQueue() {
        a = (Item[]) (new Object[1]);
        N = 0;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item x) {
        if (N == a.length) {
            this.resize(a.length * 2);
        }
        a[N++] = x;
    }

    public Item dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        if (N == a.length / 4) {
            resize(a.length / 2);
        }
        int index = StdRandom.uniform(N);
        Item x = a[index];
        a[index] = a[--N];
        a[N] = null;
        return x;
    }

    public void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    public Item sample() {
        if (this.isEmpty()) {
            return null;
        }
        int index = StdRandom.uniform(N);
        return a[index];
    }

    public Iterator<Item> iterator() {
        return new RandomQueueIterator();
    }
    
    
    public class RandomQueueIterator implements Iterator<Item>{

        private Item[] temp;
        private int index ;
        
        public RandomQueueIterator(){
            temp = (Item[])new Object[N];
            for (int i = 0; i < N; i++)
                temp[i] = a[i];
            
            StdRandom.shuffle(temp);
            index = 0;
        }
        
        public boolean hasNext() {
            return index < N;
        }

        public Item next() {
            return temp[index++];
        }

        public void remove() {
            
        }
        
    }
    
    public static void main(String[] args) {
        RandomQueue<Integer> queue = new RandomQueue<Integer>();
        for (int i = 1; i <= 52; i++)
            queue.enqueue(i);
        
        for (Object object : queue) {
            System.out.println(object);
    }       
}

代码索引

RandomQueue.java

题目

1.3.36 随机迭代器。为上一题中的 RandomQueue<Card> 编写一个迭代器，随机返回队列中的所有元素。

---

1.3.36 Random iterator. Write an iterator for RandomQueue<Item> from the previous exercise that returns the items in random order.

分析

上面一题已经写了答案，这边再贴出来

答案

public class RandomQueueIterator implements Iterator<Item>{
    private Item[] temp;
    private int index ;
    
    public RandomQueueIterator(){
        temp = (Item[])new Object[N];
        for (int i = 0; i < N; i++)
            temp[i] = a[i];
        
        StdRandom.shuffle(temp);
        index = 0;
    }
    
    public boolean hasNext() {
        return index < N;
    }

    public Item next() {
        return temp[index++];
    }

    public void remove() {
        
    }
    
}       

代码索引

RandomQueue.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。