首页 > 编程语言 >手把手教你使用C语言实现堆栈数据结构算法-两种方式(链表+数组)

手把手教你使用C语言实现堆栈数据结构算法-两种方式(链表+数组)

时间:2024-08-31 20:47:22浏览次数:10  
标签:return int 手把手 top C语言 链表 stack size

堆栈

定义

栈(stack) 是一种遵循先入后出逻辑的线性数据结构,常见操作入栈,出栈,访问栈


图片来源:https://www.hello-algo.com/

栈的实现

栈遵循先入后出的原则,因此我们只能在栈顶添加或删除元素。然而,数组和链表都可以在任意位置添加和删除元素,因此栈可以视为一种受限制的数组或链表。换句话说,我们可以“屏蔽”数组或链表的部分无关操作,使其对外表现的逻辑符合栈的特性。

基于链表的实现

使用链表实现栈时,我们只需将链表的头节点视为栈顶,尾节点视为栈底

入栈操作,只需将元素插入链表头部(这种节点插入方式被称为“头插法”),出栈操作,只需将头结点从链表中删除即可。

/* 基于链表实现的栈 */
typedef struct
{
    ListNode *top; // 将头节点作为栈顶
    int size;      // 栈的长度
} LinkedListStack;

/* 构造函数 */
LinkedListStack *newLinkedListStack()
{
    LinkedListStack *s = malloc(sizeof(LinkedListStack));
    s->top = NULL;
    s->size = 0;
    return s;
}

/* 析构函数 */ 
void delLinkedListStack(LinkedListStack *s)
{
    while (s->top)
    {
        ListNode *n = s->top->next;
        free(s->top);
        s->top = n;
    }
    free(s);
}

/* 获取栈的长度 */
int size(LinkedListStack *s)
{
    return s->size;
}

/* 判断栈是否为空 */
bool isEmpty(LinkedListStack *s)
{
    return size(s) == 0;
}

/* 入栈 */
void push(LinkedListStack *s, int num)
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->next = s->top; // 更新新加节点指针域
    node->val = num;     // 更新新加节点数据域
    s->top = node;       // 更新栈顶
    s->size++;           // 更新栈大小
}

/* 访问栈顶元素 */
int peek(LinkedListStack *s)
{
    if (s->size == 0)
    {
        printf("栈为空\n");
        return INT_MAX;
    }
    return s->top->val;
}

/* 出栈 */
int pop(LinkedListStack *s)
{
    int val = peek(s);
    ListNode *tmp = s->top;
    s->top = s->top->next;
    // 释放内存
    free(tmp);
    s->size--;
    return val;
}

基于数组的实现

使用数组实现栈时,可以将数组的尾部作为栈顶,入栈,出栈分别在尾部添加与删除元素,时间复杂度为O(1);

由于入栈元素可能会源源不断的增加,使用动态数组操作可避免后续增容操作

/* 基于数组实现的栈 */
typedef struct
{
    int *data;
    int size;
} ArrayStack;

/* 构造函数 */
ArrayStack *newArrayStack()
{
    ArrayStack *stack = malloc(sizeof(ArrayStack));
    // 初始化一个大容量,避免扩容
    stack->data = malloc(sizeof(int) * MAX_SIZE);
    stack->size = 0;
    return stack;
}

/* 析构函数 */
void delArrayStack(ArrayStack *stack)
{
    free(stack->data);
    free(stack);
}

/* 获取栈的长度 */
int size(ArrayStack *stack)
{
    return stack->size;
}

/* 判断栈是否为空 */
bool isEmpty(ArrayStack *stack)
{
    return stack->size == 0;
}

/* 入栈 */
void push(ArrayStack *stack, int num)
{
    if (stack->size == MAX_SIZE)
    {
        printf("栈已满\n");
        return;
    }
    stack->data[stack->size] = num;
    stack->size++;
}

/* 访问栈顶元素 */
int peek(ArrayStack *stack)
{
    if (stack->size == 0)
    {
        printf("栈为空\n");
        return INT_MAX;
    }
    return stack->data[stack->size - 1];
}

/* 出栈 */
int pop(ArrayStack *stack)
{
    int val = peek(stack);
    stack->size--;
    return val;
}
/* 测试代码 */
int main()
{
    ArrayStack *stack = newArrayStack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    printf("%d\n", pop(stack));
    printf("%d\n", pop(stack));
    printf("%d\n", pop(stack));
    printf("%d\n", pop(stack));
    delArrayStack(stack);
    return 0;
}

典型应用

  • 浏览器的后退与前进,软件中的撤销和反撤销
  • 程序内存管理
  • 深度优先算法,回溯算法
  • 后缀表达式取值

标签:return,int,手把手,top,C语言,链表,stack,size
From: https://www.cnblogs.com/wujingzhilv/p/18390748

相关文章

  • 讲解如何用C语言实现带头单向单链表
    目录链表的结构组成:链表的常用接口:初始化带头单链表的头指针:动态申请一个结点(用于后续数据的插入):单链表打印:单链表尾插:单链表的头插:单链表的尾删:单链表头删:单链表查找符合值的第一个节点,没找到时返回NULL:单链表在pos位置之后插入x:单链表删除pos位置之后的值......
  • 主元素问题(C语言)
    主元素问题(C语言)题目参考代码#include<stdio.h>intmain(){//主元素问题intn,s[400002],num=1,max=0,maxNum=0;scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&s[i]);for(inti=0;......
  • c语言分支与循环详解
    使用if、switch实现分支结构,使用for、while、dowhile实现循环结构分支:1.1if语句的语法if(表达式) 语句;在c语言中0表示假,则语句不执行。非0表示真,语句执行1.2else与if对应,比如说一个数不是奇数就是偶数了if(表达式) 语句1;else 语句2;表达式成立则执行语句1,不成......
  • 代码随想录算法训练营,8月31日 | 24. 两两交换链表中的节点,19.删除链表的倒数第N个节点
    24.两两交换链表中的节点题目链接:24.两两交换链表中的节点文档讲解︰代码随想录(programmercarl.com)视频讲解︰两两交换链表中的节点日期:2024-08-31做前思路:用上虚拟头指针,从头开始,先指向2再到1,再到3,但要注意保留原本的结点。Java代码如下:classSolution{publicListN......
  • leetcode刷题day4|链表部分(24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点、
    前言:链表练习的第二天,对链表的理解加深了24.两两交换链表中的节点这个题一开始的思路是用cur和next两个指针来做,但是绕来绕去绕迷糊了,最后超时了。把错误的代码放在下面警醒大家:主要问题出现在这两行代码,next.next发生了更改。next.next=next.next.next;next.next.nex......
  • leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)
    前言:链表部分之前刷过一些题,掌握的还可以,希望可以顺利把这部分题刷完。203.移除链表元素思路:自己创建一个头节点,使新的头节点指向旧的头节点。错误尝试:一开始考虑的比较复杂,设置了指针pre,能够想到直接比较cur.next.val和val的值会使代码更加简洁,但也要注意想清楚如果删除......
  • 7-1 素数对猜想(C语言)
    7-1素数对猜想题目参考代码#include<stdio.h>intmain(){ //一、用埃拉托斯特尼筛法,找出所有的素数 intnum[100002]; intN; scanf("%d",&N); for(inti=2;i<N+2;i++)//赋初值为1,表示均为素数 num[i]=1; //把未标记的数的的倍数,全部标记为非素......
  • 【华为OD机试真题E卷】31、最大社交距离 | 机试真题+思路参考+代码分析(E卷复用)(C语言、
    文章目录一、题目......
  • 数据结构-单链表-详解-2
    数据结构-单链表-详解-21.前言2.创建新结点3.头插与尾插3.1头插3.2尾插空链表找尾4.头删与尾删4.1头删4.2尾删1.前言在数据结构-单链表-详解-1中,我们不仅了解了单链表的基本概念,还掌握了如何创建和打印单链表。今天,我将详细讲解如何对单链表进行头尾部的插入、......
  • Python比C语言到底有什么优势?为什么越来越多人都学python?
    Python作为一种高级编程语言,在众多编程语言中脱颖而出,主要得益于其多方面的优势。以下是Python相比于其他语言的一些显著优势:简单易学:Python的语法清晰、简洁,易于阅读和编写,这使得它成为初学者的首选语言。其语法结构接近于自然语言,减少了学习曲线的陡峭度。丰富的库和框......