手撕数据结构:栈+例题

目录

一、栈的概念及结构

二、栈的头文件及基本框架

三、接口实现

1、对栈的初始化

 2、栈的销毁

3、入栈操作

4、出栈操作

 5、判断栈是否为空

6、返回栈顶元素

7、遍历栈

四、有效的括号 - 力扣（LeetCode）

题目描述：

 思路：

代码：

---

一、栈的概念及结构

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

如同子弹夹，我们进行添子弹和出子弹，很形象。

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

 接下来，我们以数组栈的形式去模拟。

二、栈的头文件及基本框架

1.  
   #pragma once
2.  
   #include<stdio.h>
3.  
   #include<stdlib.h>
4.  
   #include<stdbool.h>
5.  
   #include<assert.h>
6.  
    
7.  
   typedef int STDataType;
8.  
    
9.  
   typedef struct Stack
10.  
    {
11.  
    STDataType* a;//就是以a开头的一段连续的空间
12.  
    int top;//定义栈顶位置
13.  
    int capacity;
14.  
    }ST;
15.  
     
16.  
    void SLInit(ST* ps);
17.  
    void SLDestroy(ST* ps);
18.  
    void STPush(ST* ps, STDataType x);
19.  
    void STPop(ST* ps);
20.  
    int STSize(ST* ps);
21.  
    bool STEmpty(ST* ps);
22.  
    STDataType STTop(ST* ps);//获取栈顶元素

三、接口实现

1、对栈的初始化

1.  
   void SLInit(ST* ps)
2.  
   {
3.  
   ST* ret = (ST*)malloc(4 * sizeof(ST));
4.  
   if (ret == NULL)
5.  
   {
6.  
   perror(malloc);
7.  
   exit(-1);
8.  
   }
9.  
   ps->a = ret;
10.  
    ps->capacity = 4;
11.  
    ps->top = 0;
12.  
    }

 2、栈的销毁

1.  
   void SLDestroy(ST* ps)
2.  
   {
3.  
   free(ps->a);
4.  
   ps->a = NULL;
5.  
   ps->capacity = 0;
6.  
   ps->top = 0;
7.  
   }

3、入栈操作

1.  
   void STPush(ST* ps, STDataType x)
2.  
   {
3.  
   assert(ps != NULL);
4.  
   //检查需不需要扩容
5.  
   if (ps->top == ps->capacity)
6.  
   {
7.  
   ps->capacity = 4;
8.  
   ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);
9.  
   if (ret == NULL)
10.  
    {
11.  
    perror(realloc);
12.  
    exit(-1);
13.  
    }
14.  
    ps->a = ret;
15.  
    }
16.  
    ps->a[ps->top] = x;
17.  
    ps->top ;
18.  
    }

4、出栈操作

1.  
   void STPop(ST* ps)
2.  
   {
3.  
   assert(ps);
4.  
   ps->top--;
5.  
   }

 5、判断栈是否为空

1.  
   bool STEmpty(ST* ps)
2.  
   {
3.  
   assert(ps);
4.  
   return ps->top == 0;
5.  
   如果右边等式成立返回true，反之返回false
6.  
   }

6、返回栈顶元素

1.  
   STDataType STTop(ST* ps)
2.  
   {
3.  
   assert(ps);
4.  
   assert(ps->top > 0);
5.  
   return ps->a[ps->top - 1];
6.  
   }

7、遍历栈

不同于其他数据结构，遍历栈不用print

1.  
   //遍历栈的特殊方式
2.  
   while (!STEmpty(&ps))
3.  
   {
4.  
   printf("%d ", STTop(&ps));
5.  
   STPop(&ps);
6.  
   }

四、有效的括号 - 力扣（LeetCode）

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

 思路：

如果是左括号就入栈，如果是右括号就与栈顶元素进行比较。这样就正好匹配题目的要求，但博主目前没有学过STL库，所以只能将上面的手撕栈CV一下啦，下面的代码为了避免冗余去除掉这一部分~

代码：

1.  
   bool isValid(char * s)
2.  
   {
3.  
   char* ret = s;
4.  
   int num = 0;
5.  
   //利用奇数偶数判断数量是否匹配
6.  
   while(*ret)
7.  
   {
8.  
   num ;
9.  
   ret ;
10.  
    }
11.  
    if(num%2 != 0)
12.  
    {
13.  
    return false;
14.  
    }
15.  
    ST ps;
16.  
    SLInit(&ps);
17.  
    while(*s)
18.  
    {
19.  
    switch(*s)
20.  
    {
21.  
    case '{':
22.  
    case '[':
23.  
    case '(':
24.  
    STPush(&ps,*s);
25.  
    break;
26.  
    case ')':
27.  
    case ']':
28.  
    case '}':
29.  
    if(STSize(&ps) == 0)
30.  
    return false;
31.  
    if(*s == ']' && STTop(&ps) != '['||
32.  
    *s == ')' && STTop(&ps) != '('||
33.  
    *s == '}' && STTop(&ps) != '{')
34.  
    {
35.  
    SLDestroy(&ps);
36.  
    return false;
37.  
    }
38.  
    STPop(&ps);
39.  
    break;
40.  
    }
41.  
    s ;
42.  
    }
43.  
    //防止((出现
44.  
    if(!STEmpty(&ps))
45.  
    return false;
46.  
    return true;
47.  
    }

这篇好文章是转载于：学新通技术网