Resizable arrays · deamortized: O(1) in the worst case

The doubling trick copies all elements at once, so a single operation can take Θ(n) time. Here, the copying is spread out: besides elements (capacity C) we keep both of its possible successors, elementsBigger (2C) and elementsSmaller (C/2). Every write goes to all three. On a resize the arrays just shift by one row: the array we shift into is already in sync. Only the one newly allocated array is filled in the background — 2 elements per operation, from the top down — and the hatched region shows what is still missing. That is always finished before the new array is needed.

Small screen: the arrays scroll sideways. The code and the analysis are below the drawing.

Detail

Example

Push n, pop n

Leave the field empty for a random key. New operations are added right after the one on screen.

— / — Delay 650ms

The array fitzoom100%

written (to all three arrays) copied by progressCopy deleted not yet copied into the new array

Array accesses per operation

What happens

Popped

Worst-case analysis

Java code

Input

A sequence of stack operations in the format of Sedgewick & Wayne’s tobe.txt: every word is pushed, a - pops. An optional first line init: a b c gives elements that are on the stack at the start; the initial capacity is the smallest power of two ≥ max(8, their number). Keys are up to 4 characters; # starts a comment. The stack holds at most 200 elements here.