网站导航
> 文档中心 > 【数据结构】栈的基本操作 + OJ练习 （C语言版）

【数据结构】栈的基本操作 + OJ练习 （C语言版）

网友: 文档中心 2022-04-01 10:18:48

文章目录

  • 前言
  • 栈：（Stack）
    • 1. 栈的概念及结构
    • 2.栈的实现
  • 栈和函数栈帧有关系吗？
  • 栈的具体实现：
    • 头文件: （Stack.h）
    • 函数实现:（Stack.c）
    • 测试：（Test.c）
  • 栈的OJ题：

前言

在之前的数据结构的学习中，我们主要学习了线性表中的顺序表和链表，并且做了几道经典OJ题，今天将继续学习线性表中的另一个结构 - 栈。
前情回顾:

目前已学的线性表有：（链接如下）

  • 顺序表
    • 顺序表的OJ题
  • 单链表
    • 单链表的OJ题
    • 带环链表的证明

其实链表又可以细分为：带哨兵位/不带哨兵位，单向/双向，循环/非循环。
将各种情况排列组合，一共有8种组合方式。

我们只讲具有代表性的，其中还有一种具有代表性的链表那就是：
带头双向循环链表：
在这里插入图片描述
它的实现方式与单链表相似，甚至因为其独特的结构，相较单链表而言反而更加简单！
小伙伴们可以自己尝试实现，其中大多数的操作可以复用同种操作，在此就不再过多赘述。

栈：（Stack）

1. 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。

在这里插入图片描述

2.栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为限于栈的结构每次插入数据只能从栈顶插入，单链表的尾插需要遍历整个链表去找尾，效率低，(除非使用带头双向循环链表 或者 将栈底设置为单链表的头每次头插)，而数组在尾上插入数据的代价比较小。
在这里插入图片描述
分析到这里，那就可以说是砍瓜切菜了，这不就是顺序表的尾插尾删吗，比顺序表的实现还要轻松。

栈和函数栈帧有关系吗？

其实它们没有任何关系（属于两个学科，名字相同而已）：
在之前C语言的学习中我们知道，程序的内存区域划分为：栈区，堆区，静态区，和常量区。

  1. 这里的 "栈” 是 “操作系统” 中内存划分的一个区域，用来调用函数时 “创建栈帧” 的。
    在这里插入图片描述2. 而我们今天学习的 “栈” 是一个数据结构。

栈的具体实现：

头文件: （Stack.h）

#pragma once//数组栈的实现#include#include#include#include#includetypedef int STDataType;typedef struct Stack{int* a;int top; //栈顶的位置int capacity; //容量}ST;//初始化void StackInit(ST* ps);//销毁void StackDestroy(ST* ps);//进栈void StackPush(ST* ps, STDataType x);//出栈void StackPop(ST* ps);//判断栈是否为空bool StackEmpty(ST* ps);//栈顶的数据STDataType StackTop(ST* ps);//栈的数据个数int StackSize(ST* ps);

限于栈的特殊结构，出栈只能从栈顶出，所以这里需要单独写一个函数来获取栈顶元素。

函数实现:（Stack.c）

#include"Stack.h"//初始化void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}//销毁void StackDestroy(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}//进栈void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;int* tmp = (int*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){printf("%s\n", strerror(errno));exit(-1);}else{ps->a = tmp;}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}//出栈void StackPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}//判断栈是否为空bool StackEmpty(ST* ps){assert(ps);/*if (ps->top > 0){return false;}else{return true;}*/return ps->top == 0;}//栈顶的数据STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}//栈的数据个数int StackSize(ST* ps){assert(ps);return ps->top;}

测试：（Test.c）

#include"Stack.h"void TestStack(){ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n\n");StackPush(&st, 3);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n\n");//StackDestroy(&st);}int main(){TestStack();return 0;}

在这里插入图片描述
大家在实现数据结构的时候，一定要写一块函数，测一块函数，不然最后都是错也不到改哪里。

栈的OJ题：

OJ链接
在这里插入图片描述

typedef char STDataType;typedef struct Stack{STDataType* a;int top; //栈顶的位置int capacity; //容量}ST;//初始化void StackInit(ST* ps);//销毁void StackDestroy(ST* ps);//进栈void StackPush(ST* ps, STDataType x);//出栈void StackPop(ST* ps);//判断栈是否为空bool StackEmpty(ST* ps);//栈顶的数据STDataType StackTop(ST* ps);//栈的数据个数int StackSize(ST* ps);//初始化void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}//销毁void StackDestroy(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}//进栈void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){//printf("%s\n", strerror(errno));exit(-1);}else{ps->a = tmp;}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}//出栈void StackPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}//判断栈是否为空bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}//栈顶的数据STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}//栈的数据个数int StackSize(ST* ps){assert(ps);return ps->top;}bool isValid(char* s){    ST st;    StackInit(&st); while(*s)    {  if((*s == '(') || (*s == '{') || (*s == '[')) {     StackPush(&st,*s);     s++; } else {     if(StackEmpty(&st))     {  return false;     }   STDataType top = StackTop(&st);     StackPop(&st);     if ((*s == ')' && top != '(')     || (*s == ']' && top != '[')     || (*s == '}' && top != '{'))     {  StackDestroy(&st);  return false;     }      else     {  s++;     } }    }    bool ret = StackEmpty(&st);    StackDestroy(&st);    return ret;}

思路：
读完题之后不难发现，括号的匹配时，是匹配最后存储的数据，那我们优先想到用栈来实现，但是C语言没有C++那么友好可以有库可以直接调用，需要我们自行实现一个栈。
遍历字符串，是左括号就入栈，不是左括号就出栈将刚好遍历到的字符和栈顶数据比对。
同时注意：
栈为空的时候，不能出栈。当while循环结束时，如果栈不为空就不该返回ture。将这些细节处理妥当就没有大问题。

网络标签：

相关问题