C++ 栈（stack）模拟实现（千字详细教程）（附源码）
C++ 栈（stack）模拟实现（千字详细教程）（附源码）
栈简介
众所周知，栈（stack）是计算机技术中不可或缺的一部分，在函数调用（尤其是递归）等方面发挥了不可或缺的作用。栈，是一种后入先出的数据结构，先进去的反而后出来。就像这样：
栈在C++中其实是有现成实现的，在
有的小伙伴可能要问了：搞那么麻烦干什么？用数组，再维护一个栈顶下标不就好了吗？
这里，就不得不提到栈的优点——它数据存取速度快。数组插入、删除操作时间复杂度是O(N)，而栈的是O(1)。而在特定的问题中，栈完全够用，但是数组的功能有冗余，反而拖慢了速度。
栈实现
环境：VS2022/std:C++20
单链表
首先，单链表会写吧？但是还有一个问题：要是直接设定方法的参数与返回值的类型的话，我们的node就只能适应一种类型。众所周知，结构体不能重载，同时编写int_node、float_node、double_node、char_node......也根本不切实际。因此，C++提供了泛型编程——模板。为了让node能够适应各种数据类型，我们可以使用类模板。就像这样：
template <typename T>
struct node {
......
};
注意：此处typename就是typename（也可以是class)，不是用来填的！
那么这时，我们就可以在node中把T当成正常的数据类型来使用，使得我们能够用T来定义要存储的数据。这时，node要这么用：
node<数据类型> 节点名;
所以最终，node长这样：
template <typename T>
struct node {
public:
T data; //数据
item<T>* last; //指向上一个入栈的结构体的指针
};
模拟实现栈，自然要根据
size();//查看栈中元素个数
empty();//检查栈是否为空
top();//查看栈顶元素
push();//压栈，向栈顶增加元素
pop();//弹栈，从栈顶删除元素
当然，还包括构造函数与析构函数。由于单链表的局限性，没法实现迭代器operator。
方法实现
size()
先从最简单的size()开始吧。size()方法要求我们在类内维护一个变量，我们命名为s。同时，为了计数，在构造函数中设置其初始值为零，再在push()与pop()函数中改变s的值。对了，stack类也要用上类模板。
好了，现在我们的stack类成了这样：
template <typename T>
class stack {
public:
stack() {
s = 0;
}
~stack() {
}
T push(T& type) {
s++;
}
T pop() {
s--;
}
T top() {
}
int size() {
return s;
}
bool empty() {
}
private:
int s;
};
empty()
接下来写empty()。 超级简单，只要判断s的值是不是等于0就可以了。
bool empty() {
return s == 0;
}
top()
再写top()。top()方法要求我们维护一个指向栈顶节点的指针，我们命名为t。所以，应该在构造函数中赋初值。返回值不应该是node对象，而是node中的data。我们还可以用inline来修饰上面三个极简单的函数，减少函数调用开销，使得stack类更加高效。我们现在的stack类：
template <typename T>
class stack {
public:
stack() {
s = 0;
t = NULL;
}
~stack() {
}
inline int size() {
return s;
}
inline bool empty() {
return s == 0;
}
inline T top() {
return t->type;
}
T push(T& item) {
s++;
}
T pop() {
s--;
}
private:
int s;
item<T>* t;
};
push()与pop()
实现push()与pop() ，稍微难了一点，也难不到哪儿去。
新创建一个node对象，让last指针指向栈顶节点，再让t指向新node，就能完成push()。同时，为了操控新对象，再创建一个指针，命名为n。
T push(T type) {
item<T>* n = new item<T>;
n->last = t;
n->type = type;
t = n;
s++;
return type;
}
让t等于栈顶节点的last，再删除栈顶节点，就能完成pop()。同时，为了有返回值，还得先保存栈顶节点的data，为了操控不再被t指向的栈顶节点，新创建一个指针，命名为d。
T pop() {
item<T>* d = t;
t = d->last;
T type = d->data;
delete d;
d = NULL;
s--;
return type;
}
析构函数
还缺一个析构函数，就是删除所有节点。
~stack() {
while (!empty())
pop();
}
构造函数
其实刚刚已经编好了，整理出来：
好啦！放在一个头文件stack.h里，放进std，正式完工。
成品
我的编译器没有NULL宏，就自己定义了一个。
#pragma once
#define NULL 0
namespace std {
template <typename T>
struct item {
public:
T data;
item<T>* last;
};
template <typename T>
class stack {
public:
stack() {
s = 0;
t = NULL;
}
~stack() {
while (!empty())
pop();
}
T push(T type) {
item<T>* n = new item<T>;
n->last = t;
n->data = type;
t = n;
s++;
return type;
}
T pop() {
item<T>* d = t;
t = d->last;
T type = d->data;
delete d;
d = NULL;
s--;
return type;
}
inline T top() {
return t->data;
}
inline int size() {
return s;
}
inline bool empty() {
return s == 0;
}
private:
int s;
item<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
完全符合预期！