9/8/22, 2:19 PM CISC/CMPE 365 - Dynamic Stacks
Dynamic Stacks [ CLRSe3 17.4 ] back to Schedule & Notes
We'll implement a stack in an array. When the stack fills up the
array, the array is expanded to double its size. In the
code
below, A is the array, n is its size, and t is the index of the
next available empty slot in A.
push( x )
if t > n {
B = "allocate array of size 2n"
for i = 1 to n {
B[i] = A[i]
n = 2n
free A
A = B // A points to the B array now
A[t] = x
t = t + 1
Here's what happens when we push 5 elements into a dynamic array
with initial size n = 1 and initial index t = 1:
A push operation can be very expensive because might
require that the whole array be copied, which costs O(n)
for n
elements.
However, we can show that the amortized time of
a push is in O(1).
That means that this is an efficient approach to implementing a
dynamic array.
Amortized Analysis of push
The idea is to offset the cost of copying by having existing
elements that have not yet been copied pay for the
copying from A to B:
Upon inserting these elements pay for copying
2 1 1
3 2 1, 2
5 3, 4 1, 2, 3, 4
[Link]/~jstewart/365/notes/13/[Link] 1/4
9/8/22, 2:19 PM CISC/CMPE 365 - Dynamic Stacks
9 5, 6, 7, 8 1, 2, ..., 8
So each element pays only once (from the middle column
above), and each element pays for copying at most
two others
(since the right column contains at most twice the number of
elements as the middle column).
We'll use the accounting method of amortized analysis because
we are having specific elements pay for
operations.
Just before a copy from A to B, each element in the top
half of the array, A[ n
2
+ 1 … n] , should have
two
credits. That makes a total of n credits in the array.
Upon copying the n elements, A[1 … n], those n
credits will be used.
Suppose k elements are copied during a push.
k could be either zero (if the array is not yet full) or n
(if the array
is full). Then
T̂ (push) = T (push) + (# credits stored) − (# credits used)
k k
= (1 + k) + (2) − (2 ) because elements contribute 2 credits each
2 2
= 3
Therefore, in a sequence of pushes, the
amortized time of each push is in O(1).
The pop Operation
So as not to waste memory, we should shrink the array when it
gets smaller due to repeated pop operations.
Once the array contains one-quarter of its capacity, we'll
reduce it to one-half its current size, as follows:
pop( x )
t = t - 1
x = A[t]
if t <= n/4+1 {
B = "allocate array of size n/2"
for i = 1 to n/4 {
B[i] = A[i]
n = n/2
free A
A = B
return x
Here's what happens with a full array of four elements that
gets a push and then three pops:
[Link]/~jstewart/365/notes/13/[Link] 2/4
9/8/22, 2:19 PM CISC/CMPE 365 - Dynamic Stacks
Exercise
Why not shrink the array to one-quarter its current size once it becomes one-quarter full?
solution
Amortized Analysis of pop
Upon a pop, we will leave behind a credit on the
array slot that contained the popped element.
We cannot guarantee that there are credits on A[ + 1 … n] because there might never have been elements
in
n
those positions. Consider that the array might have been
expanded from size to size n, after which
there were
n
no other push operations. Then the
slots A[ + 2 … n] would never contained
any elements.
n
So we can only guarantee, once the array shrinks
sufficiently, that there were elements in A[ n
4
+ 1…
n
2
+ 1] .
Those array slots each contain a credit, so we have n
4
+ 1 credits to pay for the n
4
elements that get
copied when
the array shrinks.
There might be more than that number of credits, but we don't
need to use the excess credits and can discard
them.
If no shrinking occurs in a pop, its amortized cost is
T̂ (pop) = T (pop) + (# credits bought) − (# credits used)
= 1 + 1 − 0 where one credit is bought and placed on the array slot that contained the p
= 2
If shrinking occurs, its amortized cost is
T̂ (pop) = T (pop) + (# credits bought) − (# credits used)
n n
= (1 + ) + (1) − ( + 1)
4 4
= 1
[Link]/~jstewart/365/notes/13/[Link] 3/4
9/8/22, 2:19 PM CISC/CMPE 365 - Dynamic Stacks
Conclusion
We can maintain a dynamic stack in amortized O(1) cost per operation!
back to Schedule & Notes
[Link]/~jstewart/365/notes/13/[Link] 4/4
