A stack is a dynamic data structure that can store records of data and that supports two primary functions usually called PUSH and POP. The operation PUSH is used to add elements to the stack, while the operation POP removes a prespecified element off the stack. A key property of a stack is that it implements a last in, first out (LIFO) policy; namely the last element pushed onto the stack must be the first element popped off the stack. One should compare this policy to that of another data structure, the queue, which implements a first in, first out (FIFO) policy.

An important way to visualize the operation of a stack is to think of it literally as a stack of cafeteria trays, with each tray corresponding to a record of data. The PUSH operation corresponds to pushing a tray, or new piece of data onto the...