|< Free Open Study >|
We have defined a stack at the logical level as an abstract data type, discussed its use in an application, and presented an implementation encapsulated in a class. Although our logical picture of a stack is a linear collection of data elements with the newest element (the top) at one end and the oldest element at the other end, the physical representation of the stack class does not have to recreate our mental image. The implementation of the stack class must support the last in, first out (LIFO) property; how this property is supported, however, is another matter. For instance, the push operation could "time stamp" the stack elements and put them into an array in any order. To pop an element, we would have to search the array, looking for the newest time stamp. This representation is very different from the stack implementation we developed in this chapter, but to the user of the stack class they are functionally equivalent. The implementation is transparent to the program that uses the stack, because the stack is encapsulated by the operations in the class that surrounds it.
Rather than requiring the user to provide a file containing information about the size of a structure and the type of the items on the structure, C++ provides a way to supply this information when a structure is declared in a program. Templates are a C++ construct that allows the client to specify the type of the items to be on the structure by including it in angle brackets beside the type name in the declaration statement. Because class constructors can be parameterized, the client can pass the size of the structure by placing it in parentheses beside the variable name in the declaration statement. Additionally, a class constructor can use the new operator to get an array of the proper size in dynamic storage.
In this chapter, we also examined the definition and operations of a queue. We discussed some of the design considerations encountered when we use an array to hold the elements of a queue. Although the array itself is a random-access structure, our logical view of the queue as a structure limits us to accessing only the elements in the front and rear positions of the queue stored in the array.
Usually more than one functionally correct design is available for the same data structure. When multiple correct solutions exist, the requirements and specifications of the problem may determine which solution is the best design.
In the design of data structures and algorithms, you will often find that tradeoffs are necessary. A more complex algorithm may result in more efficient execution; a solution that takes longer to execute may save memory space. As always, we must base our design decisions on what we know about the problem's requirements.
|< Free Open Study >|
|Converted from CHM to HTML with chm2web Pro 2.85 (unicode)|