[雷神宫殿钥匙],涟韵,洛克王国费米龙
栈，一个非常基础、常用的数据结构。
其用途十分广泛，如：
1. 理论上所有的递归都可以用非递归实现，其中绝大部分需要用栈。
2. 表达式求值算法中要用栈。
3. 括号匹配算法要用栈。
4. 浏览器前进后退算法要用双栈。
5. dfs 算法要用栈。
可以说用栈的地方数不胜数，因此，这是必须熟练掌握并能熟练应用的结构。
括号匹配算法：力扣第 20 题。
用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈
栈的基本规则：先进先出。
其他废话不多说，这里用 c++ 模拟一个几乎与 stl stack 一样的栈（当然会简化一些东西，链式栈）。
相关接口及注释已经写于源码中。
这是链式栈及基本操作：
源码：
我要评论#include <iostream>
#include <iomanip>
/* 链式栈 */
template<typename _ty>
class stack
{
// 定义节点结构
struct node
{
_ty data;
node* next = nullptr;
explicit node(const _ty& _data) :data(_data) {}
};
public:
stack() = default;
~stack();
// 栈是否为空
bool empty() const { return n_size == 0; } // or return p_top == nullptr
// 返回栈长度
size_t size() const { return n_size; }
// 返回栈顶数据引用
_ty& top() const;
// 压栈
void push(const _ty& _data);
// 出栈
void pop();
private:
node* p_top = nullptr;
size_t n_size = 0;
};
template<typename _ty>
stack<_ty>::~stack()
{
node* temp = p_top;
while (temp != nullptr)
{
p_top = p_top->next;
delete temp;
temp = p_top;
}
n_size = 0;
}
template<typename _ty>
_ty& stack<_ty>::top() const
{
if (p_top == nullptr) throw std::exception("stack is empty.");
else return p_top->data;
}
template<typename _ty>
void stack<_ty>::push(const _ty& _data)
{
node* temp = new node(_data);
temp->next = p_top;
p_top = temp;
temp = nullptr;
++n_size;
}
template<typename _ty>
void stack<_ty>::pop()
{
if (p_top == nullptr) return;
node* temp = p_top;
p_top = p_top->next;
delete temp;
--n_size;
}
int main()
{
std::cout.setf(std::ios_base::boolalpha);
stack<int> sk;
std::cout << "empty?: " << sk.empty() << std::endl;
std::cout << "push datas..." << std::endl;
for (int i = 0; i < 5; ++i) sk.push(i + 1);
std::cout << "now empty?: " << sk.empty() << std::endl;
std::cout << "now size: " << sk.size() << std::endl;
std::cout << "now top: " << sk.top() << std::endl;
std::cout << "pop top..." << std::endl;
sk.pop();
std::cout << "now empty?: " << sk.empty() << std::endl;
std::cout << "now size: " << sk.size() << std::endl;
std::cout << "now top: " << sk.top() << std::endl;
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论