定义:栈是限定仅在表尾进行插入和删除操作的线性表。
把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
#include <iostream>
template<typename T>
struct stack_node
{
stack_node(const T& d) : next(nullptr), data(d) {}
stack_node* next;
T data;
};
template<typename T>
class LinkStack
{
public:
LinkStack();
~LinkStack();
void mvPush(const T& d); // 入栈
void mvPop(); // 出栈
bool mbIsEmpty() { return ((miCount > 0) ? false : true); }; // 栈是否为空
int miGetCount() { return miCount; }
private:
typedef stack_node<T>* stack_type;
private:
stack_type mopTop; // 栈顶指针
int miCount; // 节点数
};
template<typename T>
LinkStack<T>::LinkStack() : mopTop(nullptr), miCount(0)
{}
template<typename T>
LinkStack<T>::~LinkStack()
{
if (mopTop != nullptr) {
stack_type tmp_node = mopTop->next;
delete mopTop;
mopTop = tmp_node;
}
}
template<typename T>
void LinkStack<T>::mvPush(const T& d)
{
// 创建新的栈节点
stack_type opNewNode = new stack_node<T>(d);
// 入栈:
// 1、把当前的栈顶元素赋值给新节点的直接后继
opNewNode->next = mopTop;
// 2、将新的节点数值给栈顶指针
mopTop = opNewNode;
// 修改栈节点总数
++miCount;
}
template<typename T>
void LinkStack<T>::mvPop()
{
// 判断栈是否为空
if (miCount == 0) {
std::cout << "error: stack is empty!" << std::endl;
}
else {
// 出栈:
// 1、将栈顶节点赋值给需要出栈的临时指针
stack_type opPopNode = mopTop;
// 2、栈顶指针指向后一节点
mopTop = mopTop->next;
// 3、释放出栈节点
delete opPopNode;
opPopNode = nullptr;
// 修改栈节点总数
--miCount;
}
}
int main()
{
LinkStack<int> ls;
ls.mvPush(1);
ls.mvPush(2);
ls.mvPop();
ls.mvPop();
system("pause");
return 0;
}