投稿
  1. 首页
  2. 随笔

疫情封校，在宿舍学习数据结构——栈(Stack)详解(实例代码&&各接口代码）

反义疑问句 • 2022-12-17 • 随笔 • 阅读 562

疫情封校，在宿舍学习数据结构——栈(Stack)详解(实例代码&&各接口代码）,第1张

疫情封校，在宿舍学习数据结构——栈(Stack)详解(实例代码&&各接口代码）

目录
  • 前言
  • 1.栈
    • （1）顺序栈
      • 1.栈的结构定义
      • 2.元素访问
      • 3.初始化栈
      • 4.判断栈是否为空
      • 5.清空栈
      • 6.计算栈中元素的个数
      • 7.获得栈顶元素
      • 8.进栈 *** 作Push
      • 9.出栈 *** 作Pop
      • 10.遍历栈中元素并进行打印
      • 11.顺序栈完整代码示例
      • 顺序栈测试结果
    • (2)链栈
      • 1.//链栈的抽象数据类型定义
      • 2.//初始化链栈
      • 3.//入栈 *** 作 Push
      • 4.//出栈 *** 作 Pop
      • 5.//得到栈顶
      • 6.//遍历打印栈中元素
      • 7.//返回栈的长度
      • 8.//清空链栈中的元素
      • 9.链栈完整代码示例
      • 10.链栈运行结果

前言

我们之前已经学习过线性表，栈（stack）和队列（queue）也属于线性表，只不过他们两个都是特殊的线性表；

栈和队列是特殊的线性表，除它两的特殊点之外，其余 *** 作和特性都与普通线性表相似，在学习栈和队列之前，我们可以先复习线性表

  1. 传送门—>线性表的顺序储存结构.
  2. 传送门—>线性表的链式储存结构.
1.栈

栈（stack）是仅限在表尾进行插入和删除 *** 作的线性表，可分为顺序栈和链栈

（1）顺序栈

顾名思义，顺序栈就是线性表的顺序储存结构，只不过他的插入和删除只能在表尾进行；

我们吧允许进行插入和删除的一端称为栈顶（top），另一端称为栈底（base）不含任何数据元素的栈称为空栈

1.栈的结构定义 
#include
#include					//bool（布尔类型的头文件） 
#define stacksize 200				//定义数组大小为20
typedef bool Status;			//表示状态 
typedef int Elemtype;		//int类型别名

typedef struct {
	Elemtype data[stacksize];			//数据域 
	Elemtype top;						//栈顶指针 
}My_Stack;
2.元素访问 
void visit(Elemtype e)			//访问栈中的元素 
{
	printf("%d ", e);
}
3.初始化栈 
Status initstack(My_Stack *s)			//初始化栈 
{
	//这里没有给data申请空间建应该是因为数组的大小已经定义完成 
	s -> top = -1;	
	return true;
}
4.判断栈是否为空 
Status stackempty(My_Stack s)			//判断栈是否为空 
{
	if(s.top == -1)
		return true;
	else 
		return false;
}
5.清空栈 
Status ClearStack(My_Stack *s) 		//将栈清空 
{ 
        s -> top = -1;
        return true;
}
6.计算栈中元素的个数 
Elemtype length(My_Stack s)		//计算栈中元素的个数 
{
	return s.top + 1;
}
7.获得栈顶元素 
Status getTop(My_Stack s, Elemtype *e)	//获得栈顶元素 
{
	if(s.top == -1)
		return false;
	else
		*e = s.data[s.top];
	return true;
}
8.进栈 *** 作Push 
Status push(My_Stack *s, Elemtype e)			//元素e入栈 
{
	if(s -> top == stacksize - 1)
		return false;
	else
	{
		s -> top++;				//栈顶指针加一 
		s -> data[s -> top] = e;		//将新元素赋给栈顶元素，新插入的元素进栈 ， 
		return true;
	 } 
}

没有涉及循环语句，时间复杂度为O(1)

9.出栈 *** 作Pop 
Status pop(My_Stack *s, Elemtype *e)		//栈顶元素出栈 
{
	if(s -> top == -1)
		return false;
	else
	{
		*e = s -> data[s -> top];
		s -> top--;			//栈顶指针减一 
		return true;
	}
}
}

没有涉及循环语句，时间复杂度为O(1)

10.遍历栈中元素并进行打印 
Status traverse(My_Stack s)		//遍历栈中元素并进行打印 
{
	int i = 0;
	while(i <= s.top)			 
		visit(s.data[i++]);
	printf("n");
}
11.顺序栈完整代码示例 
#include

#include					//bool（布尔类型的头文件） 

#define stacksize 200				//定义数组大小为20

typedef bool Status;			//表示状态 

typedef int Elemtype;		//int类型别名

typedef struct 
{
	Elemtype data[stacksize];			//数据域 
	
	Elemtype top;						//栈顶指针 
	
}My_Stack;				

void visit(Elemtype e)			//访问栈中的元素 
{
	printf("%d ", e);
}

Status initstack(My_Stack *s)			//初始化栈 
{
	//这里没有给data申请空间建应该是因为数组的大小已经定义完成 
	s -> top = -1;	
	return true;
}

Status stackempty(My_Stack s)			//判断栈是否为空 
{
	if(s.top == -1)
		return true;
	else 
		return false;
} 

Status ClearStack(My_Stack *s) 		//将栈清空 
{ 
        s -> top = -1;
        return true;
}

Elemtype length(My_Stack s)		//计算栈中元素的个数 
{
	return s.top + 1;
}

Status getTop(My_Stack s, Elemtype *e)	//获得栈顶元素 
{
	if(s.top == -1)
		return false;
	else
		*e = s.data[s.top];
	return true;
}

Status push(My_Stack *s, Elemtype e)			//元素e入栈 
{
	if(s -> top == stacksize - 1)
		return false;
	else
	{
		s -> top++;				//栈顶指针加一 
		s -> data[s -> top] = e;		//将新元素赋给栈顶元素，新插入的元素进栈 ， 
		return true;
	 } 
}

Status traverse(My_Stack s)		//遍历栈中元素并进行打印 
{
	int i = 0;
	while(i <= s.top)			 
		visit(s.data[i++]);
	printf("n");
	return true;
} 

Status pop(My_Stack *s, Elemtype *e)		//栈顶元素出栈 
{
	if(s -> top == -1)
		return false;
	else
	{
		*e = s -> data[s -> top];
		s -> top--;			//栈顶指针减一 
		return true;
	}
}

int main()
{
	My_Stack s;				
	
	int j, e;
	
	initstack(&s);

	for(j = 1;j <= 150;j+=10)
		push(&s, j);
			
	puts("进栈之后的元素依次为： ");
	
	traverse(s);
	
	pop(&s, &e); 
	
	printf("n");
	
	printf("弹出的栈顶元素为 %d nn", e);
	
	if(stackempty(s))
	{
		printf("弹出栈顶元素之后的栈变为空nn");
	}
	else
	{
		printf("弹出栈顶元素之后的栈不为空nn");
	}
    getTop(s, &e);//获取栈顶元素 
    
    printf("栈顶元素 TopElem = %d 栈的长度为 %d nn", e, length(s));
    
    printf("进行清空栈操作"); 
    
	ClearStack(&s);//清空栈 
	
	if(stackempty(s))
	{ 
		printf("清空栈后，栈空nn");
	}
	else 
	{
		printf("清空栈后，栈不空nn"); 
	}
	return 0;
}
顺序栈测试结果

(2)链栈

顾名思义，链栈就是线性表的链式储存结构
与链表的 *** 作相似

1.//链栈的抽象数据类型定义 
#define OK 1
#define ERROR 0
using namespace std; 
typedef int Status;
typedef int ElemType;
//链栈的抽象数据类型定义 
typedef struct StackNode
{
	 ElemType data;
	 
	struct StackNode *next;
	
}StackNode, *linkStack;
2.//初始化链栈 
Status InitStack(linkStack &S)
{
	//构造一个空栈，栈顶指针置为空 
	S = NULL;
	return OK;
}
3.//入栈 *** 作 Push 
Status Push(linkStack &S,ElemType e)
{
	    linkStack p;//定义p 
	    //这里使用的是C++语法new出的地址，也可使用C语言的语法malloc
		p=(linkStack)malloc(sizeof(StackNode)); //需要包含malloc头文件 
		//	p=new StackNode;//生成新结点 
		
		p->data=e;//e赋给新结点的数据域 
		
		p->next=S; //新结点插入栈顶 
		
		S=p;//修改栈顶指针为p
		
		return OK;
}
4.//出栈 *** 作 Pop 
Status Pop(linkStack &S,ElemType &e)
{
	linkStack p;//定义p 
	
	if(S==NULL) return ERROR;//栈空 
	
	e=S->data;//将栈顶元素赋给e 
	
	p=S;//p临时保存栈顶元素以备释放 
	
	S=S->next;//修改栈顶指针 
	
	free(p);//释放空间 
	
	return OK;
}
5.//得到栈顶 
ElemType GetTop(linkStack S)
{
	
	if(S!=NULL) //栈非空
	 return S->data; 
}
6.//遍历打印栈中元素 
 ElemType GetElem(linkStack S)
 {
 	linkStack p=S;//定义一个指针p； 
	 while(p)//p不断向栈尾移动
	 {
	 	cout<data<<" ";
	 	p=p->next;
	  } 
	  cout< 
7.//返回栈的长度 

 int StackLen(linkStack S)
 {
 	int len=0;
 	linkStack p=S;
	 while(p)
	 {
	 	len++;
	 	p=p->next;
	  } 
	  return len;
  } 

 
8.//清空链栈中的元素 

 Status StackClear(linkStack &S)
 {
 	linkStack p=S;//定义一个指针p； 
	 while(p)//p不断向栈尾移动，S=p，释放S 
	 {
	 	p=p->next;
	 	free(S);
	 	S=p;
	  } 
	  return OK;
 }

 
9.链栈完整代码示例 

#include

#include

#define OK 1
#define ERROR 0
using namespace std; 
typedef int Status;
typedef int ElemType;
//链栈的抽象数据类型定义 
typedef struct StackNode
{
	 ElemType data;
	 
	struct StackNode *next;
	
}StackNode, *linkStack; 
//初始化链栈 
Status InitStack(linkStack &S)
{
	//构造一个空栈，栈顶指针置为空 
	S = NULL;
	return OK;
}
//入栈 *** 作 
Status Push(linkStack &S,ElemType e)
{
	    linkStack p;//定义p 
	    //这里使用的是C++语法new出的地址，也可使用C语言的语法malloc
		p=(linkStack)malloc(sizeof(StackNode)); //需要包含malloc头文件 
		//	p=new StackNode;//生成新结点 
		
		p->data=e;//e赋给新结点的数据域 
		
		p->next=S; //新结点插入栈顶 
		
		S=p;//修改栈顶指针为p
		
		return OK;
}
//出栈 *** 作 
Status Pop(linkStack &S,ElemType &e)
{
	linkStack p;//定义p 
	
	if(S==NULL) return ERROR;//栈空 
	
	e=S->data;//将栈顶元素赋给e 
	
	p=S;//p临时保存栈顶元素以备释放 
	
	S=S->next;//修改栈顶指针 
	
	delete p;//释放空间 
	
	return OK;
} 
//得到栈顶 
ElemType GetTop(linkStack S)
{
	
	if(S!=NULL) //栈非空
	 return S->data; 
	 return 0;
}  
//遍历栈中元素
 ElemType GetElem(linkStack S)
 {
 	linkStack p=S;//定义一个指针p； 
	 while(p)
	 {
	 	cout<data<<" ";
	 	p=p->next;
	  } 
	  cout<next;
	  } 
	  return len;
  } 
 //清空链栈中的元素 
 Status StackClear(linkStack &S)
 {
 	linkStack p=S;//定义一个指针p； 
	 while(p)//p不断向栈尾移动，S=p，释放S 
	 {
	 	p=p->next;
	 	free(S);
	 	S=p;
	  } 
	  return OK;
 }
int main()
{
	linkStack S; 
	
	ElemType e; 
	
	InitStack(S); 
	
	cout<<"进行入栈操作"< 
10.链栈运行结果 

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691095.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
反义疑问句 反义疑问句 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存