It would be nice if we could create a generic version of intStack; i.e., a stack capable of accepting data of arbitrary type. This suggests something similar to the templating of functions with which we are already familiar.
//Header File: stack.h
#ifndef STACK_H
#define STACK_H
// INTERFACE
template <class T> class stack
{
private:
int top;
T s[100];
public:
stack ();
void push(const T);
T pop();
bool empty() const;
bool full() const;
};
#endif
template <class T>
//Implementation is not obvious
stack<T>::stack()
{
top=-1;
}
template <class T>
void stack<T>::push(const T item)
{
top++;
s[top] = item;
}
template <class T>
T stack<T>::pop()
{
return (s[top--]);
}
template <class T>
bool stack<T>::empty() const
{
return (top==-1);
}
template <class T>
bool stack<T>::full() const
{
return (top==99);
}
The following driver program
//File: stackDriver.cpp
#include <iostream>
#include "stack.h"
using namespace std;
int main()
{
stack<int> s;
s.push(25);
s.push(12);
cout << s.pop() << endl;
s.push(34);
s.push(45);
cout << s.pop() << endl;
cout << s.pop() << endl;
return 0;
}
gives results identical to those obtained in lab exercise from last week
Lab Exercise. Try the driver program with stacks of doubles, stacks of strings, etc.
You may recall from your introduction to data structures course that arrays (random access) are ideal for list applications that do not require both the ability to add and delete members of the list AND maintain sorted order. Since arrays are typically implemented using contiguous memory locations, adding an entry to the list will require that members below the new entry be moved out of the way to make room. Similarly, deleting a member will require movement of members to fill the void left by the removed entry.
One way to solve this dilemma is through the use of linked lists (sequential access). That is, rather than requiring contiguous locations, the members of the list are assigned arbitrary locations. The list is maintained by adding a link field to each entry.
Example. Create a simple linked list class. This class will have a front and rear pointer to allow adding and removing nodes from the front and rear. In addition, we will overload the insertion operator (<<) to facilitate output of list objects. A first version of the class interface might look as follows:
//Header File: smallLinked.h
#include <iostream>
//#include <iostream.h> Visual C++
using namespace std; //Eliminate for Visual C++
struct node
{
int data;
node * next;
};
class list
{
friend ostream & operator<< (ostream &,
list &);
private:
node *front;
node *rear;
public:
//list();
//Constructor
//list(const list &); //Copy
Constructor
//~list();
//Destructor
// Mutators
list & add_front (const int);
list & remove_front ();
list & add_rear (const int);
list & remove_rear ();
// Accessor
bool empty() const;
};
Lab Exercise. Implement the Constructor, the add_front () method, and overloaded << operator. You can then use my driver program to test your code. When you finish, feel free to compare your version with mine.