为什么我的 Stack 实现中的第 98 个元素如此奇怪

Question

我在C++中有以下堆栈数据结构实现：

// file: Stack.h
#pragma once
#include <iostream>
#include <exception>
class CStack
{
private:
    int counter;
    int *data;
    int currentmaxsize;
    void adjust();
public:
    void push(int value);
    int pop();
    int peek();
    int getsize();
    CStack();
    ~CStack();
};

// file: Stack.cpp
#include "Stack.h"
void CStack::adjust()
{
    int *temp = new int[currentmaxsize];
    for (int i = 0; i < counter; i++)
    {
        temp[i] = data[i];
    }
    delete data;
    data = new int[currentmaxsize * 2];
    for (int i = 0; i < counter; i++)
    {
        data[i] = temp[i];
    }
    delete temp;
    currentmaxsize *= 2;
}
int CStack::getsize()
{
    return counter;
}
void CStack::push(int value)
{
    if (counter+1 == currentmaxsize)
    {
        adjust();
    }
    counter++;
    data[counter] = value;
}
int CStack::peek()
{
    return data[counter];
}
int CStack::pop()
{
    if (counter > 0)
    {
        int ret = data[counter];
        counter--;
        return ret;
    }
    else if (counter == 0)
    {
        throw std::exception("cannot pop empty stack");
    }
    return 0xFFFFFFFF;
}
CStack::CStack()
{
    data = new int[100];
    currentmaxsize = 100;
    counter = 0;
}

CStack::~CStack()
{
    delete data;
}

这是一个相当标准的堆栈实现。与你在大多数教科书中看到的堆栈类型唯一不同的是 adjust(( 函数，如果达到原始边界，它会以更大的大小重新分配堆栈。

我也为数据结构编写了以下驱动程序：

// file: driver.cpp
#include <iostream>
#include "Stack.h"
int main(int argc, char *argv[])
{
    CStack stack;
    for (int i = 0; i < 200; i++)
    {
        stack.push(i);
        std::cout << "Pushed: " << i << std::endl;
        //std::cout << "New stack size: " << stack.getsize() << std::endl;
    }
    int len = stack.getsize();
    std::cout << "len = " << len << std::endl;
    for (int i = 0; i < len; i++)
    {
        std::cout << "Popped: " << stack.pop() << std::endl;
        //std::cout << "New stack size: " << stack.getsize() << std::endl;
    }
    return 0;
}

这几乎按照我的预期工作，除了程序输出中的这个值：

Popped: 100
Popped: 99
Popped: 7798895
Popped: 97
Popped: 96

堆栈中第 98 个元素的值总是具有这样的奇怪值，我不知道为什么会这样 - 当堆栈达到 100 个值而不是 99 个值时，会调用 adjust(( 函数，所以我不认为这是调整函数的问题。

Answer 1

您的push和peek以及其他函数可能使用counter作为最后一个元素的索引。 但是代码的其他部分使用 counter 作为元素的数量counter-1因此这将是最后一个索引。 因此，数据在adjust期间会丢失

选择一个设计：有效索引为 0 到 counter-1(含(或 0 到 counter 或 1 到 counter(浪费位置 0(。

我只喜欢这些选择中的第一个，但其中任何一个都可以工作(您现有的代码最接近第三个(。 让不同的部分按照不同的规则进行游戏是行不通的。

Answer 2

我至少看到一个错误。 您在执行new[]后正在使用delete。

new应与delete匹配，new[]应与delete[]匹配。否则，它是未定义的行为。

此外，您在adjust函数中执行不必要的复制。