用C++实现链式栈(以链表为底层数据结构)

C++实现链式栈

1.何为链式栈?

既栈中的每个元素在内存中的分配不是连续的,元素之间的连接是通过每个元素节点中的一个指针实现。如下图:
用C++实现链式栈(以链表为底层数据结构)
可以看出,将链表的头部作为了栈顶。

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。

用C++实现链式栈(以链表为底层数据结构)

  1. Pop():

第一步:先用临时变量tmp保存栈顶的下一个地址;
第二步:释放top的内存,
第三步:让top指向第一步保存的地址。
用C++实现链式栈(以链表为底层数据结构)

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

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

上一篇:C 链式栈


下一篇:Day25.C提高(数据机构02)