# O(1)
push(S,x)

# O(1)
x = pop(S)

# O(n) where n is the size of the stack
pop_all(S) {
   while not empty(S)
     pop(S)
}


# input: L is a list of numbers
f(L) {
   S = NewEmptyStack()
   for each n in L            // executed |L| times
      if n > 0 then
         push(S,n)                // O(1)
      else if n < 0 then
         pop(S)                   // O(1)
      else
         pop_all(S)               // O(|L|)
                                  // because the stack can
                                  // become as large as |L|
}

# overall complexity: O(|L| * |L|) = O(|L|^2)

###### Now let's do amortized complexity ###############

The potential energy of my stack S is defined to be |S|

To each operation I assign an amortized cost s.t.
  1) part of the cost is used to increment the potential
     energy
  2) the cost CAN be negative (in that case I am USING the
     potential energy)
  3) it must be true that the potential energy never becomes
     negative!

push(S,x):  costs 2  (1 to do the work + 1 to increment
                      the potential energy that is the
                      length of the stack)
pop(S):     cost 0   (1 to do the work - 1 because the
                      potential energe is decremented,
                      i.e. the stack becomes shorter)
pop_all(S): cost 0   (n to do the work - n because the
                      stack length is decremented by n)

Is property 3 verified? YES, it is: the length of the stack
can never become negative!

# input: L is a list of numbers
f(L) {
   S = NewEmptyStack()
   for each n in L            // executed |L| times
      if n > 0 then
         push(S,n)                // O(2)
      else if n < 0 then
         pop(S)                   // O(0)
      else
         pop_all(S)               // O(0)
}

# overall complexity: O(|L| * 2) = O(|L|)