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

本系列博客习题来自《算法(第四版)》,算是本人的读书笔记,如果有人在读这本书的,欢迎大家多多交流。为了方便讨论,本人新建了一个微信群(算法交流),想要加入的,请添加我的微信号: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](//www.greatytc.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() + "");
            }
        }
    }
}

显示结果:

image.png

代码索引

Stack.java

视频讲解

点此观看分析视频:顶级程序员教你学算法(26)-Stack概念(1.3.1-1.3.2)

广告

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 《忍住了看你,却忍不住想你》 作者 仓央嘉措 格桑花开了,开在对岸 看上去很美。看得见却够不着 够不着也一样的美 ...
    遇巧阅读 393评论 0 3
  • 天凉小酥风 花香意醉迷 恐惊白玉仙 不舍动兰楫
    漠塘阅读 269评论 3 3
  • 盛夏帝都,傍晚,38℃的空气渐渐散去, 日初落,阳台越窗望去天边高级灰的颜色散落着好看的云… 瞬,有人敲门,应声推...
    霂燊阅读 592评论 0 2
  • 有时我在想生活总会在给你关上门的时候还留着第一扇窗只是这扇窗来的时间有先后罢了 我要你任素汐 - 我要你 余书已经...
    Charlet阅读 339评论 0 0