HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Linked list implementation of a stack

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listimplementationlinkedstack

Problem

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
#include
#include "DblStack.h"
using namespace std;

// Class Constructor
// post: stack is created & initialized to be empty
DblStack::DblStack()
: myTop(0), mySize(

Solution

Bug here:

If rhs.isEmpty() is true then you don't initialize mySize thus you have a random size.

DblStack::DblStack(const DblStack& rhs)
{
    myTop = 0;
    if (!rhs.isEmpty())


Copy and Swap Idiom

Rather than write your own assignment operator. Prefer to use the standard idiom of the language. Since this is mostly a copy of the copy constructor may as well use it rather than re-write the code.

DblStack& operator=(DblStack copy)
{
    copy.swap(*this);
    return *this;
}
void swap(DblStack& other) nothrow
{
    std::swap(myTop,  other.myTop);
    std::swap(mySize, other.mySize);
}


Efficiency

To make sure things are working perfectly you way want to implement the move constructor and the move assignment operator. These will make sure the compiler does the most efficient thing when you use the standard libraries.

nullptr

Use nullptr to represent the empty pointer.

return (myTop == 0);  // 0 should be nullptr


Should always check operations succeed

while (infile >> val)
{
   timeStep.push(val);
   infile >> val;         // You should make sure that works
                          // before you push into `soundData`
   soundData.push(val);
}

// Personally I would write like this:

while(infile >> timeVal >> soundVal)
{
   // Read worked.
   timeStep.push_back(timeVal);
   soundVal.push_back(soundVal);
}

Code Snippets

DblStack::DblStack(const DblStack& rhs)
{
    myTop = 0;
    if (!rhs.isEmpty())
DblStack& operator=(DblStack copy)
{
    copy.swap(*this);
    return *this;
}
void swap(DblStack& other) nothrow
{
    std::swap(myTop,  other.myTop);
    std::swap(mySize, other.mySize);
}
return (myTop == 0);  // 0 should be nullptr
while (infile >> val)
{
   timeStep.push(val);
   infile >> val;         // You should make sure that works
                          // before you push into `soundData`
   soundData.push(val);
}

// Personally I would write like this:

while(infile >> timeVal >> soundVal)
{
   // Read worked.
   timeStep.push_back(timeVal);
   soundVal.push_back(soundVal);
}

Context

StackExchange Code Review Q#67606, answer score: 11

Revisions (0)

No revisions yet.