本文主要是介绍用C++实现链式栈(以链表为底层数据结构)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

C++实现链式栈

• 1.何为链式栈？
• 2.顺序栈和链式栈对比
• 3.链式栈的常用操作
• 4.push()和pop()的实现详解
• 5.实例：代码中加了详细的注释

1.何为链式栈？

既栈中的每个元素在内存中的分配不是连续的，元素之间的连接是通过每个元素节点中的一个指针实现。如下图:

可以看出，将链表的头部作为了栈顶。

2.顺序栈和链式栈对比

前面已经说过顺序栈，它是用数组来实现的。可以参考用C++实现顺序栈(以数组为底层数据结构，可自动扩容)。它的缺点很明显：栈的大小总是事先定好一个长度，这样我们就无法忽视栈空间所带来的问题。尽管我们在顺序栈中加入了自动括容的功能，这样能很好的解决栈大小事先就固定好了长度的问题，但是，可以预见，当栈的使用过程中元素个数变化较大，既有时很小，有时又很大，这对内存空间的开销是很大的浪费。

相比顺序栈，链式栈不需要事先确定栈大小的问题，栈的大小随着出入栈操作不断的自己改变。而且链式栈总是一个萝卜一个坑，有一个萝卜时(Push),就生成一个坑;拔掉萝卜时(Pop)时，坑就被填满，这样就杜绝了内存空间的浪费。当然链式栈也有其局限性：每个元素都有一个指针域，这也增加了内存的开销。

3.链式栈的常用操作

链式栈的操作顺序栈一样：

• i.压栈push：将数据放入栈中
• ii.出栈pop：将栈顶数据删除
• iii.获取栈顶元素，但不删除：top();
• iV.获取当前栈的大小：size();
• V.判断栈当前的状态是否为空，既判空：empty()；

4.push()和pop()的实现详解

1. Push():
   第一步：由于栈元素是节点的形式，所以我们需要生成一个节点tmp。
   第二步：让tmp指向top；
   第三部：修改top的值，让其既top = tmp。

2. 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++实现顺序栈(以数组为底层数据结构，可自动扩容)

以上就是链式栈的介绍，本人水平与有限，欢迎各位码友批评指正。

这篇关于用C++实现链式栈(以链表为底层数据结构)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！