C/C++数据结构之堆栈（Stack）：理解、实现与运用_c++ stack

当我们讨论堆栈时，我们首先需要了解它的概念和基本原理。堆栈是一种后进先出（Last In, First Out，LIFO）的数据结构，它的操作主要包括压栈（Push）和弹栈（Pop），以及查看栈顶元素（Top）。这种数据结构常用于解决与函数调用、表达式求值和回溯算法相关的问题。

堆栈是计算机科学中一种重要的数据结构，它遵循“后进先出”（Last In, First Out，LIFO）的原则，就像我们堆放书籍一样，最后放入的书籍最先取出。在本文中，我们将深入讨论堆栈的概念、抽象堆栈、顺序栈、链栈以及堆栈在数制转换中的应用，并通过详细的代码例子进行解释。

1. 堆栈的概念

堆栈是一种线性数据结构，具有两个基本操作：压栈（Push）和弹栈（Pop）。压栈表示将元素放入堆栈顶部，而弹栈表示从堆栈顶部取出元素。堆栈的典型应用包括函数调用、表达式求值和回溯算法等。

2. 抽象堆栈

在讨论具体实现之前，让我们先来看看抽象堆栈的接口：

template <typename T>
class AbstractStack {
public:
    virtual void push(const T& value) = 0;
    virtual void pop() = 0;
    virtual T top() const = 0;
    virtual bool isEmpty() const = 0;
    virtual size_t size() const = 0;
};

这个抽象类定义了堆栈的基本操作，我们将通过不同的实现来具体化这些操作。

3. 顺序栈及其典型成员函数

顺序栈是使用数组实现的堆栈，下面是顺序栈的实现：

template <typename T>
class ArrayStack : public AbstractStack<T> {
private:
    static const size_t MAX_SIZE = 100;
    T data[MAX_SIZE];
    size_t topIndex;
 
public:
    ArrayStack() : topIndex(0) {}
 
    void push(const T& value) override {
        if (topIndex < MAX_SIZE) {
            data[topIndex++] = value;
        } else {
            // 栈满，抛出异常或进行扩容等处理
        }
    }
 
    void pop() override {
        if (!isEmpty()) {
            --topIndex;
        } else {
            // 栈空，抛出异常或进行其他处理
        }
    }
 
    T top() const override {
        if (!isEmpty()) {
            return data[topIndex - 1];
        } else {
            // 栈空，抛出异常或进行其他处理
            return T();
        }
    }
 
    bool isEmpty() const override {
        return topIndex == 0;
    }
 
    size_t size() const override {
        return topIndex;
    }
};

4. 链栈及其典型成员函数

链栈是使用链表实现的堆栈，下面是链栈的实现：

template <typename T>
struct Node {
    T data;
    Node* next;
    Node(const T& value) : data(value), next(nullptr) {}
};
 
template <typename T>
class LinkedStack : public AbstractStack<T> {
private:
    Node<T>* topNode;
 
public:
    LinkedStack() : topNode(nullptr) {}
 
    void push(const T& value) override {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = topNode;
        topNode = newNode;
    }
 
    void pop() override {
        if (!isEmpty()) {
            Node<T>* temp = topNode;
            topNode = topNode->next;
            delete temp;
        } else {
            // 栈空，抛出异常或进行其他处理
        }
    }
 
    T top() const override {
        if (!isEmpty()) {
            return topNode->data;
        } else {
            // 栈空，抛出异常或进行其他处理
            return T();
        }
    }
 
    bool isEmpty() const override {
        return topNode == nullptr;
    }
 
    size_t size() const override {
        size_t count = 0;
        Node<T>* current = topNode;
        while (current != nullptr) {
            ++count;
            current = current->next;
        }
        return count;
    }
};

5. 堆栈数制转换问题

堆栈在数制转换中有着广泛的应用，我们以十进制到二进制的转换为例来演示：

std::string decimalToBinary(int decimal) {
    LinkedStack<int> stack;
    while (decimal > 0) {
        stack.push(decimal % 2);
        decimal /= 2;
    }
 
    std::string binary;
    while (!stack.isEmpty()) {
        binary += std::to_string(stack.top());
        stack.pop();
    }
 
    return binary.empty() ? "0" : binary;
}

通过堆栈的压栈和弹栈操作，我们可以轻松实现十进制到二进制的转换。

这是一篇关于C/C++数据结构之堆栈（Stack）的详细文章，覆盖了堆栈的概念、抽象堆栈、顺序栈、链栈以及堆栈在数制转换中的应用。如果你想进一步了解堆栈相关的资源和知识点，以下是一些可能有帮助的链接：

1. 堆栈的概念和基本原理：

   • 堆栈 - 维基百科

2. C++ 模板类及虚函数的使用：

   • C++ Templates

3. 顺序栈的实现：

   • C++ 标准模板库（STL）

4. 链栈的实现：

   • C++ 链表详解

5. 堆栈在数制转换中的应用：

   • 进制转换算法

6. 其他相关资源：

   • 《数据结构与算法分析》 - Mark Allen Weiss（书籍）

请注意，链接的内容可能会有更新，建议查看最新的文档和教程。希望这些资源对你深入理解堆栈及其在C/C++中的应用有所帮助。