c++ - ArrayStack 大小

Question

我在 C++ 中完成了这个任务，我必须只使用数组(而不是使用 vector 之类的东西)来实现堆栈。老师给了我们一个可以遵循的界面和一些代码来测试我们的 ArrayStack。我的问题是，当我创建一个堆栈时，用 100 个元素填充它然后清空它，大小为 4(我将最小值设置为 4)，当教师代码执行相同操作时(在 testStack 函数中)，相同的检查失败。

这是我的代码:

#include <iostream>
#include <string>
#include <assert.h>

using namespace std;

template<typename T>
class Stack {
public:
    // Adds new element to the top of the stack
    virtual void push(T x) = 0;
    // Returns the top element AND removes it from the stack
    // If the stack is empty use 'throw std::out_of_range("<human_friendly_message>");'
    virtual T pop() = 0;
    // Returns the top element but does NOT remove it from the stack
    // If the stack is empty use 'throw std::out_of_range("<human_friendly_message>");'
    virtual T top() = 0;
    // Returns the current number of elements in the stack
    virtual int getSize() = 0;
    // Returns the current capacity of the underlying data storage (array)
    virtual int getCapacity() = 0;
    // Returns true if the stack has no elements and false otherwise
    virtual bool isEmpty() = 0;
};

template<typename T>
class ArrayStack : public Stack<T>{
private:
    T* data;
    int arraysize;
    int N;

    void resize(int capacity)
    {
        T* copy = new T[capacity];

        for (int i = 0; i < N; i++)
            copy[i] = data[i];

        T* p = data;
        data = copy;
        delete [] p;
    }

public:
    ArrayStack(){
        N = 0;
        data = new T[4];
        arraysize = 4;
    }

    ArrayStack(int n){
        if (n < 1) n = 1;

        N = 0;
        data = new T[n];
        arraysize = n;
    }

    bool isEmpty(){ return N == 0; }

    void push(T x)
    {
        if (N == arraysize)
        {
            resize(2 * arraysize);
            arraysize *= 2;
        }
        data[N] = x;
        N++;
    }

    T pop()
    {
        if (isEmpty()){
            throw out_of_range("Can't pop on empty stack");
        }
        else{
            N--;
            T k;
            k = data[N];

            if (N > 0 && N == arraysize / 4 && arraysize/2>=4)
            {
                resize(arraysize / 2);
                arraysize /= 2;
            }
            return k;
        }
    }

    T top()
    {
        if (isEmpty()) throw out_of_range("Can't top on empty stack");
        return data[N - 1];
    }

    int getCapacity()
    {
        return arraysize;
    }

    int getSize()
    {
        return N;
    }

    ~ArrayStack()
    {
            delete [] data; 
    }
};

template<class T>
void testStack(Stack<T> *& stack, int cap = 128) {
    for (int i = 0; i < 100; i++) {
        stack->push(i);
        assert(stack->top() == i);
    }

    assert(stack->getCapacity() == cap);
    assert(stack->getSize() == 100);


    for (int i = 99; i >= 0; i--) {
        assert(stack->top() == i);
        stack->pop();
    }
    assert(stack->getCapacity() == 4);
    assert(stack->isEmpty());
}

int main() {    
    try {
        Stack<int> * stackI = new ArrayStack<int>();
        testStack(stackI);
        delete stackI;

        Stack<float> * stackF = new ArrayStack<float>(1);
        testStack(stackF);
        delete stackF;

        Stack<double> * stackD = new ArrayStack<double>(65536);
        testStack(stackD, 65536);
        delete stackD;

        Stack<string> * stackS = new ArrayStack<string>();
        stackS->push("string1");
        stackS->push("string2");
        stackS->push("string3");
        stackS->push("string4");

        for (int i = 0; i < 4; i++) {
            stackS->pop();
        }
        assert(stackS->isEmpty());

        cout << "All tests passed!" << endl;

    }
    catch (std::exception & ex) {
        cout << ex.what() << endl;
    }

    return 0;
}

Answer 1

您可能已经注意到，问题出现在最后一个堆栈，即初始容量为 65536 的堆栈。

如果您在断言失败之前打印容量，您会注意到它是 65536。
看起来堆栈的大小根本没有调整过。

看你什么时候收缩存储的条件，有一个必需的条件N == arraysize / 4 .

自 N不大于 100，并且 65536/4 是 16384，这个条件永远不会成立。

替换 ==与 <=照顾它:

N <= arraysize / 4