C++如何实现顺序栈(使用模板类)

什么是顺序栈？

顺序栈是一种使用数组存储数据的栈。在顺序栈中，栈顶指针指向存储栈顶元素的位置，栈顶指针的下标为 0 时表示栈为空。

如何实现顺序栈？

1.定义模板类

顺序栈可以通过 C++ 中的模板类来实现，这样可以使其具备更好的可扩展性和复用性。下面是一个使用模板类实现顺序栈的示例代码：

template <class T>
class SequenceStack {
public:
    SequenceStack() {}
    ~SequenceStack() {}
    bool isEmpty() const { return top == -1; }
    bool isFull() const { return top + 1 == maxsize; }
    int getLength() const { return top + 1; }
    void push(const T& item);
    T pop();
    T getTop() const;
private:
    enum { maxsize = 100 };
    T data[maxsize];
    int top = -1;
};

这里定义了一个名为 SequenceStack 的模板类，其模板参数为 T。SequenceStack 存储了一个 T 类型的数组 data，数组的最大长度为 maxsize。top 表示当前栈顶元素的下标，初始值为 -1，当 top = -1 时表示栈为空。

2.push 函数实现

下面是 push 函数的代码实现：

template <class T>
void SequenceStack<T>::push(const T& item) {
    if (isFull()) {
        throw std::overflow_error("SequenceStack is full");
    }
    data[++top] = item;
}

如果栈已经满了，就抛出一个 std::overflow_error，否则将新元素插入到 data[top+1] 位置，然后将 top 的值加 1。

3.pop 函数实现

下面是 pop 函数的代码实现：

template <class T>
T SequenceStack<T>::pop() {
    if (isEmpty()) {
        throw std::underflow_error("SequenceStack is empty");
    }
    return data[top--];
}

如果栈已经为空，就抛出一个 std::underflow_error，在否则将 top 指针指向下一个元素，然后返回栈顶元素的值。

4.getTop 函数实现

下面是 getTop 函数的代码实现：

template <class T>
T SequenceStack<T>::getTop() const {
    if (isEmpty()) {
        throw std::underflow_error("SequenceStack is empty");
    }
    return data[top];
}

如果栈已经为空，就抛出一个 std::underflow_error，在否则返回栈顶元素的值。

示例代码

示例 1：顺序栈的基本操作

我们可以使用下面的代码来测试 SequenceStack 类的基本操作：

#include <iostream>
#include "SequenceStack.hpp"

int main() {
    SequenceStack<int> stack;
    std::cout << "isEmpty? " << stack.isEmpty() << std::endl;
    std::cout << "push 1" << std::endl;
    stack.push(1);
    std::cout << "get top item: " << stack.getTop() << std::endl;
    std::cout << "push 2, 3, 4" << std::endl;
    stack.push(2);
    stack.push(3);
    stack.push(4);
    std::cout << "pop item: " << stack.pop() << std::endl;
    std::cout << "get top item: " << stack.getTop() << std::endl;
    std::cout << "push 5, 6, 7, 8, 9, 10" << std::endl;
    for (int i = 5; i <= 10; ++i) {
        stack.push(i);
    }
    std::cout << "isFull? " << stack.isFull() << std::endl;
    std::cout << "get length: " << stack.getLength() << std::endl;
    std::cout << "pop all items: ";
    while (!stack.isEmpty()) {
        std::cout << stack.pop() << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出结果：

isEmpty? 1
push 1
get top item: 1
push 2, 3, 4
pop item: 4
get top item: 3
push 5, 6, 7, 8, 9, 10
isFull? 1
get length: 10
pop all items: 10 9 8 7 6 5 3 2 1

示例2：计算表达式中的数值

我们可以使用下面的代码来测试 SequenceStack 类在处理表达式时的功能：

#include <iostream>
#include <string>
#include "SequenceStack.hpp"

int evaluateExpression(const std::string& expr) {
    SequenceStack<int> stack;
    for (auto c : expr) {
        if (isdigit(c)) {
            stack.push(c - '0');
        } else {
            int r = stack.pop();
            int l = stack.pop();
            if (c == '+') {
                stack.push(l + r);
            } else if (c == '-') {
                stack.push(l - r);
            } else if (c == '*') {
                stack.push(l * r);
            } else if (c == '/') {
                stack.push(l / r);
            }
        }
    }
    return stack.pop();
}

int main() {
    std::string expr = "2 3 + 4 * 15 -";
    std::cout << "calculate expression " << expr << std::endl;
    std::cout << "result: " << evaluateExpression(expr) << std::endl;
    return 0;
}