Mastering Algorithms with C

Implementation and Analysis of Stacks

The structure Stack is the stack data structure . One way to implement a stack is as a linked list. A simple way to do this is to typedef Stack to List (see Example 6.1). In addition to simplicity, using a typedef has the benefit of making the stack somewhat polymorphic. Informally, polymorphism is a principle normally associated with object-oriented languages that allows an object (a variable) of one type to be used in place of another. This means that because the stack is a linked list, and hence has the same properties as a linked list, we can use linked list operations on it in addition to those of a stack. Thus, the stack can behave like a linked list when we want it to.

As an example, suppose we want to traverse the elements of a stack, perhaps so we can display them or determine whether a specific element resides in the stack. To do this, we get the element at the head of the list using list_head and traverse the list using list_next. Using only stack operations, we would have to pop the elements one at a time, inspect them, and push them onto another stack temporarily. Then, after accessing all of the elements, we would need to rebuild the original stack by popping the elements off the temporary stack and pushing them back onto the original one. This method would be less efficient and undoubtedly would look less than intuitive in a program.

Example 6.1. Header for the Stack Abstract Datatype

/***************************************************************************** ...