疫情封校，在宿舍学习数据结构——栈(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.栈

栈（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.链栈运行结果

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

C/C++/C#相关栏目本月热门文章