C++实现链式栈
1.何为链式栈？
既栈中的每个元素在内存中的分配不是连续的，元素之间的连接是通过每个元素节点中的一个指针实现。如下图:
可以看出，将链表的头部作为了栈顶。
2.顺序栈和链式栈对比
前面已经说过顺序栈，它是用数组来实现的。可以参考用C++实现顺序栈(以数组为底层数据结构，可自动扩容)。它的缺点很明显：栈的大小总是事先定好一个长度，这样我们就无法忽视栈空间所带来的问题。尽管我们在顺序栈中加入了自动括容的功能，这样能很好的解决栈大小事先就固定好了长度的问题，但是，可以预见，当栈的使用过程中元素个数变化较大，既有时很小，有时又很大，这对内存空间的开销是很大的浪费。
相比顺序栈，链式栈不需要事先确定栈大小的问题，栈的大小随着出入栈操作不断的自己改变。而且链式栈总是一个萝卜一个坑，有一个萝卜时(Push),就生成一个坑;拔掉萝卜时(Pop)时，坑就被填满，这样就杜绝了内存空间的浪费。当然链式栈也有其局限性：每个元素都有一个指针域，这也增加了内存的开销。
3.链式栈的常用操作
链式栈的操作顺序栈一样：
• i.压栈push：将数据放入栈中
• ii.出栈pop：将栈顶数据删除
• iii.获取栈顶元素，但不删除：top();
• iV.获取当前栈的大小：size();
• V.判断栈当前的状态是否为空，既判空：empty()；
4.push()和pop()的实现详解
- Push():
第一步：由于栈元素是节点的形式，所以我们需要生成一个节点tmp。
第二步：让tmp指向top；
第三部：修改top的值，让其既top = tmp。
- Pop():
第一步：先用临时变量tmp保存栈顶的下一个地址；
第二步：释放top的内存，
第三步：让top指向第一步保存的地址。
5.实例：代码中加了详细的注释
MyStack.h
#ifndef _MY_STACK_H
#define _MY_STACK_H
template<typename T>
class LinkStack;
template<typename T>
class StackNode
{
friend class LinkStack<T>;//生命栈类为节点类的友元，以便访问其私有数据
public:
StackNode(){};
StackNode(T _data) :data(_data), link(nullptr){};
~StackNode(){};
private:
T data;
StackNode<T>* link;
};
template<typename T>
class LinkStack
{
public:
LinkStack();
~LinkStack();
void Push(const T& _data);//入栈
void Pop();//删除
T& Top();//返回栈顶数据
bool Empty();//判断栈是否为空
int Size();//返回栈的大小
private:
StackNode<T> *top;//栈顶指针
int size;//栈当前的大小
};
//构造函数和析构函数
template <typename T>
LinkStack<T>::LinkStack()
:top(nullptr), size(0)
{
}
template <typename T>
LinkStack<T>::~LinkStack()
{
while (!Empty()){
Pop();
}
}
//push函数
template <typename T>
void LinkStack<T>::Push(const T& _data)
{
StackNode<T> *tmp = new StackNode<T>(_data);//生成一个新的栈元素节点，并赋初值_data
tmp->link = top;//push的元素节点指向原来的栈顶
top = tmp;//push的元素节点做为栈顶
size++;//栈的大小+1
}
//pop函数
template <typename T>
void LinkStack<T>::Pop()
{
if (!Empty()){
StackNode<T> *tmp = top->link;//保存栈顶的下一个元素，因为它将成为栈顶
delete top;
top = tmp;
size--;//栈大小-1
}
else exit(1);
}
//返回栈顶数据
template <typename T>
T& LinkStack<T>::Top()
{
if (!Empty())
return top->data;//栈不空返回栈顶数据
else
exit(1);
}
//检查栈是否为空
template <typename T>
bool LinkStack<T>::Empty()
{
if (size > 0)
return false;
else
return true;
}
//返回栈的大小
template <typename T>
int LinkStack<T>::Size()
{
return size;
}
#endif
main.cpp
#include <iostream>
#include "MyStack.h"
using namespace std;
int main()
{
LinkStack<int> st;
for (int i = 1; i <= 11; i++){
st.Push(i); //入栈
}
while (!st.Empty())
{
cout << "size = " << st.Size() << "\t"; //打印当前栈的大小
cout << "top = " << st.Top() << endl; //打印当前栈顶数据
st.Pop();//出栈
}
system("pause");
return 0;
}
测试结果：
顺序栈实现：
用C++实现顺序栈(以数组为底层数据结构，可自动扩容)
以上就是链式栈的介绍，本人水平与有限，欢迎各位码友批评指正。