博客

数据结构之栈（顺序栈和链栈）（c语言附完整代码）

  • Post author:
  • Post category:其他


文章目录



一、定义

① 栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。

② 进行数据插入的删除和操作的一端，称为

栈顶

，另一端则称为

栈底

。

③ 栈中的元素遵守

后进先出

的原则，即 LIFO原则（Last In First Out）栈也称为后进先出表。

④栈的插入操作通常称为

进栈

或者

入栈

，栈的删除操作通常称为

出栈

或

退栈

。


示意图：


在这里插入图片描述


栈的顺序存储结构称为顺序栈


声明顺序栈
 

typedef struct 
{	
	ElemType data[MaxSize];
	int top;				//栈指针
} SqStack;


栈的链式存储结构称为链栈


声明链栈
 

typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LinkStNode;



二、基本运算



顺序栈



设计顺序栈基本运算算法四要素

：



1.栈空的条件:s->top==-1;

2.栈满的条件:s->top==MaxSize-1(data数组最大下标)

3.进栈操作:先将栈顶指针top加1，然后将元素e放在栈顶指针处

4.出栈操作:先将栈顶指针处的元素取出并赋给e，然后将栈顶指针减1


初始化栈
 

void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;
}

该运算创建一个空栈，将s指向它，并将栈顶指针设置为-1。


本算法的时间复杂度为O（1）


销毁栈
 

void DestroyStack(SqStack *&s)
{
	free(s);
}

该运算用free函数释放栈s占用的空间。


本算法的时间复杂度为O（1）


判断栈是否为空
 

bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}

该运算判断栈是否为空，当s->top=-1时表示栈为空。


本算法的时间复杂度为O（1）


进栈操作
 

bool Push(SqStack *&s,ElemType e)
{
	if (s->top==MaxSize-1)    //栈满的情况，即栈上溢出
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}

该运算插入一个数据元素，首先判断栈是否为已满，如果栈已满则返回 false，在栈不满的条件下先将栈顶指针增1，然后在该位置插入元素e，最后返回 true。


动画演示：


在这里插入图片描述


本算法的时间复杂度为O（1）


出栈操作
 

bool Pop(SqStack *&s,ElemType &e)
{
	if (s->top==-1)		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
}

该运算删除一个数据元素，首先判断栈是否为空，如果为空则返回false，在栈不为空的条件下先将栈顶元素赋给e，然后再将栈顶指针减1，最后返回 true。


动画演示：


在这里插入图片描述


本算法的时间复杂度为O（1）


取栈顶元素
 

bool GetTop(SqStack *s,ElemType &e)
{
	if (s->top==-1) 		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	return true;
}

该运算在栈不为空的的条件下将栈顶元素赋给e并返回 true，如果栈为空则返回false。


本算法的时间复杂度为O（1）



链栈



设计链栈(带头结点)基本运算算法四要素

：



1.栈空的条件:s->next==NULL

2.栈满的条件:由于只有内存溢出时才出现栈满，通常不考虑这样的情况，所以在链栈中可以看成不存在栈满

3.进栈操作:首先新建一个结点存放元素e(由p指向它)，将结点p插入到头结点之后

4.出栈操作:取出首结点的值并将其删除


初始化栈
 

void InitStack(LinkStNode *&s)
{
	s=(LinkStNode *)malloc(sizeof(LinkStNode));
	s->next=NULL;
}

该运算创建一个空栈，就是创建链栈的头结点 并将其next域置为NULL。


本算法的时间复杂度为O（1）


销毁栈
 

void DestroyStack(LinkStNode *&s)
{
	LinkStNode *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}

该运算释放链栈s占用的全部结点空间，和单链表的销毁算法相同。


本算法的时间复杂度为O（n）


判断栈是否为空
 

bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}

该运算判断栈是否为空，就是判断s->next=NULL是否成立。


本算法的时间复杂度为O（1）


进栈操作
 

void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		//插入p结点作为开始结点
	s->next=p;
}

首先新建一个结点，用来存放元素e(由指针p指向它)，然后将其插入到头结点之后(此处类似于创建单链表时的头插法)，最后返回true。


本算法的时间复杂度为O（1）


出栈操作
 

bool Pop(LinkStNode *&s,ElemType &e)
{
	LinkStNode *p;
	if (s->next==NULL)		//栈空的情况
		return false;
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);				//释放p结点
	return true;
}

首先判断栈是否为空，如果为空则返回false，在栈不为空的条件下将首结点的值赋给e(

此处e为引用型参数)

，然后将其删除，最后返回true。


本算法的时间复杂度为O（1）


取栈顶元素
 

bool GetTop(LinkStNode *s,ElemType &e)
{
	if (s->next==NULL)		//栈空的情况
		return false;
	e=s->next->data;
	return true;
}

首先判断栈是否为空，如果为空则返回false，在栈不为空的条件下将首结点的数据域赋给e(

e为引用型参数

)，最后返回true。


本算法的时间复杂度为O（1）



三 、小结

在这里插入图片描述



四 、完整代码



顺序栈

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int top;				//栈指针
} SqStack;					//顺序栈类型
void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;
} 
void DestroyStack(SqStack *&s)
{
	free(s);
}
bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
	if (s->top==MaxSize-1)    //栈满的情况，即栈上溢出
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
	if (s->top==-1)		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
} 
bool GetTop(SqStack *s,ElemType &e)
{
	if (s->top==-1) 		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	return true;
}
int main()
{
	SqStack *s;     //定义一个栈
	InitStack(s);   //初始化栈 
	ElemType e;
	Push(s,1);
	Push(s,2);
	Push(s,3);
	GetTop(s,e);    // 取栈顶元素
	printf("当前栈顶元素为:%d\n",e);
	Pop(s,e);
	printf("出栈元素为:%d\n",e);
	printf("当前栈是否为空:%d\n",StackEmpty(s));
	DestroyStack(s);
	return 0;	
}



链栈

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LinkStNode;					//链栈类型
void InitStack(LinkStNode *&s)
{
	s=(LinkStNode *)malloc(sizeof(LinkStNode));
	s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
	LinkStNode *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		//插入p结点作为开始结点
	s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{	LinkStNode *p;
	if (s->next==NULL)		//栈空的情况
		return false;
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);				//释放p结点
	return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{	if (s->next==NULL)		//栈空的情况
		return false;
	e=s->next->data;
	return true;
}
int main()
{
	LinkStNode *s;    //定义一个栈
	InitStack(s);     //初始化栈 
	ElemType e;
	Push(s,1);         //进栈1 
	Push(s,2);         //进栈2 
	Push(s,3);         //进栈3 
	GetTop(s,e);       // 取栈顶元素
	printf("当前栈顶元素为:%d\n",e);
	Pop(s,e);
	printf("出栈元素为:%d\n",e);
	printf("当前栈是否为空:%d\n",StackEmpty(s));
	DestroyStack(s);
	return 0;	
}

参考资料

李春葆《数据结构教程》（第五版）


版权声明：本文为m0_62795460原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。