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!