栈的实现

简介: 栈的实现

@[toc]

本篇将讲述栈的相关知识

在之前的文章中我们学习了线性表,大家一定要掌握线性表的相关知识,这是后面内容的基础。

栈的定义

先来看看栈的定义:

栈是限定仅在表尾进行插入和删除操作的线性表。表尾一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈;从一个栈删除元素又称作出栈或退栈。

由定义可以得知,栈本质就是一个线性表,只不过栈只能在表尾进行插入和删除操作,是操作受限的线性表。
因为只能在表尾进行插入和删除,所以栈中的元素是先进后出的,也就是说,最先进栈的元素最后才出栈。

可以将栈的结构类比成子弹夹,最先压入的子弹在最底下。

下图为元素的进栈过程:
在这里插入图片描述
下图为元素的出栈过程:
在这里插入图片描述
对于入栈和出栈的理解一定要透彻,比如现在有三个元素1,2,3,其入栈顺序为1,2,3,则出栈顺序是怎样的呢?有以下几种情况:

  1. 让1先入栈,然后2入栈,最后3入栈;出栈顺序为:3,2,1
  2. 让1先入栈,1出栈,然后2入栈,2出栈,最后3入栈,3出栈;出栈顺序为:1,2,3
  3. 让1先入栈,然后2入栈,2出栈,1出栈,最后3入栈,3出栈;出栈顺序为:2,1,3
  4. 让1先入栈,然后2入栈,2出栈,最后3入栈,3出栈,1出栈;出栈顺序为:2,3,1
  5. 让1先入栈,1出栈,然后2入栈,最后3入栈,3出栈,2出栈;出栈顺序为:1,3,2

元素的入栈和出栈顺序比较灵活,大家可以自己画图理解一下。

栈的抽象数据类型定义

这个大家都有基础了,我直接贴出来就可以了。

ADT Stack{
   
   
    数据对象:D = {
   
   ai|ai∈ElemSet,i = 1,2,3,...,n-1,n,n>=0}
    数据关系:R1={
   
   <ai-1,ai>|ai-1,ai∈D,i=2,3,...,n-1,n}
    基本操作:
        InitStack();//初始化栈
        Push(int val);//入栈
        Pop(int *val);//出栈
        DestroyStack(&s);//销毁栈
        StackEmpty(s);//判断栈是否为空
        StackLength(s);//求栈的长度
        GetTop(s,&val);//获取栈顶元素
        ClearStack(&s);//清空栈
        ......
}ADT Stack

栈的顺序实现

对于栈的顺序存储,我们依然通过数组实现。
通过设置两个指针,一个top指针指示栈顶元素的位置;一个base指针指示栈底元素的位置。
不过为了操作方便,通常top指针指示的并不是栈顶元素的位置,而是栈顶元素之上的一个位置,如下图:
在这里插入图片描述
当top指向base,即:top == base的时候,表示栈为空。
而为了判断栈满的情况,我们设置一个stacksize,它表示栈的最大容量。倘若top - base`== stacksize,表示栈已满。

下面是对栈的结构定义:

#define Elemtype int

typedef struct{
   
   
    ElemType *top;    //栈顶指针
    ElemType *base;    //栈底指针
    int stacksize;    //栈的最大容量
}Stack,*PStack;

顺序栈的基本操作

下面介绍顺序栈的一些基本操作。

顺序栈的初始化

如何对顺序栈进行初始化呢?直接看代码:

void InitStack(PStack s){
   
   
    //分配一段内存
    s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(s->base == NULL){
   
   
        exit(-1);
    }
    //初始栈顶指针等于栈底指针
    s->top = s->base;
    s->stacksize = MAXSIZE;//最大容量
}

判断顺序栈是否为空

在顺序栈的定义中,我们就说道,如果知道一个顺序栈是否为空,判断栈顶指针的指向和栈底指针的指向是否相同,即:top == base,若条件成立,则表示顺序栈为空。
代码如下:

int StackEmpty(Stack s){
   
   
    if(s.top == s.base){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

求顺序栈的长度

求顺序栈的长度非常简单,让栈顶指针减栈底指针即可得到长度。
代码如下:

int StackLength(Stack s){
   
   
    return s.top - s.base;
}

清空顺序栈

清空顺序栈并不是释放栈的内存,而是清除栈内的元素,不管栈内有没有有用的元素,我们此时统统认为它们是无用的,是垃圾,所以只需将栈顶指针指向栈底即可完成顺序栈的清空。
代码如下:

void ClearStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        s->top = s->base;
    }
}

销毁顺序栈

销毁很简单,把栈的内存释放即可。
代码如下:

void DestroyStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        free(s->base);
        s->stacksize = 0;
        s->base = s->top = NULL;
    }
}

顺序栈的入栈

上面的操作比较简单,下面来看看比较复杂的操作:入栈和出栈。
假设有下面的一个顺序栈:
在这里插入图片描述
如何对该顺序栈进行入栈操作呢?
把入栈元素值赋值给top指针指向的位置,然后top指针往上移动一位。
在这里插入图片描述
还得考虑栈满的情况,也就是当top - base == stacksize时,栈满,无法入栈。
代码如下:

int    Push(PStack s,int val){
   
   
    //判断栈是否满
    if(s->top - s->base == s->stacksize){
   
   
        return -1;
    }
    //将元素val入栈
    *s->top = val;//对top指针所指的区域赋值
    //栈顶指针加1
    s->top++;
    return 1;//入栈成功,返回1
}

顺序栈的出栈

假设有如下的一个顺序表:
在这里插入图片描述
如何实现出栈呢?
top指针指向的是栈顶元素的上一个位置,所以 要想实现出栈操作,得先让top指针向下移动一位,然后取出元素:
在这里插入图片描述
当然还需要考虑栈空的情况,当栈顶指针和栈底指针指向同一个位置,即:top == base时,栈空,无法出栈。
代码如下:

int Pop(PStack s,int *val){
   
   
    //判断栈是否空
    if(StackEmpty(*s)){
   
   
        return -1;
    }
    s->top--;//将指针下移
    *val = *s->top;//元素出栈
    return 1;//出栈成功,返回1
}

初始化、入栈、出栈的操作我们都实现了,下面来测试一下:

void main(){
   
   
    Stack s,*ps;
    int val,i;
    ps = &s;
    InitStack(ps);
    Push(ps,1);
    Push(ps,2);
    Push(ps,3);

    for(i = 0;i < 3;i++){
   
   
        Pop(ps,&val);
        printf("出栈元素:%d\t",val);
    }
    getchar();
}

运行结果:

出栈元素:3    出栈元素:2    出栈元素:1

在初始化的时候,我们是通过传入一个Stack指针类型的变量ps,而ps的值是Stack类型变量s的地址,为什么要这样做呢?
因为如果直接使用变量ps,或者直接通过PStack定义出指针变量,再将该变量作为参数传入初始化函数时,程序会检测出你没有对该变量进行初始化,从而产生错误,所以必须这么做。当然,你也可以把这一步骤放到初始化函数内部进行。

栈的链式实现

下面来说一说栈的链式实现,对于链式栈,我们同样通过链表实现,对于链栈,它只能在链表头部进行操作,我们将链表头部称为栈顶,链表尾部称为栈底。
链栈的结构定义如下:

typedef struct Node{
   
   
    ElemType data;//数据域
    struct Node *next;//指针域
}Node,*Stack;

在链栈中,可以不需要头结点(增设头结点反而会使操作更复杂),那么链表的头指针其实就是栈顶指针。

链栈的基本操作

链栈的初始化

链栈的初始化非常简单,无需创建头结点,声明头指针并设初始值为NULL即可,代码如下:

Stack InitStack(){
   
   
    //构造一个空栈
    Stack s = NULL;//s为头指针,亦为栈顶指针,初始值为NULL
    return s;
}

判断链栈是否为空

判空算法也很简单,看看栈顶指针是否为NULL就可以了,代码如下:

int StackEmpty(Stack s){
   
   
    //若栈顶指针为NULL,表明栈为空
    if(s == NULL){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

关于其它的一些操作比较简单,写法类似于单链表,下面重点说一说入栈和出栈操作。

链栈的入栈操作

假设有下面的一个链栈:
在这里插入图片描述
如何实现入栈操作呢?
先让新结点p的指针域指向栈顶结点,即:p->next = s
在这里插入图片描述
然后要让新插入的结点p成为栈顶结点,即:s = p
在这里插入图片描述
此时完成入栈操作。
代码实现如下:

Stack Push(Stack s,int val){
   
   
    //创建新结点
    Stack p = (Stack) malloc(sizeof(Node));
    if(p == NULL){
   
   
        exit(-1);
    }
    p->data = val;
    //让p指向栈顶结点
    p->next = s;
    //让p成为栈顶结点
    s = p;
    return s;
}

链栈的出栈操作

假设如下的一个链栈:
在这里插入图片描述
该如何实现出栈呢?
出栈非常简单,让栈顶指针s指向下一个结点就可以了,即:s = s->next
在这里插入图片描述
但此时我们就找不到被删除的结点了,所以在改变指针指向之前,我们需要定义一个结点类型变量p存储栈顶结点,然后改变指针指向,最后释放p,完成出栈操作。
代码实现如下:

Stack Pop(Stack s,int *val){
   
   
    Stack p;
    if(s == NULL){
   
   
        printf("栈为空!");
        return s;
    }
    *val = s->data;
    //保存栈顶结点
    p = s;
    //让栈顶指针指向下一个结点
    s = s->next;
    //释放结点内存
    free(p);
    return s;//出栈成功
}

下面来测试一下:

void main(){
   
   
    Stack s;
    int val = 0,i;
    s = InitStack();
    s = Push(s,1);
    s = Push(s,2);
    s = Push(s,3);

    for(i = 0;i < 3;i++){
   
   
        s = Pop(s,&val);
        printf("出栈元素值:%d\t",val);
    }
    getchar();
}

运行结果:

出栈元素值:3    出栈元素值:2    出栈元素值:1

源代码

顺序栈代码

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 10
#define ElemType int

typedef struct{
   
   
    ElemType *top;    //栈顶指针
    ElemType *base;    //栈底指针
    int stacksize;    //栈的最大容量
}Stack,*PStack;

int Pop(PStack s,int *val){
   
   
    //判断栈是否空
    if(s->top == s->base){
   
   
        return -1;
    }
    s->top--;//将指针下移
    *val = *s->top;//元素出栈
    return 1;//出栈成功,返回1
}

int    Push(PStack s,int val){
   
   
    //判断栈是否满
    if(s->top - s->base == s->stacksize){
   
   
        return -1;
    }
    //将元素val入栈
    *s->top = val;//对top指针所指的区域赋值
    //栈顶指针加1
    s->top++;
    return 1;//入栈成功,返回1
}

void DestroyStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        free(s->base);
        s->stacksize = 0;
        s->base = s->top = NULL;
    }
}

void ClearStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        s->top = s->base;
    }
}

int StackLength(Stack s){
   
   
    return s.top - s.base;
}

int StackEmpty(Stack s){
   
   
    if(s.top == s.base){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

void InitStack(PStack s){
   
   
    //分配一段内存
    s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(s->base == NULL){
   
   
        exit(-1);
    }
    //初始栈顶指针等于栈底指针
    s->top = s->base;
    s->stacksize = MAXSIZE;//最大容量
}

链栈代码

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 10
#define ElemType int

typedef struct{
   
   
    ElemType *top;    //栈顶指针
    ElemType *base;    //栈底指针
    int stacksize;    //栈的最大容量
}Stack,*PStack;

int Pop(PStack s,int *val){
   
   
    //判断栈是否空
    if(s->top == s->base){
   
   
        return -1;
    }
    s->top--;//将指针下移
    *val = *s->top;//元素出栈
    return 1;//出栈成功,返回1
}

int    Push(PStack s,int val){
   
   
    //判断栈是否满
    if(s->top - s->base == s->stacksize){
   
   
        return -1;
    }
    //将元素val入栈
    *s->top = val;//对top指针所指的区域赋值
    //栈顶指针加1
    s->top++;
    return 1;//入栈成功,返回1
}

void DestroyStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        free(s->base);
        s->stacksize = 0;
        s->base = s->top = NULL;
    }
}

void ClearStack(PStack s){
   
   
    if(s->base != NULL){
   
   
        s->top = s->base;
    }
}

int StackLength(Stack s){
   
   
    return s.top - s.base;
}

int StackEmpty(Stack s){
   
   
    if(s.top == s.base){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

void InitStack(PStack s){
   
   
    //分配一段内存
    s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(s->base == NULL){
   
   
        exit(-1);
    }
    //初始栈顶指针等于栈底指针
    s->top = s->base;
    s->stacksize = MAXSIZE;//最大容量
}
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
174 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
31 1
|
21天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
46 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
29天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
47 0
|
2月前
初步认识栈和队列
初步认识栈和队列
64 10