EECE 352: PS6

Due: Wednesday 13 October 1999

Problem 1 (80%) You will implement a class called DoubleStack. A doublestack consists of two stacks: a red one and a blue one. The user of a double stack can push, pop, and top from both the red and the blue stacks independently. The double stack you implement needs to provide this functionality while following these rules:
  1. You will use only one array for your implementation of the doublestack. You cannot use vectors or any of the STL containers. Your constructor must reserve memory for this array and the destructor must recover it.
  2. If the array you declare is of size N, you should not need to increase its size until the total number of elements in the red stack plus the elements in the blue stack is equal to N. When it is time to increase the size of the array, you should call the function expand.
  3. Your class should be templated.
  4. You should be careful about placing the const's in the right place.
Below is a skeleton for the DoubleStack class which gives all the functions I want you implement. Notice that this listing is missing all the arguments, return values, const keywords, etc. which you should place in your program. 
template <class ...>
class DoubleStack {
  //some data members
public:
	//The argument is the initial size of the array
  ... DoubleStack(int s = 10); //constructor, s is the initial size of the array
  ... ~DoubleStack();//destructor

  ... pushRed(...); // big-O time = ??
  ... pushBlue(...); // big-O time = ??
  ... popRed(...); // big-O time = ??
  ... popBlue(...); // big-O time = ??
  ... topRed(...); // big-O time = ??
  ... topBlue(...); // big-O time = ??
  ... expand(...); // big-O time = ??
  
  ... operator<<(...);
};
Below is the main.cpp which you can use to test your program. 
#include<iostream>
#include<fstream>
#include<string>
#include"DoubleStack.h" //remember to define all function in header
				//as mentioned in the class News (Aug 24)

using namespace std;

int main(){
	DoubleStack<string> q;
	q.pushRed("Russia"); q.pushRed("Stop"); q.pushRed("Blood");
	q.pushBlue("Moon"); q.pushBlue("Blood"); q.pushBlue("Sky");

	cout << q << endl;	//you must implement operator<< for DoubleStack.
						//It should print:
						//Red: Russia Stop Blood
						//Blue: Moon Blood Sky

	for (int count =0; count <1; count++){ //to test if your destructor works OK
		DoubleStack<string> p(10);

	//I will now read some words from this file and push them
	//into the stack.
		ifstream ifs("//Engr_asu/ECE352/words");
		string s;
		int i;
		for (i=0;i <10000; ++i){
			ifs >> s;
			p.pushRed(s);
		};
		for (i=0;i<20000;++i){
			ifs >> s;
			p.pushBlue(s);
		};
	//Pop and print some of the words.
		cout << "Blue: ";
		for (i=0; i< 10; ++i){
			string w = p.topBlue();
			cout << w << " ";
			p.popBlue();
		}
		cout << endl << "Red: ";
		for (i=0; i< 10; ++i){
			string w = p.topRed();
			cout << w << " ";
			p.popRed();
		}
		cout << endl;
	}
	return 0;
}
Problem 2 (20%) Write the big-O running time of each of the member functions in your class. State whether this time holds for every call to the function or if it is amortized.
Jose M. Vidal
Last modified: Thu Oct 7 18:32:40 EDT 1999