8.1 Introduction

A class declared as a "template" is a class that has a placeholder.  By using specific data types for placeholder,  various concrete classes can be created. In the bag example of the Abstract Data Types chapter, the user can use it only for integers.  To use bag for another data type,  such as character, the program must be re-written for the new data type. This feature is expressed by using “template” keyword in the class definition as follows:

template <class type> class class-name { … }

8.2  Stack Example Part 1: Using an Array

The first example is a stack, yet another simple container ADT. The program shows how to use the stack ADT for implementing a simple calculator.  The idea of this program is drawn  from [Main & Savitch, 1997]. An example dialogue with this simple calculator isas  follows:

Type a parenthesized arithmetic expression: ((2+(3*6))/2)
Value is 10

The implementation of stacks here uses an array for the stack values. In this example, the interface part (visible to users) and the implementation part (hidden from users) are clearly separated.  The programmer needs only to look at the class definition and use public functions to implement the calculator. This separation makes the calculator program used in this example and the next example identical, and demonstrates the strength of the concept of ADT. The template class definition of a stack using an array is as follows:
 

template <class Item> class stack { public:    enum {CAPACITY = 100};    stack() {used = 0;}    void push(Item& value) {       assert(size() < CAPACITY);       data[used] = value;       used++;    }    Item pop() {       assert(!is_empty());       used--;       return data[used];    }    Item peek() {       assert(!is_empty());       return data[used -1];    }    int  size()      {return used;}    bool is_empty()  {return used == 0;} private:    Item data[CAPACITY];    int used; };

The following program uses the above class definition.  In order to implement the calculator shown above example,  two stacks, one for floating point numbers and the other for operator tokens (characters) are created. the two stacks are created from the same class definition through template feature.
 

// ------------ Calculator example ---------------- // The folowing is a simple calculator program to evaluate a fully // parenthesized arithmetic expression. // This example shows a fundamental use of stacks. #include <iostream.h> #include <assert.h> #include <ctype.h> #include <string.h>  void eval_tops(stack<double>& numbers, stack<char>& operators) {    double operand1, operand2;    operand2 = numbers.pop();    operand1 = numbers.pop();    switch (operators.pop()) {       case '+': numbers.push(operand1 + operand2); break;       case '-': numbers.push(operand1 - operand2); break;       case '*': numbers.push(operand1 * operand2); break;       case '/': numbers.push(operand1 / operand2); break;    } } double read_and_eval(istream& ins) {    const char DECIMAL = '.';    const char RIGHT_PAREN = ')';    stack<double> numbers;    stack<char>   operators;    double value;    char symbol;    while (!ins.eof() && ins.peek() != '\n') {       if (isdigit(ins.peek()) || (ins.peek() == DECIMAL)) {          ins >> value;          numbers.push(value);      }       else if (strchr("+-*/", ins.peek()) != NULL) {          ins >> symbol;          operators.push(symbol);        }       else if (ins.peek() == RIGHT_PAREN) {          cin.ignore();          eval_tops(numbers, operators);       }       else          cin.ignore();    }    return numbers.pop(); } main() {    double result;    cout << "Type a parenthesized arithmetic expression: ";    result = read_and_eval(cin);    cout << "Value is " << result << endl; }

8.3 Stack Example Part 2: Using a Linked-list

The second example is another stack implementation. This implementation of stack uses linked list as a base data structure.

The idea of this program is also cited from [Main & Savitch, 1997].  This example demonstrates the strength of the notion of abstract data type.  The main program is  the same as the previous array-based stack example.  As a user of an ADT, one can treat the data type, a stack in this case, as though it is a built-in data type of the language. Even though  the underlying data structure, a doubly linked list, is changed, the main program of the previous example can be used with this class new definition.
 

// ------------ Link-list Implementation---------------- template <class Item>    struct node {       Item data;       node* link;    }; template <class Item> int length(node<Item>* head) {    node<Item>* cursor;    int result;    result = 0;    cursor = head;    while (cursor != NULL) {       cursor = cursor->link;       result++;    }    return result; } template <class Item> void head_insert(node<Item>*& head, const Item& new_item) {    node<Item>* insert;    insert = new node<Item>;    insert->data = new_item;    insert->link = head;    head = insert; } template <class Item> void insert(node<Item>* previous, Item& new_item) {    Node<Item>* insert;    insert = new Node<Item>;    insert->data = new_item;    insert->link = previous->link;    previous->link = insert; } template <class Item> void head_remove(node<Item>*& head) {    node<Item>* target;    target = head;    head = head->link;    delete target; } template <class Item> void remove(node<Item>* previous) {    node<Item>* target;    target = previous->link;    previous->link = target->link;    delete target; } template <class Item> void clear(node<Item>*& head) {    while (head != NULL) head_remove(head); } // ------------ The class stack ---------------- template <class Item> class stack { public:    stack()  {top = NULL;}    ~stack() {clear(top);}    void push(const Item& entry) {       head_insert(top, entry);    }    Item pop() {       Item result;       assert(!is_empty());       result = top->data;       head_remove(top);       return result;    }    int size() {return length(top);}    bool is_empty() {return top == NULL;}    Item peek() {       assert(!is_empty());       return top->data;    } private:    node<Item>* top; };

References

[Ledgard, 1996]
       Henry F. Ledgard. The Little Book of Object-Oriented Programming. Prentice-Hall, 1996.
[Main et al, 1997]
       Michael Main, Walter Savitch. Data Structures and Other Objects using C++. Addison-Wesley Publishing, 1997.
[Stroustrup, 1988]
       Bjarne Stroustrup. What Is Object-Oriented Programming. IEEE Software, May 1988 (1991 revised version, AT&T.)