算法Sedgewick第四版-第1章基础-008一用数组实现栈(泛型、可变大小)-白红宇

算法Sedgewick第四版-第1章基础-008一用数组实现栈(泛型、可变大小)

阅读量：5282 次

发布时间：2019-06-14

本文共 11035 字，大约阅读时间需要 36 分钟。

1 package algorithms.ADT; 2  3 /****************************************************************************** 4  *  Compilation:  javac FixedCapacityStackOfStrings.java 5  *  Execution:    java FixedCapacityStackOfStrings 6  *  Dependencies: StdIn.java StdOut.java 7  *   8  *  Stack of strings implementation with a fixed-size array. 9  *10  *  % more tobe.txt 11  *  to be or not to - be - - that - - - is 12  * 13  *  % java FixedCapacityStackOfStrings 5 < tobe.txt 14  *  to be not that or be15  *16  *  Remark:  bare-bones implementation. Does not do repeated17  *  doubling or null out empty array entries to avoid loitering.18  *19  ******************************************************************************/20 21 import java.util.Iterator;22 import java.util.NoSuchElementException;23 24 import algorithms.util.StdIn;25 import algorithms.util.StdOut;26 27 public class FixedCapacityStackOfStrings implements Iterable
     
       {28     private String[] a;  // holds the items29     private int N;       // number of items in stack30 31     // create an empty stack with given capacity32     public FixedCapacityStackOfStrings(int capacity) {33         a = new String[capacity];34         N = 0;35     }36 37     public boolean isEmpty()            {  return N == 0;                    }38     public boolean isFull()             {  return N == a.length;             }39     public void push(String item)       {  a[N++] = item;                    }40     public String pop()                 {  return a[--N];                    }41     public String peek()                {  return a[N-1];                    }42     public Iterator
      
        iterator()  { return new ReverseArrayIterator(); }43 44 45     public class ReverseArrayIterator implements Iterator
       
         {46         private int i = N-1;47 48         public boolean hasNext() {49             return i >= 0;50         }51 52         public String next() { 53             if (!hasNext()) throw new NoSuchElementException();54             return a[i--];55         }56 57         public void remove() {58             throw new UnsupportedOperationException();59         }60     }61 62 63     public static void main(String[] args) {64         int max = Integer.parseInt(args[0]);65         FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max);66         while (!StdIn.isEmpty()) {67             String item = StdIn.readString();68             if (!item.equals("-")) stack.push(item); 69             else if (stack.isEmpty())  StdOut.println("BAD INPUT"); 70             else                       StdOut.print(stack.pop() + " ");71         }72         StdOut.println();73 74         // print what's left on the stack75         StdOut.print("Left on stack: ");76         for (String s : stack) {77             StdOut.print(s + " ");78         }79         StdOut.println();80     } 81 }

用泛型的

1 package algorithms.ADT; 2  3 /****************************************************************************** 4  *  Compilation:  javac FixedCapacityStack.java 5  *  Execution:    java FixedCapacityStack 6  *  Dependencies: StdIn.java StdOut.java 7  *   8  *  Generic stack implementation with a fixed-size array. 9  *10  *  % more tobe.txt 11  *  to be or not to - be - - that - - - is 12  * 13  *  % java FixedCapacityStack 5 < tobe.txt 14  *  to be not that or be15  *16  *  Remark:  bare-bones implementation. Does not do repeated17  *  doubling or null out empty array entries to avoid loitering.18  *19  ******************************************************************************/20 21 import java.util.Iterator;22 import java.util.NoSuchElementException;23 24 import algorithms.util.StdIn;25 import algorithms.util.StdOut;26 27 public class FixedCapacityStack
     
       implements Iterable
      
        {28     private Item[] a;    // holds the items29     private int N;       // number of items in stack30 31     // create an empty stack with given capacity32     public FixedCapacityStack(int capacity) {33         a = (Item[]) new Object[capacity];   // no generic array creation34         N = 0;35     }36 37     public boolean isEmpty()          {  return N == 0;                    }38     public void push(Item item)       {  a[N++] = item;                    }39     public Item pop()                 {  return a[--N];                    }40     public Iterator
       
         iterator()  { return new ReverseArrayIterator(); }41 42 43     public class ReverseArrayIterator implements Iterator
        
          {44         private int i = N-1;45 46         public boolean hasNext() {47             return i >= 0;48         }49 50         public Item next() {51             if (!hasNext()) throw new NoSuchElementException();52             return a[i--];53         }54 55         public void remove() {56             throw new UnsupportedOperationException();57         }58     }59 60 61     public static void main(String[] args) {62         int max = Integer.parseInt(args[0]);63         FixedCapacityStack
         
           stack = new FixedCapacityStack
          
           (max);64 while (!StdIn.isEmpty()) {65 String item = StdIn.readString();66 if (!item.equals("-")) stack.push(item); 67 else if (stack.isEmpty()) StdOut.println("BAD INPUT"); 68 else StdOut.print(stack.pop() + " ");69 }70 StdOut.println();71 72 // print what's left on the stack73 StdOut.print("Left on stack: ");74 for (String s : stack) {75 StdOut.print(s + " ");76 }77 StdOut.println();78 } 79 }

可变大小的

1 package algorithms.ADT;  2   3 /******************************************************************************  4  *  Compilation:  javac ResizingArrayStack.java  5  *  Execution:    java ResizingArrayStack < input.txt  6  *  Dependencies: StdIn.java StdOut.java  7  *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt  8  *    9  *  Stack implementation with a resizing array. 10  * 11  *  % more tobe.txt  12  *  to be or not to - be - - that - - - is 13  * 14  *  % java ResizingArrayStack < tobe.txt 15  *  to be not that or be (2 left on stack) 16  * 17  ******************************************************************************/ 18  19 import java.util.Iterator; 20 import java.util.NoSuchElementException; 21  22 import algorithms.util.StdIn; 23 import algorithms.util.StdOut; 24  25 /** 26  *  The ResizingArrayStack class represents a last-in-first-out (LIFO) stack 27  *  of generic items. 28  *  It supports the usual push and pop operations, along with methods 29  *  for peeking at the top item, testing if the stack is empty, and iterating through 30  *  the items in LIFO order. 31  *   32  *  This implementation uses a resizing array, which double the underlying array 33  *  when it is full and halves the underlying array when it is one-quarter full. 34  *  The push and pop operations take constant amortized time. 35  *  The size, peek, and is-empty operations takes 36  *  constant time in the worst case.  37  *  
 38  *  For additional documentation, 39  *  see Section 1.3 of 40  *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. 41  * 42  *  @author Robert Sedgewick 43  *  @author Kevin Wayne 44  */ 45 public class ResizingArrayStack
      
        implements Iterable
       
         { 46     private Item[] a;         // array of items 47     private int N;            // number of elements on stack 48  49  50     /** 51      * Initializes an empty stack. 52      */ 53     public ResizingArrayStack() { 54         a = (Item[]) new Object[2]; 55         N = 0; 56     } 57  58     /** 59      * Is this stack empty? 60      * @return true if this stack is empty; false otherwise 61      */ 62     public boolean isEmpty() { 63         return N == 0; 64     } 65  66     /** 67      * Returns the number of items in the stack. 68      * @return the number of items in the stack 69      */ 70     public int size() { 71         return N; 72     } 73  74  75     // resize the underlying array holding the elements 76     private void resize(int capacity) { 77         assert capacity >= N; 78         Item[] temp = (Item[]) new Object[capacity]; 79         for (int i = 0; i < N; i++) { 80             temp[i] = a[i]; 81         } 82         a = temp; 83     } 84  85     /** 86      * Adds the item to this stack. 87      * @param item the item to add 88      */ 89     public void push(Item item) { 90         if (N == a.length) resize(2*a.length);    // double size of array if necessary 91         a[N++] = item;                            // add item 92     } 93  94     /** 95      * Removes and returns the item most recently added to this stack. 96      * @return the item most recently added 97      * @throws java.util.NoSuchElementException if this stack is empty 98      */ 99     public Item pop() {100         if (isEmpty()) throw new NoSuchElementException("Stack underflow");101         Item item = a[N-1];102         a[N-1] = null;                              // to avoid loitering103         N--;104         // shrink size of array if necessary105         if (N > 0 && N == a.length/4) resize(a.length/2);106         return item;107     }108 109 110     /**111      * Returns (but does not remove) the item most recently added to this stack.112      * @return the item most recently added to this stack113      * @throws java.util.NoSuchElementException if this stack is empty114      */115     public Item peek() {116         if (isEmpty()) throw new NoSuchElementException("Stack underflow");117         return a[N-1];118     }119 120     /**121      * Returns an iterator to this stack that iterates through the items in LIFO order.122      * @return an iterator to this stack that iterates through the items in LIFO order.123      */124     public Iterator
        
          iterator() {125         return new ReverseArrayIterator();126     }127 128     // an iterator, doesn't implement remove() since it's optional129     private class ReverseArrayIterator implements Iterator
         
           {130         private int i;131 132         public ReverseArrayIterator() {133             i = N-1;134         }135 136         public boolean hasNext() {137             return i >= 0;138         }139 140         public void remove() {141             throw new UnsupportedOperationException();142         }143 144         public Item next() {145             if (!hasNext()) throw new NoSuchElementException();146             return a[i--];147         }148     }149 150 151     /**152      * Unit tests the 
          Stack data type.153      */154     public static void main(String[] args) {155         ResizingArrayStack
          
            s = new ResizingArrayStack
           
            ();156 while (!StdIn.isEmpty()) {157 String item = StdIn.readString();158 if (!item.equals("-")) s.push(item);159 else if (!s.isEmpty()) StdOut.print(s.pop() + " ");160 }161 StdOut.println("(" + s.size() + " left on stack)");162 }163 }