C++ 栈（stack）模拟实现（千字详细教程）（附源码）

C++ 栈（stack）模拟实现（千字详细教程）（附源码）

引用

CSDN

1.

https://blog.csdn.net/input_me/article/details/139970788

栈（stack）是计算机科学中一种重要的数据结构，广泛应用于函数调用、表达式求值等场景。本文将详细介绍如何使用C++单链表来模拟实现栈的基本功能，包括元素的压栈、弹栈、查看栈顶元素等操作。

栈简介

栈是一种后入先出（LIFO）的数据结构，就像一叠盘子，最后放进去的盘子总是最先被取出来。在C++中，虽然标准库提供了<stack>头文件来实现栈，但为了更好地理解栈的工作原理，本文将使用单链表来模拟实现栈。

栈的实现

环境配置

本实现基于VS2022，C++标准为C++20。

单链表节点设计

为了使栈能够存储不同类型的数据，我们将使用C++的模板特性。定义一个泛型节点结构体：

template <typename T>
struct node {
    T data;        // 存储的数据
    node<T>* last; // 指向上一个节点的指针
};

栈类设计

栈类需要实现以下功能：

• size()：返回栈中元素的数量
• empty()：检查栈是否为空
• top()：返回栈顶元素
• push()：向栈顶添加元素
• pop()：从栈顶删除元素

栈类框架

template <typename T>
class stack {
public:
    stack() {
        s = 0;
        t = nullptr;
    }
    ~stack();
    T push(T& type);
    T pop();
    T top();
    int size();
    bool empty();
private:
    int s; // 元素数量
    node<T>* t; // 栈顶指针
};

方法实现

1. size() 和 empty() 实现

inline int size() {
    return s;
}
inline bool empty() {
    return s == 0;
}

2. top() 实现

inline T top() {
    return t->data;
}

3. push() 实现

T push(T type) {
    node<T>* n = new node<T>;
    n->last = t;
    n->data = type;
    t = n;
    s++;
    return type;
}

4. pop() 实现

T pop() {
    node<T>* d = t;
    t = d->last;
    T type = d->data;
    delete d;
    d = nullptr;
    s--;
    return type;
}

5. 析构函数实现

~stack() {
    while (!empty())
        pop();
}

完整代码

将上述代码整合到一个头文件stack.h中：

#pragma once
namespace std {
    template <typename T>
    struct node {
    public:
        T data;
        node<T>* last;
    };
    template <typename T>
    class stack {
    public:
        stack() {
            s = 0;
            t = nullptr;
        }
        ~stack() {
            while (!empty())
                pop();
        }
        T push(T type) {
            node<T>* n = new node<T>;
            n->last = t;
            n->data = type;
            t = n;
            s++;
            return type;
        }
        T pop() {
            node<T>* d = t;
            t = d->last;
            T type = d->data;
            delete d;
            d = nullptr;
            s--;
            return type;
        }
        inline T top() {
            return t->data;
        }
        inline int size() {
            return s;
        }
        inline bool empty() {
            return s == 0;
        }
    private:
        int s;
        node<T>* t;
    };
}

测试代码

#include <cstdio>
#include "stack.h"
int main() {
    std::stack<int> mystack;
    mystack.push(1);
    mystack.push(2);
    mystack.push(3);
    mystack.push(4);
    if (mystack.empty())
        printf("empty\n");
    else
        printf("not empty\n");
    printf("%d\n", mystack.pop());
    printf("%d\n", mystack.top());
    mystack.pop();
    mystack.pop();
    printf("%d\n", mystack.size());
}

测试结果：

not empty
4
3
1

完全符合预期！