I am working on a basic linked list implementation of a stack of ItemType
(currently set to double but can be changed) values. The stack code will then be used in a function that reverses a sound data file by reading in all the data samples, pushing them onto a stack, and then creating a new sound data file while popping values off the stack. My code seems to be working fine, but it does take a rather long time to finish processing.
Though this is likely due in part to the length of the files, I would appreciate any tips to help optimize my code and potentially speed it up.
Below is my header file:
#ifndef DBLSTACK_H
#define DBLSTACK_H
typedef double ItemType; // stack currently holds doubles
class DblStack
{
private:
//Node class
class Node
{
public:
double data;
Node *next;
// Node constructor
Node(double value, Node * link = 0)
{
data = value;
next = link;
}
};
typedef Node * NodePtr;
// Data members
NodePtr myTop; //points to top of stack
public:
// Class Constructor
DblStack();
// Copy Constructor
DblStack(const DblStack& rhs);
// Class Deconstructor
~DblStack();
// Assignment operator
// Assigns a stack to another
const DblStack& operator= (const DblStack& rhs);
// isEmpty
// Checks if the stack is empty
bool isEmpty() const;
// push
// Pushes an item on top of the stack.
void push(const ItemType& item);
// pop
// Pops the top item off the stack.
void pop();
// top
// Returns the top item of the stack without popping it.
ItemType top() const;
// size
// Returns the number of items on the stack.
size_t size() const;
};
#endif
And here is my source file:
#include <cstddef>
#include <stdexcept>
#include "DblStack.h"
using namespace std;
// Class Constructor
// post: stack is created & initialized to be empty
DblStack::DblStack()
: myTop(0), mySize(0)
{
}
// Copy Constructor
// pre: parameter object, rhs, exists
// post: stack is created to be a copy of the parameter stack
DblStack::DblStack(const DblStack& rhs)
{
myTop = 0;
if (!rhs.isEmpty())
{
// Copy first node
myTop = new DblStack::Node(rhs.top());
// Set pointers to run through stack
DblStack::NodePtr lastPtr = myTop;
DblStack::NodePtr origPtr = rhs.myTop->next;
while (origPtr != 0)
{
lastPtr->next = new DblStack::Node(origPtr->data);
lastPtr = lastPtr->next;
origPtr = origPtr->next;
}
}
}
// Class Deconstructor
// pre: the stack exists
// post: the stack is destroyed and any dynamic memory is returned to the system
DblStack::~DblStack()
{
// Set pointers to run through stack
DblStack::NodePtr curr = myTop, next;
while (!isEmpty())
{
next = curr->next;
delete curr;
curr = next;
}
}
// Assignment operator
// Assigns a stack to another
// pre: both class objects exist
// post: this class object gets assigned a copy of the parameter class object
const DblStack& DblStack::operator= (const DblStack& rhs)
{
if (this != &rhs)
{
if (rhs.isEmpty())
{
myTop = 0;
}
else
{
DblStack tmp(rhs); // Call copy constructor
std::swap(myTop, tmp.myTop);
}
}
return *this;
}
// isEmpty
// Checks if the stack is empty
// pre: A stack exists.
// post: Returns true if it IS empty, false if NOT empty.
bool DblStack::isEmpty() const
{
return (myTop == 0);
}
// push
// Pushes an item on top of the stack.
// pre: Stack exists and item is passed.
// post: the item is placed on top of the stack, and size is incremented.
void DblStack::push(const ItemType& item)
{
myTop = new DblStack::Node(item, myTop);
mySize++;
}
// pop
// Pops the top item off the stack.
// pre: Stack exists.
// post: Removes item on top of stack. If the stack
// was already empty, throws a std::underflow_error exception.
void DblStack::pop()
{
if (!isEmpty())
{
DblStack::NodePtr ptr = myTop;
myTop = myTop->next;
mySize--;
delete ptr;
}
else
{
throw std::underflow_error("Stack is empty");
}
}
// top
// Returns the top item of the stack without popping it.
// pre: Stack exists.
// post: Returns item on top of stack. If the stack
// was already empty, throws a std::underflow_error exception.
ItemType DblStack::top() const
{
if (!isEmpty())
{
return myTop->data;
}
else
{
throw std::underflow_error("Stack is empty");
}
}
// size
// Returns the number of items on the stack.
// post: Returns size from the private section of class.
size_t DblStack::size() const
{
return mySize;
}
Additionally, here is the source code for "reverse" which will implement the stack:
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include "DblStack.h"
using namespace std;
// open input and output files
// pre: user is prepared to enter file names at the keyboard
// post: files have been opened
void openFiles (ifstream &infile, ofstream &outfile);
int main ()
{
ifstream infile;
ofstream outfile;
openFiles(infile, outfile);
cout << "Reading the input file..." << endl;
string firstLine, secondLine;
getline(infile,firstLine);
getline(infile,secondLine);
DblStack timeStep, soundData;
double val;
while (infile >> val)
{
timeStep.push(val);
infile >> val;
soundData.push(val);
}
cout << "There were " << timeStep.size() << " samples in the file." << endl;
cout << "Creating output file... wait for Done message." << endl;
outfile << firstLine << endl;
outfile << secondLine << endl;
while (!(timeStep.isEmpty() || soundData.isEmpty()))
{
outfile << " " << timeStep.top() << "\t" << soundData.top() << "\n";
timeStep.pop();
soundData.pop();
}
infile.close();
outfile.close();
cout << "Done." << endl;
char junk;
cout << "press enter to exit";
junk = cin.get();
junk = cin.get();
}
// open input and output files
// pre: user is prepared to enter file names at the keyboard
// post: files have been opened
void openFiles (ifstream &infile, ofstream &outfile)
{
// open input data file
string inFileName;
cout << "Enter the name of the input file: ";
cin >> inFileName;
infile.open(inFileName.c_str());
if (infile.fail()) {
cout << "Error opening input data file" << endl;
exit(1);
}
// open output data file
string outFileName;
cout << "Enter the name of the output file: ";
cin >> outFileName;
outfile.open(outFileName.c_str());
if (outfile.fail()) {
cout << "Error opening output data file" << endl;
exit(1);
}
}