Search code examples
javaindexingstacklifo

indexing confusion Stack LIFO


I've been teaching myself Java with http://www.cs.princeton.edu/courses/archive/spr15/cos126/lectures.html as a reference. I was just going over the topic of Stack and they had the following code as an example

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class StrawStack
{
    private String[] a;
    private int N=0;

    public StrawStack(int max)
    { a = new String[max];}

    public boolean isEmpty()
    { return (N==0);}

    //push a string on top of the stack
    public void push(String item)
    { a[N++] = item;}

    //return the last string added to the top of the stack 
    // this is what gets printed out in the main method
    public String pop()
    { return a[--N];  }

    public int size()
    { return N;} 

    public static void main(String[] args)
    {
     int max = Integer.parseInt(args[0]);
     StrawStack stack = new StrawStack(max);
     while (!StdIn.isEmpty())
     {
      String item = StdIn.readString();
      if (item.equals("-"))
      { StdOut.print(stack.pop() + " ");}
      else
      { stack.push(item);}
     }
    }
    //StdOut.println();   
}

The use to be or not to – be - - that - - - is as an input and then the output is to be not that or be, which makes sense because - makes the code print out the last string. My confusion is how this ends up working out when it has a[--N] in the pop method. I wrote out the to be or not to – part of the input on paper and kept track of indices. I thought it goes like so:

(a[0] stays default a[1] = to a[2]= be a[3]= or a[4]=not a[5]=tountil it runs into -, then it calls upon pop. My confusion is, somehow the code calls upon pop and returns a[5] = to instead of a[4] = not, which i think should be the case. Because right before it runs into -, N = 5 and then after hitting -, N gets assigned 4 if im not mistaken (which i must be)


Solution

  • In this code, N is the index of the next empty space, not the index of the last inserted String in the stack. So when doing a[--N], this indeed decreases N first, but it points then to the last inserted item, "to".

    When encountering the first "-", the stack is as follows:

    a[0] = "to"
    a[1] = "be"
    a[2] = "or"
    a[3] = "not"
    a[4] = "to"
    

    and N is 5.