( similar to Dynamic Tables in CLR 18.4 )

We'll implement a stack in an array. As the stack gets too big, the array is doubled in size.

Claim
  ( push )  O( 1 )

Idea
Let the elements already inserted pay for the copying :

 

upon inserting	these elements	pay for copying
2	1	1
3	2	1, 2
5	3, 4	1, 2, 3, 4
9	5, 6, 7, 8	1, 2, ... 8

- Each element only pays once.
- Each element pays for copying at most two others.

Each element in the top half of the array ( A[  + 1 ] . . . A[ n ] ) has two credits. Upon copying, the array is full and  elements store 2 credits each, so we use up those 2 *  credits to pay for copying. Upon inserting a new element, we store two credits on it.

( push ) = T( push ) + num_bought - num_used

Suppose we copy n elements.

( push ) = ( n + 1 ) + 2 - ( 2 *  )
= 3

Suppose we copy 0 elements.

( push ) = 1 + 2 - 0
= 3

In a sequence of n pushes, each takes amortized time in O( 1 ).

Alternatively, we could use the Potential Method :

= ( number of elements in the 'top half' of the array ) * 2
= ( t -  - 1 ) * 2

e.g.

Suppose we copy n elements :

  ( 1 + n ) + ( 1 * 2 ) + (  * 2 )

  3

Suppose we copy 0 elements :

  1 + [ ( ( t + 1 ) -  - 1 ) * 2 ] - [ ( t -  ) * 2 ]

  1 + 2

where the 2 represents 

  3

But let's not waste memory. If the stack shrinks dramatically, we should free up some of the unused array space.

Idea
When size shrinks to half the capacity ( i.e. when t drops to  + 1 ), shrink the capacity by half.

Problems

Push n times, where  .

push once	... expands ...	cost O( n )
pop once	... contracts ...	cost O( n )
push once	... expands ...	cost O( n )
pop once	... contracts ...	cost O( n )
etc.

There's no way the amortized cost can be O( 1 ).

Another Idea

When size shrinks to a quarter of the capacity ( i.e. when  ) shrink the array by half. Intuitively, we want many cheap operations before an expensive one.

What pays for the copies?

We can't guarantee credits in A[  + 1 ] . . . A[ n ], since we might not have inserted anything there. On the other hand, we know that, upon contracting, A[  + 1 ] ... A[ n ] used to have elements in them, which were popped.

Idea

Upon popping, leave a credit behind in the now-empty slot of A. When we contract, A[  + 1 ] ... A[  + 1 ] are guaranteed to contain  + 1 credits, which will pay for copying  elements.

Note that A[  + 2 ] ... A[ n ] might have credits, but we can throw those away.

So -

( push ) = T( push ) + num_bought - num_used

suppose we don't contact :

( pop ) = cost to return one + cost to put on A[ t ] - used
= 1 + 1 - 0 = 2

suppose we contact from n to  and copy  elements :

( pop ) =
T( copy  and return one )
+ T( put on A[  + 1 ] )
- ( credits in A[  + 1 ] ... A[  + 1 ] )

= ( 1 +  ) + 1 - (  + 1 )

= 1

  ( pop ) = 1

This doesn't conflict with 'push', so -

( pop )  O( 1 )
( push )  O( 1 )

We can maintain a dynamic stack in amortized constant time per operation!

Note that the potential method is more difficult, since potential depends upon the history ( i.e. the sequence of pushes and pops ).

We could try -

= max( 2( t -  - 1 ),  + 2 - t )

... where the first expression in 'max' is > 0 for expanding, the second is > 0 for contracting ...

- but the credit approach is more intuitive!

Copyright 1998
James Stewart
Dynamic Graphics Project
Department of Computer Science
University of Toronto