6
\$\begingroup\$

I have modified my code as per the suggestion given by some of the developers. Let me know if there are any further concerns or scope for improvements.

Original Version

 #include"iostream"
template <class T>
class Mystack
{
private:
    T *input;
    int top;
    int capacity;
public:
    Mystack();
    ~Mystack();
    void push(T x);
    T pop();
    T topElement() const;
    bool isEmpty() const;
    void print();
};
template <class T>
Mystack<T>::Mystack()
{
    top = -1;
    capacity = 5;
    input = new T[capacity];
}
template <class T>
Mystack<T>::~Mystack()
{
    delete[]input;
}
template <class T>
void Mystack<T>::push(T x)
{
    if (top + 1 == capacity)
    {
        T *vec = new T[capacity + capacity];
        for (int i = 0; i <= top; i++)
        {
            vec[i] = input[i];
        }
        delete[]input;
        input = vec;
        capacity = capacity * 2;
        top++;
        input[top] = x;
    }
    else
    {
        top++;
        input[top] = x;
    }
}
template <class T>
T Mystack<T>::pop()
{
    if (isEmpty())
    {
        throw std::out_of_range("Stack Underflow");
    }
    else
    {
        std::cout << "The popped element is" << input[top];
        return input[top--];

    }
}
template <class T>
bool Mystack<T>::isEmpty() const
{
    if (top == -1)
    {
        std::cout << "Is Empty" << std::endl;
        return true;
    }
    else
    {
        std::cout << "Not Empty" << std::endl;
        return false;
    }
}
template <class T>
T Mystack<T>::topElement() const
{
    if (top == -1)
    {
        throw std::out_of_range("No Element to Display");
    }
    else
    {
        std::cout << "The top element is : " << input[top];
        return input[top];
    }
}
template <class T>
void Mystack<T>::print()
{
    for (int i = 0; i <= top; i++)
    {
        std::cout << input[i] << " ";
    }
}
int main()
{
    Mystack<int> s1;
    Mystack<float> s2;
    Mystack<char> s3;
    int choice;
    int int_elem;
    float float_elem;
    char char_elem;
    std::cout << "Enter the type of stack" << std::endl;
    std::cout << "1. int"<<std::endl;
    std::cout << "2. float" << std::endl;
    std::cout << "3. Char" << std::endl;
    std::cin >> choice;
    if (choice == 1)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. PUSH" << std::endl;
            std::cout << "2. TOP" << std::endl;
            std::cout << "3. IsEmpty" << std::endl;
            std::cout << "4. POP" << std::endl;
            std::cout << "5. EXIT" << std::endl;
            std::cout << "6. Print" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> int_elem;
                s1.push(int_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    s1.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                s1.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    s1.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                exit(0);
            case 6:
                s1.print();
                break;
            default:
                std::cout << "Enter a valid input";
                break;
            }
        }
    }
    else if (choice == 2)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. PUSH" << std::endl;
            std::cout << "2. TOP" << std::endl;
            std::cout << "3. IsEmpty" << std::endl;
            std::cout << "4. POP" << std::endl;
            std::cout << "5. EXIT" << std::endl;
            std::cout << "6. Print" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> float_elem;
                s2.push(float_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    s2.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                s2.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    s2.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                exit(0);
            case 6:
                s2.print();
                break;
            default:
                std::cout << "Enter a valid input";
                break;
            }
        }
    }
    else if (choice == 3)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. PUSH" << std::endl;
            std::cout << "2. TOP" << std::endl;
            std::cout << "3. IsEmpty" << std::endl;
            std::cout << "4. POP" << std::endl;
            std::cout << "5. EXIT" << std::endl;
            std::cout << "6. Print" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> char_elem;
                s3.push(char_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    s3.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                s3.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    s3.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                exit(0);
            case 6:
                s3.print();
                break;
            default:
                std::cout << "Enter a valid input";
                break;
            }
        }
    }
    else
        std::cout << "Invalid Choice";
    std::cin.get();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ #include <iostream> \$\endgroup\$ – bhathiya-perera Dec 31 '14 at 14:50
  • 1
    \$\begingroup\$ #include"iostream" - this works? \$\endgroup\$ – morbidCode Dec 31 '14 at 15:51
  • 1
    \$\begingroup\$ That is disturbing. #include "" should only work for user-defined header files. For standard library headers you should use <> \$\endgroup\$ – morbidCode Dec 31 '14 at 16:02
  • 1
    \$\begingroup\$ It's nice to see templates here! Thanks for taking much of our advice into consideration. \$\endgroup\$ – Jamal Dec 31 '14 at 17:37
  • 1
    \$\begingroup\$ As a note #include "" will search the user include list then the system include list. #include <> will search the system include list, then optionally the user include list. Since iostream is a system header you should use <> as it is more likely to find it quicker. The definition of user include list and the system include list are compiler dependent. \$\endgroup\$ – Martin York Jan 1 '15 at 19:06
6
\$\begingroup\$

Your main problem is that you have a RAW pointer in your class and don't implement the rule of three.

This will break your object:

 int main()
 {
     Mystack    a;
     Mystack    b(a); // Copy construction works (as compiler defined).
 }                    // Destructor will delete both objects. BUT.... (double delete)

The same problem but with assignment

 int main()
 {
     Mystack    a;
     Mystack    b;

     b = a;            // Assignment works (as compiler defined).
                       // But will leak its original value.

 }                     // Destructor will delete both objects. BUT...

Additionally (Sine this is now 2015) you may also want to use move semantics (introduced in 2011).

 Mystack(Mystack&& move)           {/*STUFF*/}
 MyStack& operator=(Mystack&& rhs) {/*STUFF*/}

The following is not a bug. But if T is expensive to create then could make your stack inefficient.

Mystack<T>::Mystack()
{
    top = -1;
    capacity = 5;
    input = new T[capacity];   // This creates an array of `capacity` but it also
                               // calls the constructor on every object in the array.
                               // even though you are only uisng the `top` values.
}

It may not be an issue. But it is worth mentioning. This will make std::vector<> more efficient as it deals with this situation (note you will need to understand placment new and manual destruction to cope with it).

Another inefficiency is the copy of data from the old array to the new re-sized array:

    T *vec = new T[capacity + capacity];
    for (int i = 0; i <= top; i++)
    {
        vec[i] = input[i];
    }

If T is big and expensive to copy then this is not efficient. Since the old vector is going to be destroyed you don't care about the old values. So a better alternative is to move the objects from the old array into the new one.

    T *vec = new T[capacity + capacity];
    for (int i = 0; i <= top; i++)
    {
        vec[i] = std::move(input[i]);
              // ^^^^^^^^^^            Changes the type to an rvalue reference
              //                       This will cause it to bind to the move assignment
              //                       operator rather than the copy.
    } 

But you should prefer to use standard algorithms rather than doing manual loops.

    T *vec = new T[capacity + capacity];
    std::move(input, input + top + 1, vec);

For safety you should not delete any thing until your object is in a consistent state.

    delete[]input;              // If any of the constructors throw an exception
                                // then your object will be left in an inconsistent state.
                                // So best to do this last.
    input = vec;
    capacity = capacity * 2;
    top++;
    input[top] = x;

Try this:

    // Change the state of the object in a safe exception safe manor.
    std::swap(input, vec);     // swap the old and new.
    capacity = capacity * 2;
    top++;
    input[top] = x;

    // Now the object is in a good state. You can do dangerous operations.
    // that have the potential to throw. Even if they throw the object is
    // in a valid state and catching and recovering from the exception would
    // work just fine.
    delete [] vec;              // Your old array (remember we swapped).

A simpler way to implement this copy is to reuse the constructor code.

 Mystack::Mystack(capacity = 5);  // Allow constructor to take a capacity.

 template <class T>
 void Mystack::push(T const& v)   // Pass by reference to avoid copy.
 {
    if (top + 1 == capacity)
    {
        Mystack    result(capacity + capacity);  // Create an object with the correct
                                                 // Capacity.

        // Put the data into result.
        std::move(input, input + top + 1, result.input);
        result.top = top;

        // Use move semantics to swap the bigger data from result into this
        // object. This will genrally put this objects data into result.
        (*this) = std::move(result);  // or result.swap(*this);

        // The destructor of result now cleans up.
    }
    top++;
    input[top] = x;
}

Couple of minor points:

void push(T const& x);    // You want to add pass the value by reference.
void push(T&& x);         // Allow people to push by using move semantics.

void pop();               // Pop is usually a void operation.

T& topElement() const;    // You can return the top value by reference.
                          // If you don't pop it then you can manipulate it
                          // in-place in the stack.

void print(std::ostream&) const;
                          // Fine have a print but at least pass the stream
                          // you want to print on and make the method const.

// Also add a free standing function that prints like other objects that just
// calls the print method:

friend std::ostream& operator<<(std::ostream& s, Mystack const& d) {
    d.print(s);
    return s;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Phew!! You are one hell of a programmer & reviewer. Thanks & Respect! I will try to incorporate the suggestions you have mentioned in my code. \$\endgroup\$ – Unbreakable Jan 1 '15 at 19:17
  • 1
    \$\begingroup\$ @Unbreakable: Look forward to reviewing your updated code. \$\endgroup\$ – Martin York Jan 1 '15 at 19:32
  • \$\begingroup\$ Hi Loki, std::move does help to avoid memcpy and realloc you had warned me about. One question I still want to know about is what happens if I allocate more than the heap can sustain because capacity is exponentially increasing? \$\endgroup\$ – thepace Jan 2 '15 at 6:10
  • \$\begingroup\$ @thepace: I am not sure exactly what you are asking. But a new that fails will throw an exception. \$\endgroup\$ – Martin York Jan 2 '15 at 9:28
  • \$\begingroup\$ ok. My concern was mainly of the way the allocations were doubled each time it exceeded which could lead to heap exhaustion at some point. I guess you are correct in not being over-aggressive with handling the exceptions as well. Thanks. \$\endgroup\$ – thepace Jan 2 '15 at 9:35
4
\$\begingroup\$

Don't repeat yourself

In the push method you have:

if (top + 1 == capacity)
{
    // ...

    top++;
    input[top] = x;
}
else
{
    top++;
    input[top] = x;
}

That is, in both branches of the if-else you increment top assign to input[top]. This is error prone, as in the future you may make change in one place and forget to do it in the other. In this example you can get rid of the duplication and eliminate the else branch:

if (top + 1 == capacity)
{
    // ...
}
top++;
input[top] = x;

I see other kinds of duplication too:

    T *vec = new T[capacity + capacity];
    capacity = capacity * 2;

Typing out capacity so many times tedious, and again, can be error prone. It's better to write this way:

    T *vec = new T[capacity * 2];
    capacity *= 2;

Spacing

The code will be easier to read if you add more blank lines to emphasize units of code that belong together and separate from other units that are more loosely related. Especially between the method implementations.

Not putting a space after [] in delete[]input is also pretty odd.

Don't print in methods

Printing to the console doesn't belong in methods of a stack implementation. I suppose you're doing this for debugging purposes and hopefully intend to remove later. Printing is an additional responsibility, and methods are best when they have just one responsibility.

The implementation will become simpler, for example isEmpty without printing:

bool Mystack<T>::isEmpty() const
{
    return top == -1;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The redundancy of increasing capacity can be avoided by using capacity *= 2; and then T* vec = new T[capacity]; \$\endgroup\$ – R Sahu Jan 2 '15 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.