001package algs13; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac ZLinkedStackOfStrings.java 005 * Execution: java ZLinkedStackOfStrings 006 * 007 * A stack of strings, implemented using a linked list. 008 * 009 * % more tobe.txt 010 * to be or not to - be - - that - - - is 011 * 012 * % java ZLinkedStackOfStrings < tobe.txt 013 * to be not that or be 014 * 015 *************************************************************************/ 016 017public class XStackOfStrings { 018 private int N; // size of the stack 019 private Node first; // top of stack 020 021 // helper Node class 022 private static class Node { 023 public Node() { } 024 public String item; 025 public Node next; 026 } 027 028 // is the stack empty? 029 public boolean isEmpty() { return first == null; } 030 031 // number of elements on the stack 032 public int size() { return N; } 033 034 035 // add an element to the stack 036 public void push(String item) { 037 Node oldfirst = first; 038 first = new Node(); 039 first.item = item; 040 first.next = oldfirst; 041 N++; 042 } 043 044 // delete and return the most recently added element 045 public String pop() { 046 if (isEmpty()) throw new Error("Stack underflow"); 047 String item = first.item; // save item to return 048 Node oldfirst = first; 049 first = first.next; // delete first node 050 N--; 051 return item; // return the saved item 052 } 053 054 // test client 055 public static void main(String[] args) { 056// Trace.run (); 057// Trace.drawStepsOfMethod ("push"); 058// Trace.drawStepsOfMethod ("pop"); 059 StdIn.fromString ("to be or not to - be - - that - - - is"); 060 061 XStackOfStrings s = new XStackOfStrings(); 062 while (!StdIn.isEmpty()) { 063 String item = StdIn.readString(); 064 Trace.draw (); 065 if (!item.equals("-")) s.push(item); 066 else if (s.isEmpty()) StdOut.println("BAD INPUT"); 067 else StdOut.print(s.pop() + " "); 068 } 069 } 070 071 072}