为什么我的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它将是last的索引.因此数据丢失了adjust

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

我只喜欢这些选择中的第一个,但其中任何一个都可以工作(您现有的代码最接近第三个).根据不同的规则玩不同的部分是行不通的.