【数据结构和算法】了解认识栈,并实现栈的相关函数(下)

简介: 【数据结构和算法】了解认识栈,并实现栈的相关函数(下)

三、完整代码实现

1.链表实现栈

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
//创建基础结构
typedef struct node {
  int data;
  struct node* next;
}ST;
//栈实际上就是一个只能进行头插头删的单向链表
//创建栈的头尾结点 结构体
typedef struct stack {
  struct node* top;//栈顶元素地址
  struct node* bottom;//栈底元素地址
  int size;//栈的元素个数
};
//表示每一个栈都是struct stack* 类型的,栈中的每一个怨怒是都是struct node *类型的  不仅需要为栈分配内存,还需要为压入栈中的元素分配内存
/*
node中的next指针用于让栈中上面的节点连接到下面的节点,stack中的top和bottom分别存放当前栈顶元素的地址和栈底元素的后一个位置的地址(NULL),
因为是用于指向栈中节点的指针,所以得是struct node* 类型。*/
//初始化栈
struct stack* create_stack()
{
  struct stack* s = (struct stack*)malloc(sizeof(struct stack));
  s->size = 0;
  s->bottom = s->top = NULL;
  return s;
}
//一开始栈是空的所以 size为0  top  bottom是NULL
//创建新的结点
struct node* create_node(int data) {
  struct node* newnode = (struct node*)malloc(sizeof(struct node));
  newnode->next = NULL;
  newnode->data = data;
  return newnode;
}
//入栈
//入栈首先要将准备入栈的元素封装成结点,和链表没有差别
void stackPush(struct stack* s, int x) {
  ST* newnode = create_node(x);
  newnode->next = s->top;
  s->top = newnode;
  s->size++;
}
//出栈
void stackPop(struct stack* s, int* x) {
//判断是否为空栈   如果是 空栈的话就  使得输出 Pop failed
  if (s->size == 0) {
    printf("Pop failed\n");
    exit(-1);
  }
  //创建结点临时变量  赋值得到栈顶元素
  ST* tmp = s->top;
  *x = tmp->data;//得到数值
  s->top = tmp->next;
  s->size--;
}
//查看栈顶元素
void stackTop(struct stack* s, int* x) {
  if (s->size == 0) {
    printf("空栈~~\n");
    exit(-1);
  }
  *x = s->top->next->data;
}
//清空栈
void make_stack_empty(struct stack* s) {
  s->size = 0;
  s->bottom = s->top ;
  //将栈底等于栈顶就可以  然后将size为0
}
void stackPrint(struct stack* s) {
  //打印栈表
  ST* list = s->top;
  printf("top -> ");
  while (list!=NULL) {
    printf("%d -> ", list->data);
    list = list->next;
  }
}
int main()
{
  struct stack *s = create_stack();
  stackPush(s, 1);
  stackPush(s, 2);
  stackPush(s, 3);
  stackPush(s, 4);
  stackPush(s, 5);
  stackPrint(s);
  int a = 0;
  stackPop(s,&a);
  printf("\n%d\n", a);
  stackPrint(s);
  return 0;
}

2.数组(顺序表)实现栈

#define _CRT_SECURE_NO_WARNINGS
#include"steck.h"
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//栈是限定在一个表里面的一段进行插入删除操作的线性表
// 数据进出的顺序为先进后处
// 应用场景:网页浏览的时候的后退  编辑软件的撤销
// 
//创建栈  两个方式:数组(顺序表)和 单链表
//1.数组:选用数组用来做栈的存储结构,只需要在数组末尾进行操作即可,完美避开数组操作中挪动数据缺陷
      //   显然是可以用数组来做栈的存储结构
//2.单链表  :因为栈是吸纳星表的一段进行操作,所以一般是用链表头进行操作
//进行头插头删  是用链表更好 效率更高
//1.用数组的方式
typedef int StackDataType;
typedef struct Stcak {
    StackDataType* data;
    int top;
    int capacity;   //数据域和元素个数
}ST;
//初始化
void StackInit(ST* ps) {
    ps->data = (StackDataType*)malloc(sizeof(StackDataType) * 4);
    if (ps->data == NULL) {
        printf("malloc failed\n");
        exit(-1);
    }
    ps->top = 0;
    ps->capacity = 4;
}
//压栈
void StackPush(ST* ps, int x) {
    assert(ps);//断言
    //满了就扩容
    if (ps->top == ps->capacity) {
        StackDataType* tmp = (StackDataType*)realloc(ps->data, sizeof(StackDataType) * ps->capacity * 2);
        if (tmp == NULL) {
            printf("realloc failed\n");
            exit(-1);
        }
        else {
            ps->data = tmp;
            ps->capacity *= 2;
        }
    }
    ps->data[ps->top] = x;
    ps->top++;
}
//出栈
void StackPop(ST* ps) {
    //出栈是将最后一个元素放出来  先进后出
    assert(ps);
    assert(ps->top > 0);//断言进行判断是否栈为空  即top!=0
    ps->top--;
    //直接减减就可以  没有了对应元素 的数据  如果再次压栈的话 会把之前的数据进行更改
}
//取得栈顶元素
StackDataType StackTop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    return ps->data[ps->top - 1];//因为top栈顶始终要保持比元素个数大一,保证压栈的时候先压栈然后再加加
//所以取栈顶元素 的时候 top-1
}
//销毁栈
void StackDestory(ST* ps) {
    assert(ps);
    free(ps->data);
    //释放数组data的空间
    ps->data = NULL;
    ps->top = ps->capacity = 0;
}
//求栈中元素个数
int StackSize(ST* ps) {
    assert(ps);
    return ps->top;
}
//判断是否为空
bool StackEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}
void StackPrint(ST* ps) {
    //打印栈表
    assert(ps);
    for (int i = 0; i < ps->top; i++) {
        printf("%d ", ps->data[i]);
    }
    printf("\n");
}
int main()
{
    ST s;
    ST *ps=&s;
  /*  StackInit(&ps);
    StackPush(&ps, 1);
    StackPush(&ps, 2);
    StackPush(&ps, 3);
    StackPush(&ps, 4);
    StackPush(&ps, 5);
    StackPrint(&ps);*/
    StackInit(ps);
    StackPush(ps, 1);
    StackPush(ps, 2);
    StackPush(ps, 3);
    StackPush(ps, 4);
    StackPush(ps, 5);
    StackPop(ps);//出栈成功
    StackPrint(ps);
    printf("%d \n", StackTop(ps));//取得栈顶元素
    printf("%d \n", StackSize(ps));//获得栈表元素个数
    StackDestory(ps);
    StackPrint(ps);//销毁栈表成功
    return 0;
}

总结

栈是限定在一个表里面的一段,对其进行插入删除操作的线性表,数据进出的顺序为先进后处,应用场景:网页浏览的时候的后退  编辑软件的撤销,实际上栈的功能就这样,学会顺序表以及链表的使用,对于栈来讲,只是懂得头擦头删,理解概念了,就好掌握并实现栈。

下文,我们会讲解一下队列,和栈相似,但是另有不同,敬请期待吧,感谢大家支持!!!

相关文章
|
22天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
26天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
78 4
|
23天前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
125 67
|
24天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
23天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
1月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
97 23
|
1月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
60 20
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
22天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
52 4