Ru-Brd |
In contrast to the sample implementations of a stack in previous chapters, you can also implement a stack by using a fixed-size array for the elements. An advantage of this method is that the memory management overhead, whether performed by you or by a standard container, is avoided. However, determining the best size for such a stack can be challenging. The smaller the size you specify, the more likely it is that the stack will get full. The larger the size you specify, the more likely it is that memory will be reserved unnecessarily. A good solution is to let the user of the stack specify the size of the array as the maximum size needed for stack elements. To do this, define the size as a template parameter: // basics/stack4.hpp #include <stdexcept> template <typename T, int MAXSIZE> class Stack { private: T elems[MAXSIZE]; // elements int numElems; // current number of elements public: Stack(); // constructor void push(T const&); // push element void pop(); // pop element T top() const; // return top element bool empty() const { // return whether the stack is empty return numElems == 0; } bool full() const { // return whether the stack is full return numElems == MAXSIZE; } }; // constructor template <typename T, int MAXSIZE> Stack<T,MAXSIZE>::Stack () : numElems(0) // start with no elements { // nothing else to do } template <typename T, int MAXSIZE> void Stack<T,MAXSIZE>::push (T const& elem) { if (numElems == MAXSIZE) { throw std::out_of_range("Stack<>::push(): stack is full"); } elems[numElems] = elem; // append element ++numElems; // increment number of elements } template<typename T, int MAXSIZE> void Stack<T,MAXSIZE>::pop () { if (numElems <= 0) { throw std::out_of_range("Stack<>::pop(): empty stack"); } --numElems; // decrement number of elements } template <typename T, int MAXSIZE> T Stack<T,MAXSIZE>::top () const { if (numElems <= 0) { throw std::out_of_range("Stack<>::top(): empty stack"); } return elems[numElems-1]; // return last element } The new second template parameter, MAXSIZE , is of type int . It specifies the size of the array of stack elements: template <typename T, int MAXSIZE> class Stack { private: T elems[MAXSIZE]; // elements }; In addition, it is used in push() to check whether the stack is full: template <typename T, int MAXSIZE> void Stack<T,MAXSIZE>::push (T const& elem) { if (numElems == MAXSIZE) { throw "Stack<>::push(): stack is full"; } elems[numElems] = elem; // append element ++numElems; // increment number of elements } To use this class template you have to specify both the element type and the maximum size: // basics/stack4test.cpp #include <iostream> #include <string> #include <cstdlib> #include "stack4.hpp" int main() { try { Stack<int,20> int20Stack; // stack of up to 20 int s Stack<int,40> int40Stack; // stack of up to 40 int s Stack<std::string,40> stringStack; // stack of up to 40 strings // manipulate stack of up to 20 int s int20Stack.push(7); std::cout << int20Stack.top() << std::endl; int20Stack.pop(); // manipulate stack of up to 40 strings stringStack.push("hello"); std::cout << stringStack.top() << std::endl; stringStack.pop(); stringStack.pop(); } catch (std::exception const& ex) { std::cerr << "Exception: " << ex.what() << std::endl; return EXIT_FAILURE; // exit program with ERROR status } } Note that each template instantiation is its own type. Thus, int20Stack and int40Stack are two different types, and no implicit or explicit type conversion between them is defined. Thus, one cannot be used instead of the other, and you cannot assign one to the other. Again, default values for the template parameters can be specified: template <typename T = int, int MAXSIZE = 100> class Stack { }; However, from a perspective of good design, this may not be appropriate in this example. Default values should be intuitively correct. But neither type int nor a maximum size of 100 seems intuitive for a general stack type. Thus, it is better when the programmer has to specify both values explicitly so that these two attributes are always documented during a declaration. |
Ru-Brd |