c++ - C++ 堆栈堆栈

Question

我正在尝试使用一组堆栈来实现一个堆栈。每个栈都有一个最大大小（阈值），每次达到这个大小（即当前栈满），我就传给下一个。这种机制对用户应该是透明的，它应该表现为一个单一的堆栈。

我想用一堆堆栈。这是我的单栈类，实现为单链表。

#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;
    }
};

这就是我实现堆栈类的方式。

#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;
}

问题是调用stack.push(i)没有做它应该做的事情。第一个（并且仅在这个例子中）内部堆栈仍然是空的，我不知道为什么。

谢谢你的帮助！

标签： c++pointersdata-structuresstack