构建数组栈类

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>

using namespace std;

// 改变一个一维数组的长度
template<class T>
void changeLength1D(T *&a, int oldLength, int newLength) {
    if (newLength < 0)
        cerr << "new Length must be > 0";
    T *temp = new T[newLength];
    int number = min(oldLength, newLength);
    copy(a, a + number, temp);
    delete[]a;
    a = temp;
}

template<class T>
class arrayStack {
public:
    explicit arrayStack(int initialCapacity = 10);

    ~arrayStack() { delete[] stack; }

    int illegalParameterValue(const string &s) {
        cout << s << endl;
        return -1;
    }

    [[maybe_unused]] [[nodiscard]] bool empty() const { return stackTop == -1; }

    [[maybe_unused]] [[nodiscard]] int size() const { return stackTop + 1; }

    [[maybe_unused]] T &top() {
        if (stackTop == -1)
            throw illegalParameterValue("Stack Empty");
        return stack[stackTop];
    }

    void pop() {
        if (stackTop == -1)
            throw illegalParameterValue("Stack Empty");
        stack[stackTop--].~T();
    }

    void push(const T &theElement);

    [[nodiscard]] int getStackTop() const;

    [[maybe_unused]] [[nodiscard]] int getArrayLength() const;

    T *getStack() const;;

private:
    int stackTop; // 当前栈顶
    int arrayLength; // 栈容量

    T *stack; // 元素数组
};

template<class T>
arrayStack<T>::arrayStack(int initialCapacity) {
    // 构造函数
    if (initialCapacity < 1)
        throw illegalParameterValue("initialCapacity must be > 0");
    arrayLength = initialCapacity;
    stack = new T[arrayLength];
    stackTop = -1;
}

template<class T>
void arrayStack<T>::push(const T &theElement) {
    // 将元素压入栈
    if (stackTop == arrayLength - 1) {
        // 空间已满，容量加倍
        changeLength1D(stack, arrayLength, arrayLength * 2);
        arrayLength *= 2;
    }
    // 在栈顶插入
    stack[++stackTop] = theElement;
}

template<class T>
int arrayStack<T>::getStackTop() const {
    return stackTop;
}

template<class T>
[[maybe_unused]] int arrayStack<T>::getArrayLength() const {
    return arrayLength;
}

template<class T>
T *arrayStack<T>::getStack() const {
    return stack;
}

template<class T>
ostream &operator<<(ostream &out, arrayStack<T> &stack) {
    int stackTop = stack.getStackTop();
    T *element = stack.getStack();
    for (int i = stackTop; i >= 0; --i)
        out << element[i] << ' ';
    return out;

}

int main() {
    auto *stack1 = new arrayStack<int>(20);
    for (int i = 0; i < 20; ++i)
        stack1->push(i);
    cout << *stack1<<"所储存数据Size："<<stack1->size() << endl;
    stack1->pop();
    cout << *stack1<<"所储存数据Size："<<stack1->size() << endl;
    cout<<"栈顶元素"<<endl;
    cout << stack1->top() << endl;
    return 0;
}

运行结果

1
2
3
4
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 所储存数据Size：20
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 所储存数据Size：19
栈顶元素
18

构建数组栈类#

代码#

运行结果#

构建数组栈类

代码

运行结果