Stack using Linked List
A stack, analogous to a stack of cafeteria plates, supports only two operations, push and pop, and a test empty. A stack is sometimes called a LIFO queue, for Last-In First-Out, because the last item pushed is the first item popped.
A linked list is a natural way to implement a stack. cons accomplishes push, and first and rest accomplish pop. Both push and pop are provided as macros in Lisp.
(setq stack (cons item stack)) ; push (setq item (first stack)) ; pop (setq stack (rest stack))
stack = cons(item, stack); // push item = first(stack); // pop stack = rest(stack); (stack == null) // empty?
Both push and pop are O(1) and very fast.
pop of an empty stack is an error; this can cause a null dereference hardware trap or an exception.