A stack, analogous to a stack of cafeteria plates, supports only two operations, push and pop. 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 = new Cons(item, stack); ; push item = first(stack); ; pop stack = rest(stack);
Both push and pop are O(1) and very fast.
pop of an empty stack is an error; this will cause a null dereference hardware trap or an exception.