A similar type of data structure is used in situations where the last item entered will be the next item served. Consider the example of the previous section, but with another column added to contrast the action of a stack with that of a queue.
Action Resulting Queue Resulting Stack A arrives A A B arrives AB AB C arrives ABC ABC service BC AB D arrives BCD ABD service CD AB
Item A will not be served until it is the only remaining item on the stack.
A last-in-first-out data structure is called a stack.
The classic everyday instance of a stack is the pile of dinner plates in the university cafeteria. Plates are added to the top of the stack, and they are also removed from the top--the opposite end to queue serving. Here, the two basic operations are called Push (add something to the stack) and Pull (take something off the stack).
What follows is the definition of a module designed to stack cardinals:
DEFINITION MODULE anADTStacks; (* a simple semi-generic stack by R. Sutcliffe last modified 1995 05 29 *) FROM ItemADT IMPORT ItemType; TYPE DataType (* local name *) = ItemType; ActionProc = PROCEDURE (DataType); Stack; (* details in implementation *) PROCEDURE Init (VAR s : Stack) ; (* Pre: none Post: Establish an empty stack *) PROCEDURE Destroy (s : Stack); (* Pre: s is a previously established stack. Post: any memory previously allocated to q is now returned. *) PROCEDURE Full (s : Stack) : BOOLEAN; (* Pre: s is a previously established stack. Post: if no more items can be stacked, returns TRUE; otherwise returns FALSE. *) PROCEDURE Empty (s : Stack) : BOOLEAN; (* Pre: s is a previously established stack. Post: if the number of active items in the stack is zero, returns TRUE; otherwise returns FALSE. *) PROCEDURE Push (s : Stack; item : DataType); (* Pre: s is a previously established stack. Post: if the stack is not full the given item is added to the stack; otherwise no action is taken. *) PROCEDURE Pull (s : Stack; VAR item : DataType); (* Pre: s is a previously established stack. Post: if the number of active items in the stack is greater than zero, an item is removed from the stack and returned on a last-in-first-out basis; otherwise no action is taken. *) PROCEDURE Traverse (s : Stack; Proc : ActionProc); (* Pre: s is a previously established stack. Post: The action specified by Proc is taken on each item in the stack from the head to the tail without affecting the stack itself. *) END anADTStacks.
The implementation can be with an array as in the example for TextQueues or it can be as a linked structure in the same manner as that for anADTQueues. In the latter case, the code can be identical, with Push substituted for Enqueue and Pull written like Serve but removing things at the other end. There is no need for a tail pointer, only for a head pointer.