算法练习(26):Stack概念(1.3.1-1.3.2)

2017-10-06 本文已影响344人 kyson老师

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

算法(第4版)

知识点

Stack概念
Stack类设计

题目

1.3.1 为FixedCapacityStackOfStrings添加一个方法isFull()。

1.3.1 Add a method isFull() to FixedCapacityStackOfStrings.

分析

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

答案

public class FixedCapacityStackOfStrings {
    private int N;
    private String[] a;
    public FixedCapacityStackOfStrings(int cap){
        String[] temp = new String[cap];
        a = temp;
    }

    public void push(String item){
        a[N++] = item;
    }

    public int size(){
        return N;
    }

    public String pop(){
        return a[--N];
    }

    public boolean isEmpty(){
        return N ==0;
    }
    //添加的isFull方法，用于判断数组是否已满，之前的实现有点问题，感谢@[wangzhou](https://www.jianshu.com/u/037b7bcf43a7)提出

    public boolean isFull(){
        return N == a.length;
    }

    public static void main(String[] argv){
        FixedCapacityStackOfStrings strs = new FixedCapacityStackOfStrings(100);
        strs.push("My");
        strs.push("name");
        strs.push("is");
        strs.push("顶级程序员不穿女装");
    }
}

代码索引

FixedCapacityStackOfStrings.java

题目

1.3.2 给定以下输入，java Stack的输出是什么？
it was - the best - of times - - - it was - the -

1.3.2 Give the output printed by java Stack for the input
it was - the best - of times - - - it was - the - -

public class Stack<Item> {
    private int N;
    private Node first;
    private class Node{
        Item item;
        Node next;
    }
    public Stack(){
        first = new Node();
    }

    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public boolean isEmpty(){
        //或:first = null
        return N == 0;
    }

    public static void main(String[] args){
        Stack<String> s = new Stack();
        while (!StdIn.isEmpty()){
            String item = StdIn.readString();
            if (!item.equals("-")){
                s.push(item);
            }else if(!s.isEmpty()){
                StdOut.print(s.pop() + "");
            }
        }
    }
}