Data Structures Can Someone help me change my program to use Templates throughou
ID: 3859354 • Letter: D
Question
Data Structures
Can Someone help me change my program to use Templates throughout? (List class, Stack class, Queue Class, and all functions)
For example
template <class T>
class stack
{
...................
}
also in my functions
template <class T>
stack <T> :: fillqueue(...
{
....
}
Thanks!!
(**************My Origonal Code Below****************)
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
using namespace std;
ofstream outfile;
const int CAPACITY = 20;
typedef int ET;
class List
{
public:
int pos;
int mysize;
ET myary[CAPACITY];
List()
{
mysize = 0;
pos = 0;
for (int i = 0; i < CAPACITY; i++)
{
myary[i] = 0;
}
}
List(List &l)
{
l.pos = 0;
for (int i = 0; i < l.mysize; i++)
{
myary[i] = l.getElement();
l.pos++;
}
mysize = l.mysize;
pos = l.pos;
}
bool empty()
{
return mysize == 0;
}
void first()
{
if (mysize >= 0)
pos = 0;
}
void last()
{
if (mysize > 0)
pos = mysize - 1;
}
void prev()
{
if (pos > 0)
pos--;
}
void next()
{
if (pos + 1 < CAPACITY)
pos++;
}
int getPos()
{
return pos;
}
void setPos(int n)
{
pos = n;
}
void insertBefore(ET v)
{
if (mysize == 0)
{
myary[0] = v;
pos = 0;
mysize = 1;
}
else
{
if (mysize + 1 > CAPACITY)
{
outfile << "The list has reached full capacity. ";
return;
}
else
{
for (int i = mysize; i >= pos; i--)
{
myary[i] = myary[i - 1];
}
myary[pos] = v;
mysize++;
}
}
}
void insertAfter(ET v)
{
if (mysize == 0)
{
myary[0] = v;
pos = 0;
mysize = 1;
}
else
{
if (mysize + 1 > CAPACITY)
{
outfile << "The list is full. ";
}
else
{
for (int i = mysize; i > pos; i--)
{
myary[i] = myary[i - 1];
}
myary[pos + 1] = v;
mysize++;
pos++;
}
}
}
ET getElement()
{
return myary[pos];
}
int size()
{
return mysize;
}
void replace(int n)
{
myary[pos] = n;
}
void erase()
{
for (int i = pos; i < mysize; i++)
{
myary[i] = myary[i + 1];
}
mysize--;
}
void clear()
{
for (int i = 0; i < mysize; i++)
{
myary[i] = 0;
}
mysize = 0;
pos = 0;
}
bool operator == (List& l)
{
if (l.size() != size())
return false;
else
{
for (int i = 0; i < size(); i++)
{
setPos(i);
l.setPos(i);
if (getElement() != l.getElement())
return false;
}
return true;
}
}
void operator = (List &l)
{
for (int i = 0; i < l.mysize; i++)
myary[i] = l.myary[i];
mysize = l.mysize;
pos = l.pos;
}
List operator + (List& l)
{
l.mysize = l.mysize + mysize;
return l;
}
friend ostream& operator << (ostream &out, List &l);
};
ostream& operator << (ostream &out, List &l)
{
for (int i = 0; i < l.size(); i++)
{
out << l.myary[i] << " ";
}
out << " ";
return out;
}
class stack
{
private:
List myStack;
int used;
public:
stack()
{
used = -1;
}
void push(ET v)
{
if (used < CAPACITY)
{
myStack.last();
myStack.insertAfter(v);
used++;
}
}
void pop()
{
if (used != 0)
{
myStack.last();
myStack.erase();
used--;
}
}
bool empty()
{
return used == 0;
}
int size()
{
return (used + 1);
}
ET top()
{
myStack.last();
return myStack.getElement();
}
};
class Queue
{
private:
List myQ;
public:
Queue()
{
myQ.clear();
}
void Enqueue(int num)
{
myQ.first();
if (myQ.size() == 0)
{
myQ.insertBefore(num);
myQ.next();
}
else if (myQ.size() < CAPACITY)
{
while(((myQ.getElement() % 10) < (num % 10)) && myQ.getElement() != 0)
{
myQ.next();
}
myQ.insertBefore(num);
}
}
void Dequeue()
{
if (myQ.size() != 0)
{
myQ.last();
myQ.erase();
myQ.next();
}
}
bool empty()
{
return myQ.empty();
}
int size()
{
return myQ.size();
}
int top()
{
myQ.last();
if (myQ.size() == 0)
return myQ.getElement();
}
void last()
{
myQ.last();
}
void prev()
{
if (myQ.size() > 0)
{
myQ.prev();
}
}
int getpos()
{
return myQ.getPos();
}
ET getElement()
{
return myQ.getElement();
}
};
int getline(char *line);
bool isBalanced(string filename);
void fillQueue(string filename);
void printQ(Queue myQ);
int getline(char *line)
{
char *tline = line;
int c;
while (((c = getchar()) != ' ') && (c != EOF))
*tline++ = c;
*tline = '';
if (c == EOF) return 0;
return (strlen(line));
}
const string OPEN = "([{<";
const string CLOSE = ")]}>";
bool isBalanced(string filename)
{
stack stk;
bool balanced = true;
string line;
ifstream infile;
infile.open(filename);
getline(infile, line);
while (infile)
{
int i = 0;
while (i < line.length())
{
char nextChar = line[i];
for (int j = 0; j < 4;)
{
if (nextChar == OPEN[j])
{
stk.push(nextChar);
outfile << line[i];
j = 4;
}
else if (nextChar == CLOSE[j])
{
char topChar = stk.top();
stk.pop();
outfile << line[i];
//balanced = (OPEN.find(topChar) == CLOSE.find(nextChar));
j = 4;
}
else
j++;
}
i++;
}
getline(infile, line);
}
return stk.empty() == 0;
}
void fillQueue(string filename)
{
ifstream infile;
infile.open(filename);
Queue qu;
string line;
int num;
int priority;
while (infile >> line)
{
if (line == "Enqueue")
{
infile >> num;
infile >> priority;
qu.Enqueue(((num * 10) + priority));
}
else if (line == "Dequeue")
{
qu.Dequeue();
}
}
printQ(qu);
}
void printQ(Queue myQ)
{
outfile << "Priority: " << "Value:" << endl;
myQ.last();
for (int i = myQ.size(); i > 0; i--)
{
outfile << (myQ.getElement() % 10) << " " << (myQ.getElement() / 10) << endl;
myQ.prev();
}
outfile << endl;
}
int main()
{
outfile.open("StackandQueue.txt");
string file1 = "LispClassData.txt";
string file2 = "Stack3.txt";
string file3 = "queue.txt";
if (isBalanced(file1))
outfile << file1 << " is balanced." << endl;
else
outfile << file1 << " not balanced." << endl << endl;
if (isBalanced(file2))
outfile << file2 << " is balanced." << endl;
else
outfile << file2 << " not balanced." << endl << endl;
fillQueue(file3);
outfile << endl << endl;
outfile.close();
system("pause");
return 0;
}
Explanation / Answer
Answer:
1)
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class stack
{
int input[5];
int peek;
public:
stack()
{
peek=-1;
}
void push(int x)
{
if(peek > 4)
{
cout <<"stack over flow";
return;
}
input[++peek]=x;
cout <<"inserted" <<x;
}
void pop()
{
if(peek <0)
{
cout <<"stack under flow";
return;
}
cout <<"deleted" <<input[peek--];
}
void display()
{
if(peek<0)
{
cout <<" stack empty";
return;
}
for(int i=peek;i>=0;i--)
cout <<input[i] <<" ";
}
};
main()
{
int ch;
stack st;
while(1)
{
cout <<" 1.push 2.pop 3.display 4.exit Enter ur choice";
cin >> ch;
switch(ch)
{
case 1: cout <<"enter the element";
cin >> ch;
st.push(ch);
break;
case 2: st.pop(); break;
case 3: st.display();break;
case 4: exit(0);
}
}
return (0);
}
2)
#include <iostream.h>
template<class T>
class Node
{
friend LinkedQueue<T>;
private:
T info;
Node<T> *link;
};
template<class T>
class LinkedQueue {
public:
LinkedQueue() {begin = end = 0;}
~LinkedQueue();
int IsEmpty() const
{return ((begin) ? 0 : 1);}
T First() const;
T Last() const;
LinkedQueue<T>& Add(const T& x);
LinkedQueue<T>& Delete(T& x);
private:
Node<T> *begin;
Node<T> *end;
};
template<class T>
LinkedQueue<T>::~LinkedQueue()
{
Node<T> *later;
while (begin) {
later = begin->link;
delete begin;
begin = later;
}
}
template<class T>
T LinkedQueue<T>::First() const
{
if (IsEmpty()) { cout<<"OutOfBounds()"; return -1; };
return begin->info;
}
template<class T>
T LinkedQueue<T>::Last() const
{
if (IsEmpty()) { cout<<"OutOfBounds()"; return -1; };
return end->info;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
{
Node<T> *p = new Node<T>;
p->info = x;
p->link = 0;
if (begin) end->link = p;
else begin = p;
end = p;
return *this;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{
if (IsEmpty()) { cout<<"OutOfBounds()"; return *this; };
x = begin->info;
Node<T> *p = begin;
begin = begin->link;
delete p;
return *this;
}
void main(void)
{
LinkedQueue<int> Q;
int x;
Q.Add(1).Add(2).Add(3).Add(4);
cout << "No queue add failed" << endl;
cout << "Queue is now 1234" << endl;
Q.Delete(x);
cout << "Deleted " << x << endl;
cout << Q.First() << " is at begin" << endl;
cout << Q.Last() << " is at end" << endl;
Q.Delete(x);
cout << "Deleted " << x << endl;
Q.Delete(x);
cout << "Deleted " << x << endl;
Q.Delete(x);
cout << "Deleted " << x << endl;
cout << "No queue delete failed " << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.