0

I'm trying to implement a stack using a set of stacks. Each stack has a maximum size (threshold), every time this size is reached (that is, the current stack is full), I pass to next one. This mechanism should be transparent to the user, it should behave as a sigle stack.

I thought to use a stack of stacks. This is my single stack class, implemented as a singly linked list.

#include <iostream>

template <typename T>
class Node
{
public:
    T data;
    Node<T> *next;

    Node(T data, Node<T> *next = nullptr)
    {
        this->data = data;
        this->next = next;
    }
};

template <typename T>
class Stack
{
    Node<T> *head;

public:
    Stack()
    {
        head = nullptr;
    }

    bool IsEmpty()
    {
        return head == nullptr;
    }

    void push(T data)
    {
        if (IsEmpty())
        {
            head = new Node<T>(data);
        }
        else
        {
            head = new Node<T>(data, head);
        }
    }

    T peek()
    {
        if (IsEmpty())
        {
            throw std::runtime_error("peek : stack empty");
        }

        return head->data;
    }

    T pop()
    {
        if (IsEmpty())
        {
            throw std::runtime_error("pop : stack empty");
        }

        T data = head->data;
        head = head->next;

        return data;
    }

    void print()
    {
        std::cout << "stack : ";

        if (IsEmpty())
        {
            std::cout << "empty" << std::endl;
            return;
        }

        Node<T> *p = head;

        while (p != nullptr)
        {
            std::cout << p->data << " ";
            p = p->next;
        }

        std::cout << std::endl;
    }
};

And here is how I'm implementing my stack of stacks class.

#include <iostream>
#include "stack.hpp"

template <typename T>
class SetOfStacks
{
private:
    Stack<Stack<T>> stacks;
    int threshold;
    int StackSize;

public:
    SetOfStacks()
    {
        stacks.push(Stack<T>());
        threshold = 4;
        StackSize = 0;
    }

    void push(T data)
    {
        if (StackSize == threshold)
        {
            stacks.push(Stack<T>());
            StackSize = 0;
        }

        stacks.peek().push(data);
        StackSize++;
    }

    bool IsEmpty()
    {
        return stacks.peek().IsEmpty();
    }

    void print()
    {
        stacks.peek().print();
    }

    T peek()
    {
        return stacks.peek().peek();
    }

    T pop()
    {
        /* ... */
    }
};

int main()
{
    try
    {
        SetOfStacks<int> stack;
        stack.print(); // --> stack empty, OK!

        for (int i = 0; i < 4; i++)
        {
            stack.push(i);
        }

        stack.print(); // --> still stack empty, why?
    }
    catch (const std::exception &exc)
    {
        std::cerr << exc.what() << std::endl;
    }

    return 0;
}

The problem is that the call to stack.push(i) doesn't do what it should do. The first (and only in this example) inner stack remains empty, and I can't figured out why.

Thanks for any help!

Arctic Pi
  • 669
  • 5
  • 19
  • Isn't this what `std::stack` already does, with the default container type `std::deque` that it has? – John Zwinck May 16 '19 at 14:26
  • I have to implement this from scratch. It's an exercise. Thanks. Moreover, the point is that I would like to understand what is the problem here, regardless of solving or not the exercise. – Arctic Pi May 16 '19 at 14:28
  • 1
    Your stack leaks memory. – eerorika May 16 '19 at 14:33
  • Before diving anything more complicated than a `Stack` of `int`s, make sure there are no bugs in `Stack` by testing the stuffing out of a `Stack` of `int`s. Otherwise you'll find yourself playing Whack-A-Mole. – user4581301 May 16 '19 at 14:36
  • 1
    Technically the issue here is that `peek()` returns a copy of the stored `Stack`, which you modify with `push` and then immediately discard (and the original one that `peek()` tried to return is left unmodified). But the whole program won't ever work correctly unless you follow the rule of three/five/zero by considering what it means to copy a `Stack`, where you currently do that, and whether you want to actually do it (all of which seems to be the point of the entire exercise). Hence the dupe. – Max Langhof May 16 '19 at 14:43
  • 1
    Essentially, there are three distinct problems here: 1. You are leaking memory. Fix this by correctly implementing the destructor of `Stack`. 2. Your program will now crash because the copy constructor/assignment of `Stack` are both missing. Implement those. 3. Don't return a copy from `peek()` (or if you do, don't assume modifying this copy will modify the top element of the `Stack` you `peek`ed). Doing only 3. might technically give you correct output but your program would still be wrong (and probably fail the exercise). – Max Langhof May 16 '19 at 14:48
  • @user4581301 Of course I moved on, only when I was enough sure the single stack class was well implemented or "robust" (in a self exercises context). Thanks. – Arctic Pi May 16 '19 at 14:50
  • @MaxLanghof Thanks. Now I (start to) see the problem. Can you explain me briefly (if it is possible) point 1? – Arctic Pi May 16 '19 at 14:55
  • 1
    If you `new` something, you must `delete` it eventually. That's what destructors are for. I really hope that whatever class you are taking covered this when introducing `new`, well before asking you to write a stack of stacks. – Max Langhof May 16 '19 at 14:58
  • @MaxLanghof Thank you so much! No class, just self learning. – Arctic Pi May 16 '19 at 15:01

0 Answers0