c++ - 为什么我的 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;
}

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

我还为数据结构编写了以下驱动程序:

// 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 个值时，会调用 adjustment() 函数，所以我不认为这是调整功能的问题。

Answer 1

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

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

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