implementation of the abstract stack As an example, here is an implementation of the abstract stack above in the C programming language. Imperative-style interface An imperative-style interface might be: typedef struct stack_Rep stack_Rep; // type: stack instance representation (opaque record) typedef stack_Rep* stack_T; // type: handle to a stack instance (opaque pointer) typedef void* stack_Item; // type: value stored in stack instance (arbitrary address) stack_T stack_create(void); // creates a new empty stack instance void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack stack_Item stack_pop(stack_T s); // removes the top item from the stack and returns it bool stack_empty(stack_T s); // checks whether stack is empty This interface could be used in the following manner: #include <stack.h> // includes the stack interface stack_T s = stack_create(); // creates a new empty stack instance int x = 17; stack_push(s, &x); // adds the address of x at the top of the stack void* y = stack_pop(s); // removes the address of x from the stack and returns it if (stack_empty(s)) { } // does something if stack is empty This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether the stack state s continues to exist after a call x ← pop(s). In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and the array size). Functional-style interface Functional-style ADT definitions are more appropriate for functional programming languages, and vice versa. However, one can provide a functional-style interface even in an imperative language like C. For example: typedef struct stack_Rep stack_Rep; // type: stack state representation (opaque record) typedef stack_Rep* stack_T; // type: handle to a stack state (opaque pointer) typedef void* stack_Item; // type: value of a stack state (arbitrary address) stack_T stack_empty(void); // returns the empty stack state stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of