算法练习(33): Queue的数组实现(1.3.13-1.3.

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

知识点

• Queue概念
• Queue数组实现

题目

1.3.13 假设某个用例程序会进行一系列入栈和出栈操作。入栈操作会将整数0到9按顺序压入栈；出栈操作会打印返回值。下面哪种顺序是不可能产生的？

1.3.13 Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations. The enqueue operations put the integers 0 through 9 in order ontothe queue; the dequeue operations print out the return value. Which of the following sequence(s) could not occur?

a. 0 1 2 3 4 5 6 7 8 9
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
d. 4 3 2 1 0 5 6 7 8 9

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

b是不能产生的。

题目

1.3.14 编写一个类ResizingArrayQueueOfStrings，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。

1.3.14 Develop a class ResizingArrayQueueOfStrings that implements the queue abstraction with a fixed-size array, and then extend your implementation to use array resizing to remove the size restriction.

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

public class ResizingArrayQueueOfStrings {
    private int N;
    private String[] items;

    public class Node {
        String item;
        Node next;
    }

    public ResizingArrayQueueOfStrings(int cap) {
        items = new String[cap];
    }

    public void enqueue(String item) {
        if (N == items.length) {
            resize(items.length * 2);
        }
        items[N++] = item;
    }

    public String dequeue() {
        // 拷贝所有的老数组元素到新的数组，并命名为oldItems
        String[] oldItems = new String[N];
        for (int i = 0; i < N; i++) {
            oldItems[i] = items[i];
        }

        // 重新设置Stack的大小
        items[--N] = null;
        if (N == items.length / 4) {
            resize(items.length / 2);
        }
        // 获取新数组
        for (int i = 0; i < N; i++) {
            items[i] = oldItems[i + 1];
        }
        return oldItems[0];
    }

    public boolean isEmpty() {
        return true;
    }

    public int size() {
        return N;
    }

    private void resize(int max) {
        String[] tempItems = new String[max];
        for (int i = 0; i < N; i++) {
            tempItems[i] = items[i];
        }
        items = tempItems;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        ResizingArrayQueueOfStrings strings = new ResizingArrayQueueOfStrings(2);
        strings.enqueue("我");
        strings.enqueue("的");
        strings.enqueue("名字");
        strings.enqueue("叫顶级程序员不穿女装");
        strings.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
        
        System.out.println(strings.dequeue());
        System.out.println(strings.dequeue());
        System.out.println(strings.dequeue());
        System.out.println(strings.dequeue());
        System.out.println(strings.dequeue());
//      System.out.println(strings.dequeue());
    }

}

代码索引

ResizingArrayQueueOfStrings.java

视频讲解

顶级程序员教你学算法(33): Queue的数组实现(1.3.13-1.3.14)

广告

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