我在C++中有以下堆栈数据结构实现:
// file: Stack.h #pragma once #include#include 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#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()函数,所以我不要想象调整功能有问题.
您push
和peek
可能的其他函数counter
用作最后一个元素的索引.但是代码的其他部分counter
用作元素的数量,因此counter-1
它将是last的索引.因此数据丢失了adjust
选择一种设计:有效索引为0到counter-1
包含0 或 0 counter
或 1到counter
(浪费位置0).
我只喜欢这些选择中的第一个,但其中任何一个都可以工作(您现有的代码最接近第三个).根据不同的规则玩不同的部分是行不通的.