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

前言

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

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

传送门—>线性表的顺序储存结构.

传送门—>线性表的链式储存结构.

1.栈

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

（1）顺序栈

在这里插入图片描述

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

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

1.栈的结构定义

#include<stdio.h>#include<stdbool.h>//bool（布尔类型的头文件） #definestacksize200//定义数组大小为20typedefbool Status;//表示状态 typedefint Elemtype;//int类型别名typedefstruct{
    Elemtype data[stacksize];//数据域 
    Elemtype top;//栈顶指针 }My_Stack;

2.元素访问

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

3.初始化栈

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

4.判断栈是否为空

Status stackempty(My_Stack s)//判断栈是否为空 {if(s.top ==-1)returntrue;elsereturnfalse;}

5.清空栈

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

6.计算栈中元素的个数

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

7.获得栈顶元素

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

8.进栈操作Push

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

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

9.出栈操作Pop

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

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

10.遍历栈中元素并进行打印

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

11.顺序栈完整代码示例

#include<stdio.h>#include<stdbool.h>//bool（布尔类型的头文件） #definestacksize200//定义数组大小为20typedefbool Status;//表示状态 typedefint Elemtype;//int类型别名typedefstruct{
    Elemtype data[stacksize];//数据域 
    
    Elemtype top;//栈顶指针 }My_Stack;voidvisit(Elemtype e)//访问栈中的元素 {printf("%d ", e);}
Status initstack(My_Stack *s)//初始化栈 {//这里没有给data申请空间建应该是因为数组的大小已经定义完成 
    s -> top =-1;returntrue;}
Status stackempty(My_Stack s)//判断栈是否为空 {if(s.top ==-1)returntrue;elsereturnfalse;} 
Status ClearStack(My_Stack *s)//将栈清空 { 
        s -> top =-1;returntrue;}
Elemtype length(My_Stack s)//计算栈中元素的个数 {return s.top +1;}
Status getTop(My_Stack s, Elemtype *e)//获得栈顶元素 {if(s.top ==-1)returnfalse;else*e = s.data[s.top];returntrue;}
Status push(My_Stack *s, Elemtype e)//元素e入栈 {if(s -> top == stacksize -1)returnfalse;else{
        s -> top++;//栈顶指针加一 
        s -> data[s -> top]= e;//将新元素赋给栈顶元素，新插入的元素进栈 ， returntrue;}}
Status traverse(My_Stack s)//遍历栈中元素并进行打印 {int i =0;while(i <= s.top)visit(s.data[i++]);printf("\n");returntrue;} 
Status pop(My_Stack *s, Elemtype *e)//栈顶元素出栈 {if(s -> top ==-1)returnfalse;else{*e = s -> data[s -> top];
        s -> top--;//栈顶指针减一 returntrue;}}intmain(){
    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 \n\n", e);if(stackempty(s)){printf("弹出栈顶元素之后的栈变为空\n\n");}else{printf("弹出栈顶元素之后的栈不为空\n\n");}getTop(s,&e);//获取栈顶元素 printf("栈顶元素 TopElem = %d 栈的长度为 %d \n\n", e,length(s));printf("进行清空栈操作");ClearStack(&s);//清空栈 if(stackempty(s)){printf("清空栈后，栈空\n\n");}else{printf("清空栈后，栈不空\n\n");}return0;}

顺序栈测试结果

在这里插入图片描述

(2)链栈

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

1.//链栈的抽象数据类型定义

#defineOK1#defineERROR0usingnamespace std;typedefint Status;typedefint ElemType;//链栈的抽象数据类型定义 typedefstructStackNode{
     ElemType data;structStackNode*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;//修改栈顶指针为preturn 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<<p->data<<" ";
         p=p->next;} 
      cout<<endl;}

7.//返回栈的长度

intStackLen(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<iostream>#include<malloc.h>#defineOK1#defineERROR0usingnamespace std;typedefint Status;typedefint ElemType;//链栈的抽象数据类型定义 typedefstructStackNode{
     ElemType data;structStackNode*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;//修改栈顶指针为preturn 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;return0;}//遍历栈中元素
 ElemType GetElem(LinkStack S){
     LinkStack p=S;//定义一个指针p； while(p){
         cout<<p->data<<" ";
         p=p->next;} 
      cout<<endl;return OK;}//返回栈的长度intStackLen(LinkStack S){int len=0;
     LinkStack p=S;while(p){
         len++;
         p=p->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;}intmain(){
    LinkStack S; 
    
    ElemType e;InitStack(S); 
    
    cout<<"进行入栈操作"<<endl;
    
    cout<<endl;for(int i=1;i<150;i+=10){Push(S,i);//入栈 } 
     cout<<"此时的栈顶为: "<<GetTop(S)<<endl;
     cout<<endl;
     
     cout<<"由栈顶到栈底遍历栈中元素"<<endl ;GetElem(S);
    cout<<endl;
    
    cout<<"此时栈的长度为"<<StackLen(S)<<endl ;
    cout<<endl;Pop(S,e);
    
    cout<<"Pop后的栈顶为: "<<GetTop(S)<<endl;
     cout<<endl;
     
     cout<<"Pop后由栈顶到栈底遍历栈中元素"<<endl ;GetElem(S);
    cout<<endl;
    
    cout<<"此时栈的长度为"<<StackLen(S)<<endl<<endl; 
    cout<<"清空栈操作"<<endl;StackClear(S);
    cout<<"此时栈的长度为"<<StackLen(S)<<endl ;return0;}

10.链栈运行结果

在这里插入图片描述

标签：数据结构链表 c语言

本文转载自: https://blog.csdn.net/qq_59708493/article/details/122266805
版权归原作者 Domo泷 所有，如有侵权，请联系我们删除。

疫情封校，在宿舍学习数据结构——栈(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)详解(实例代码&&各接口代码）”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航

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

目录

前言

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

发表评论

“疫情封校，在宿舍学习数据结构&mdash;&mdash;栈(Stack)详解(实例代码&amp;&amp;各接口代码）”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航

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

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