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

这是一个相当标准的堆栈实现。唯一与您在大多数教科书中看到的堆栈类型不同的是 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 个值时调用 adjust() 函数，而不是 99 ，所以我不认为这是调整功能的问题。

Answer 1

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

期间丢失

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

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