Advanced topics - stack implementations
Now that we have seen how stacks are used in common practice, lets examine the different types of stack implementation you may encounter. The two most common implementations are the array-based stack and the linked list-based stack. We will examine each of these here.
Array-based stack
An array-based stack utilizes a mutable array to represent the collection. In this implementation, the 0 position in the array represents the bottom of the stack. Therefore, array[0] is the first object pushed onto the stack and the last one popped off. Array-based structures are not practical for a sorted stack as any reorganizing of the structure would require significantly more operational cost than that of a list-based stack. The Tower of Hanoi puzzle is the quintessential example of sorting am array-based stack, with an operational cost of O(2n
), where n is the number of plates on the starting tower. The Tower of Hanoi puzzle will be examined in more detail in Chapter...
