C++如何实现Stack方法

栈（Stack）是一种常见的数据结构，它遵循后进先出（LIFO）的原则。栈的基本操作包括压栈（Push）、弹栈（Pop）、查看栈顶元素（Top）和判断栈是否为空（Empty）。在C++中，栈可以通过多种方式实现，本文将介绍如何使用数组和链表来实现栈，并讨论C++标准库中的std::stack容器。

1. 使用数组实现栈

数组是一种简单且高效的数据结构，可以用来实现栈。以下是使用数组实现栈的示例代码：

#include <iostream>
#define MAX_SIZE 100  // 定义栈的最大容量

class Stack {
private:
    int arr[MAX_SIZE];  // 用于存储栈元素的数组
    int top;           // 栈顶指针

public:
    Stack() {
        top = -1;  // 初始化栈顶指针为-1，表示栈为空
    }

    // 压栈操作
    void push(int value) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow!" << std::endl;
            return;
        }
        arr[++top] = value;  // 将元素压入栈顶
    }

    // 弹栈操作
    void pop() {
        if (top < 0) {
            std::cout << "Stack Underflow!" << std::endl;
            return;
        }
        top--;  // 栈顶指针减1，表示弹出栈顶元素
    }

    // 查看栈顶元素
    int peek() {
        if (top < 0) {
            std::cout << "Stack is Empty!" << std::endl;
            return -1;
        }
        return arr[top];  // 返回栈顶元素
    }

    // 判断栈是否为空
    bool isEmpty() {
        return top < 0;  // 如果栈顶指针为-1，栈为空
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.peek() << std::endl;  // 输出30
    stack.pop();
    std::cout << "Top element after pop: " << stack.peek() << std::endl;  // 输出20

    return 0;
}

代码说明：

• arr[MAX_SIZE]：用于存储栈元素的数组。
• top：栈顶指针，初始值为-1，表示栈为空。
• push(int value)：将元素压入栈顶，如果栈已满则输出“Stack Overflow!”。
• pop()：弹出栈顶元素，如果栈为空则输出“Stack Underflow!”。
• peek()：返回栈顶元素，如果栈为空则输出“Stack is Empty!”。
• isEmpty()：判断栈是否为空。

2. 使用链表实现栈

链表是另一种常用的数据结构，可以用来实现栈。以下是使用链表实现栈的示例代码：

#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class Stack {
private:
    Node* top;  // 栈顶指针

public:
    Stack() {
        top = nullptr;  // 初始化栈顶指针为nullptr，表示栈为空
    }

    // 压栈操作
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;  // 新节点的next指向当前栈顶
        top = newNode;        // 更新栈顶指针
    }

    // 弹栈操作
    void pop() {
        if (top == nullptr) {
            std::cout << "Stack Underflow!" << std::endl;
            return;
        }
        Node* temp = top;  // 临时保存栈顶节点
        top = top->next;   // 更新栈顶指针
        delete temp;       // 释放原栈顶节点
    }

    // 查看栈顶元素
    int peek() {
        if (top == nullptr) {
            std::cout << "Stack is Empty!" << std::endl;
            return -1;
        }
        return top->data;  // 返回栈顶元素
    }

    // 判断栈是否为空
    bool isEmpty() {
        return top == nullptr;  // 如果栈顶指针为nullptr，栈为空
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.peek() << std::endl;  // 输出30
    stack.pop();
    std::cout << "Top element after pop: " << stack.peek() << std::endl;  // 输出20

    return 0;
}

代码说明：

• Node类：表示链表中的节点，包含数据域data和指向下一个节点的指针next。
• Stack类：包含栈顶指针top，初始化为nullptr。
• push(int value)：创建一个新节点，并将其插入到链表头部，更新栈顶指针。
• pop()：删除链表头部节点，更新栈顶指针。
• peek()：返回链表头部节点的数据。
• isEmpty()：判断栈是否为空。

3. 使用C++标准库中的std::stack

C++标准库提供了std::stack容器，它封装了栈的基本操作，使用起来非常方便。以下是使用std::stack的示例代码：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.top() << std::endl;  // 输出30
    stack.pop();
    std::cout << "Top element after pop: " << stack.top() << std::endl;  // 输出20

    return 0;
}

代码说明：

• std::stack<int>：定义一个存储int类型元素的栈。
• push(int value)：将元素压入栈顶。
• pop()：弹出栈顶元素。
• top()：返回栈顶元素。

4. 总结

本文介绍了三种在C++中实现栈的方法： 1. 使用数组：简单高效，但需要预先分配固定大小的内存。 2. 使用链表：动态分配内存，适合元素数量不确定的场景。 3. 使用std::stack：C++标准库提供的容器，使用方便，推荐在大多数情况下使用。

根据具体需求选择合适的方法来实现栈，可以提高代码的效率和可维护性。