Stephenson:Neal:The System of the World:333:Off with his head

From the Quicksilver Metaweb.

and in a very short time the Queen was in a furious passion, and went stamping about, and shouting 'Off with his head!' or 'Off with her head!' about once in a minute. Alice in Wonderland, Lewis Carroll

Princess Caroline and Daniel Waterhouse couldn't know this, though, since Lewis Carroll (1832 to 1898) wasn't even born then.