算法练习(29):Queue概念(1.3.6-1.3.8)

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

算法(第4版)

知识点

• Queue概念
• Queue逆序
• Java 迭代器
• eclipse停止输入快捷键

题目

1.3.6 下面这段代码对队列q进行了什么操作？

---

1.3.6 What does the following code fragment do to the queue q?

Stack<String> stack = new Stack<String>();
while (!q.isEmpty())
    stack.push(q.dequeue());
while (!stack.isEmpty())
    q.enqueue(stack.pop());

答案

逆序

public class Queue<Item> implements Iterable<Item> {

    private int N;

    private class Node {
        Item item;
        Node next;
    }

    private Node first;
    private Node last;

    public Queue() {

    }

    public boolean isEmpty() {
        if (first == null)
            return true;
        return false;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (this.isEmpty()) {
            first = last;
        } else {
            oldLast.next = last;
        }
        N++;
    }

    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (this.isEmpty()) {
            last = null;
        }
        N--;
        return item;
    }

    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new QueueIterator();
    }

    private class QueueIterator implements Iterator<Item> {

        public boolean hasNext() {
            // TODO Auto-generated method stub
            return false;
        }

        public Item next() {
            // TODO Auto-generated method stub
            return null;
        }

        public void remove() {
            // TODO Auto-generated method stub
            
        }       

    }

    public static void main(String[] args) {
        Queue<String> stringQueue = new Queue<String>();
        stringQueue.enqueue("我");
        stringQueue.enqueue("的");
        stringQueue.enqueue("名字");
        stringQueue.enqueue("叫顶级程序员不穿女装");
        stringQueue.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
        
//      System.out.println(stringQueue.dequeue());
//      System.out.println(stringQueue.dequeue());
//      System.out.println(stringQueue.dequeue());
//      System.out.println(stringQueue.dequeue());
//      System.out.println(stringQueue.dequeue());
//      System.out.println(stringQueue.dequeue());
        
        
        Stack<String> stack = new Stack<String>();
        while (!stringQueue.isEmpty())
            stack.push(stringQueue.dequeue());
        while (!stack.isEmpty())
            stringQueue.enqueue(stack.pop());
        
        
        System.out.println(stringQueue.dequeue());
        System.out.println(stringQueue.dequeue());
        System.out.println(stringQueue.dequeue());
        System.out.println(stringQueue.dequeue());
        System.out.println(stringQueue.dequeue());
        
    }

}

代码索引

Queue.java

题目

1.3.7 为Stack添加一个方法peek()，返回栈中最近添加的元素（而不是弹出）。

---

1.3.7 Add a method peek() to Stack that returns the most recently inserted item on the stack (without popping it).

分析

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

答案

将

    public Item top()
    {
        return first.item;
    }

改为

    public Item peek()
    {
        return first.item;
    }

代码索引

题目

1.3.8 给定以下输入，给出DoublingStackOfStrings的数组的内容和大小。
it was - the best - of times - - - it was - the - -

---

1.3.8 Give the contents and size of the array for DoublingStackOfStrings with the input
it was - the best - of times - - - it was - the - -

答案

public class DoublingStackOfStrings<Item> implements Iterable<Item>{
    
    private int N;
    private Item[] items = (Item[])(new Object[1]);
    
    public void push(Item item)
    {
        if (items.length == N) resize(N * 2);
        items[N++] = item;
    }
    
    public Item pop()
    {
        
        Item item = items[--N];
        items[N] = null; 
        if (N > 0 && N == items.length / 4) resize(N * 2);  
        return item;
    }
    
    private void resize(int max)
    {
        Item[] items2 = (Item[])(new Object[max]);
        for (int i = 0; i < N; i++) {
            items2[i] = items[i];
        }
        items = items2;
    }
    
    public int arraySize()
    {
        return items.length;
    }
    
    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new ArrayIterator();
    }
    
    private class ArrayIterator implements Iterator<Item>{
        
        private int i = N;
        public boolean hasNext(){
            return i > 0;
        }
        
        public Item next(){
            return items[--i];
        }

    }   
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        DoublingStackOfStrings<String> stack = new DoublingStackOfStrings<String>();  
        String[] inputs = StdIn.readAllStrings();  
        for (int i = 0; i < inputs.length; i++)  
        {  
            if (inputs[i].equals("-"))  
            {  
                stack.pop();  
            }  
            else  
            {  
                stack.push(inputs[i]);  
            }  
            
        }  
        
        for (String s : stack)  
        {  
            System.out.print(s + " ");  
        }  
        System.out.println();  
        System.out.println("ArraySize: " + stack.arraySize());  
        System.out.println();  
        
    }
}

代码索引

DoublingStackOfStrings.java

视频讲解

点此观看分析视频：顶级程序员教你学算法(29)-Queue概念(1.3.6-1.3.8)

广告

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