0

我正在编写一个程序来实现一个像现实世界堆栈一样工作的堆栈，这意味着当堆栈的大小达到阈值时它会倒塌，因此需要创建一个新堆栈来插入该新元素。

以下是我的程序：

#include <iostream>
#include<vector>
#include<stack>

using namespace std;

class stack_of_plates
{
   vector<stack<int> > stacks;
   unsigned int stack_size;
   public:
   stack_of_plates(unsigned int size=100)
   {
       stack_size=size;
   }

   void push(int data)
   {
       if(stacks.empty())
       {
           stack<int> *sptr= new stack<int>; //on debugging Segmentation fault at thisline
           stacks.push_back(*sptr);
       }

       vector<stack<int> >::iterator it=stacks.end();
       if(it->size()==stack_size)
       {
           stack<int> *sptr= new stack<int>; //on debugging Segmentation fault at thisline
           stacks.push_back(*sptr);
       }
       it->push(data);
   }

   void pop()
   {
       if(stacks.empty())
       {
           cout<<"\nEmpty Stack";
           return ;
       }
       vector<stack<int> >::iterator it=stacks.end();
       if(it->empty())
       {
           it--;
       }
       it->pop();
   }
   int top()
   {
       if(stacks.empty())
       {
           cout<<"\nEmpty Stack";
           return 0;
       }
       vector<stack<int> >::iterator it=stacks.end();
       if(it->empty())
       {
           it--;
       }
       return it->top();
   }
};


int main()
{
   stack_of_plates ss;
   ss.push(1);
   ss.push(2);
   cout<<ss.top();
   return 0;
}

在编译它没有给出错误或警告。但是程序因异常错误而终止。在调试它给出的分段错误错误指示分配新堆栈的问题。请帮助我在分配新堆栈时应该如何更改我的代码。请帮我消除这个错误。

4

3 回答 3

3

stacks.end();指向量结束后的（不存在的）元素。你不能取消引用它；这样做会导致未定义的行为，可能是分段错误。

目前还不清楚你在那里做什么，但如果你想要最后一个元素的迭代器，那么要么递减它：

vector<stack<int> >::iterator it=stacks.end();  // points past the end
--it;                                           // points to last element

或使用反向迭代器（在这种情况下，您使用++而不是--在序列中向后移动）：

vector<stack<int> >::reverse_iterator it=stacks.rbegin();

将元素添加到向量可以使其无效，因此it->push_back(data)末尾的push()是不正确的。您可以避免在此处使用迭代器：

void push() {
    if (stacks.empty() || stacks.back().size()==stack_size) {
        // See below for explanation of this change
        stacks.push_back(stack<int>());
    }
    stacks.back().push(data);
}

在pop()中，如果最后一个堆栈为空，您可能想要删除它；否则，您最终会得到两个空堆栈，并且您的代码将错误地尝试pop从其中一个堆栈中提取。同样，这样做可能会导致分段错误或其他未定义的行为。你可能想要这样的东西：

void pop() {
    if (stacks.empty()) {
        cout<<"\nEmpty Stack";
        return ;
    }
    stacks.back().pop();
    if (stacks.back().empty()) {
        stacks.pop_back();
    }
}

现在我们已经建立了一个不变量，即最后一个堆栈永远不会为空，top可以更简单一点：

int top() {
    if (stacks.empty()) {
        cout<<"\nEmpty Stack";
        return 0;
    }
    return stacks.back().top();
}

此外，您通常不希望使用 创建对象new，尤其是在这种情况下，您将对象的副本放入向量中，然后丢弃指针，从而泄漏分配的内存。您可以像这样向向量添加一个空堆栈：

stacks.push_back(stack<int>());

有时（但不是在这种情况下）您可能希望将指向已分配对象的指针存储在容器中；在这种情况下，要么记得在从容器中删除它们时删除它们，要么存储智能指针，例如std::unique_ptr. 但在这种情况下，只需存储对象。

于 2012-08-22T11:00:54.023 回答
1

代码有很多问题，所以很难说哪一个是你问题的直接原因。您需要将它们一一清理，然后重新测试。如果您仍有问题，请在此处发布您的新代码。

这是列表：

  1. 您使用 new 分配的内存泄漏。由于您有一个堆栈向量，您需要做的就是调整向量的大小并分配一个新的堆栈。所以

    stacks.resize(stacks.size() + 1);

    代替

    stack<int> *sptr= new stack<int>; stacks.push_back(*sptr);

  2. vector<>.end() 返回一个迭代器，该迭代器指向最后一个元素之后的元素，这就是@Joachim 建议您在使用迭代器之前需要递减它的原因。

  3. 当您检查是否将存储转移到新堆栈时出现逻辑错误 - 检查最后一个堆栈的大小是否为最大值，并创建一个新堆栈后，您继续推动旧堆栈。

我希望这有帮助。

于 2012-08-22T10:57:17.080 回答
0

std::stack<int>已经具有您在示例中显示的功能，因此不需要std::vector< std::stack<int> >. 只需推送和弹出即可std::stack<int>避免您在代码中遇到的大多数问题。没有理由std::stack<int>限制stack_size.

除此之外，当您需要容器中的最后一个条目时，请使用back()而不是end().

于 2012-08-22T11:07:13.743 回答