数据结构（二）

数据结构（二）—栈

一、栈的概念及特点

概念

栈（stack）是限定仅在表尾进行插入或删除操作的线性表，其表尾端称为栈顶（top），表头端称为栈底（bottom），不含元素的空表称为空栈。

特点

后进先出（LIFO，Last In First Out）

基本操作

初始化
入栈
出栈
取栈顶元素

分类

根据存储结构不同，我们又可以把栈分为顺序栈和链栈

下面我们分别来实现这两种存储结构的栈。

二、顺序栈实现

顺序栈一般是用数组来实现，存在两个指针，栈顶、栈底指针，分别指向数组的尾部和头部，如下图：

栈空的条件即是top==base。比较好理解，下面直接上代码：

存储结构

//栈-顺序栈实现
#include<iostream>
using namespace std;

int const N=100;
//顺序栈的存储结构
typedef int SElemType;
typedef struct 
{
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stackSize;//栈可用的最大容量
}SqStack;

初始化

//栈初始化
void InitStack(SqStack &s)
{
	s.base=new int[N];//为顺序栈动态分配一个最大容量为N的数组空间
	s.top=s.base;//top初始为base，表示空栈
	s.stackSize=N;//stacksize置为栈的最大容量N
}

入栈

//入栈，插入元素data为新的栈顶元素
void Push(SqStack &s, SElemType data)
{
	if(s.top-s.base==s.stackSize)
	{//栈满 
		cout<<"栈已满！"<<endl;
		return;
	}
	*s.top=data;//将元素data入栈
	*s.top++;//栈顶指针加1
}

出栈

//出栈，删除栈顶元素，用data返回其值
void Pop(SqStack &s,SElemType &data)
{
	if(s.base==s.top)
	{
		cout<<"栈为空！"<<endl;
		return;
	}
    data=*s.top;
	*s.top--;//栈顶指针减1
}

取栈顶元素

//返回s的栈顶元素，不修改栈顶指针
int GetTop(SqStack &s)
{
	if(s.base!=s.top)//栈非空
		return *(s.top-1);
}

验证

int main()
{
	SqStack myStack;
	InitStack(myStack);
	Push(myStack,1);
	Push(myStack,2);
	Push(myStack,3);//将1，2，3依次入栈
	cout<<"栈顶元素："<<GetTop(myStack)<<endl;//获取当前栈顶元素
	int a;
	Pop(myStack,a);//出栈
	cout<<"弹出栈顶元素后，现栈顶元素为"<<GetTop(myStack)<<endl;//获取当前栈顶元素
	return 0;
}

运行以上代码后，运行结果如下：

三、链栈实现

链栈一般采用单链来表示：

存储结构

//链栈实现
#include<iostream>
using namespace std; 

//链栈的存储结构
typedef char ElemType;
typedef struct StackNode
{
	ElemType Data;//数据域
	StackNode *Next;//指针域
}StackNode,*LinkStack;

初始化

//初始化，构造一个空栈S，栈顶指针置空
void InitStack(LinkStack &S) 
{
	S=NULL;
}

入栈

与顺序站不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间，如下图：

//入栈，在栈顶插入元素data
void Push(LinkStack &S,ElemType data)
{
	StackNode *p=new StackNode();//生成新结点
	p->Data=data;//将新节点数据域置为data
	p->Next=S;//将新节点插入栈顶
	S=p;//修改栈顶指针为p
}

出栈

和顺序栈一样，出栈是需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间，如下图：

//出栈，删除S的栈顶元素，并用data返回其值
void Pop(LinkStack &S,ElemType &data)
{
	if(S==NULL)
	{//栈为空
		cout<<"栈为空！"<<endl;
		return;
	}
	data=S->Data;//将栈顶元素赋给data
	StackNode *p=S;//用p临时保存栈顶元素空间，以备释放
	S=S->Next;//修改栈顶元素
	delete p;//释放原栈顶元素的空间 
}

取栈顶元素

//返回S栈顶元素，不修改栈顶指针
ElemType GetTop(LinkStack &S)
{
	if(S!=NULL)//栈非空
		return S->Data;
}

验证

//打印栈 
void PrintStack(LinkStack &S)
{
	if(S!=NULL)
	{
		StackNode *p=S;
		while(p!=NULL)
		{
			cout<<p->Data<<"	";
			p=p->Next;
		}
		cout<<"
";
	}
}

int main()
{
	LinkStack LS;
	InitStack(LS);//初始化栈
	Push(LS,'a');
	Push(LS,'b');
	Push(LS,'C');//将a b C依次入栈
	PrintStack(LS);//打印当前栈
	ElemType a;
	Pop(LS,a);//将C出栈
	PrintStack(LS);//打印当前栈
	cout<<"栈顶元素为："<<GetTop(LS);//当前栈顶元素元素
	return 0;
}

运行结果如下：

四、总结

栈的实现相对来说比较简单，主要掌握顺序栈和链栈的实现即可~

参考资料：《数据结构（C语言）（第2版）》严蔚敏等著

写文不易~因此做以下申明：

1.博客中标注原创的文章，版权归原作者煦阳（本博博主）所有；

2.未经原作者允许不得转载本文内容，否则将视为侵权；

3.转载或者引用本文内容请注明来源及原作者；

4.对于不遵守此声明或者其他违法使用本文内容者，本人依法保留追究权等。