广场 › 编程语言 › #yyds干货盘点#算法开启小码农栈血脉

PHP小丑 发表于 2021-12-28 23:11:31

#yyds干货盘点#算法开启小码农栈血脉

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

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

栈的实现
栈的实现一般可以使用数组或者链表实现，==相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。==

栈节点
typedef int STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;       //栈顶
    int capacity;//容量
}ST;栈初始化函数StackInit

//栈初始化函数
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}入栈函数StackPush

//入栈函数
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)
      {
            printf("relloc fail\n");
            exit(-1);
      }
      ps->a = tmp;
      ps->capacity = newcapacity;
    }
    //扩容扩好以后把数据给过去
    ps->a = x;
    ps->top++;
}==提前把栈销毁函数写好==
栈销毁函数StackDestroy

//栈销毁函数
void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}出栈函数StackPop

//出栈函数
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top>0);
    ps->top--;      
}判断栈是否为空 函数StackEmpty

//判断栈是否为空函数
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}取栈顶元素函数StackTop

//取栈顶部函数
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a;
}栈大小函数StackSize

//栈大小函数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}遍历栈

while (!StackEmpty(&stack))
    {
      printf("%d ", StackTop(&stack));
      StackPop(&stack);
    }
代码
Stack.h
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;       //栈顶
    int capacity;//容量
}ST;

//栈初始化函数
extern void StackInit(ST* ps);
//栈销毁函数
extern void StackDestroy(ST* ps);
//入栈函数
extern void StackPush(ST* ps, STDataType x);
//出栈函数
extern void StackPop(ST* ps);
//取栈顶部函数
extern STDataType StackTop(ST* ps);
//栈大小函数
extern int StackSize(ST* ps);
//判断栈是否为空函数
extern bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

//栈初始化函数
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 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)
      {
            printf("relloc fail\n");
            exit(-1);
      }
      ps->a = tmp;
      ps->capacity = newcapacity;
    }
    //扩容扩好以后把数据给过去
    ps->a = x;
    ps->top++;
}
//栈销毁函数
void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}
//出栈函数
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top>0);
    ps->top--;      
}
//取栈顶部函数
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a;
}
//栈大小函数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}
//判断栈是否为空函数
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void Test1()
{
    ST stack = { 0 };
    StackInit(&stack);
    StackPush(&stack, 1);
    StackPush(&stack, 2);
    StackPush(&stack, 3);
    StackPush(&stack, 4);
    //遍历栈
    while (!StackEmpty(&stack))
    {
      printf("%d ", StackTop(&stack));
      StackPop(&stack);
    }
    printf("\n");
    StackDestroy(&stack);
}

int main()
{
    Test1();
    return 0;
}
练习
例1有效的括号




typedef char STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;       //栈顶
    int capacity;//容量
}ST;

//栈初始化函数
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)
      {
            printf("relloc fail\n");
            exit(-1);
      }
      ps->a = tmp;
      ps->capacity = newcapacity;
    }
    //扩容扩好以后把数据给过去
    ps->a = x;
    ps->top++;
}
//判断栈是否为空函数
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

//取栈顶部函数
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a;
}
//出栈函数
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top>0);
    ps->top--;      
}
bool isValid(char * s){
    ST st = {0};
    StackInit(&st);
    while(*s)
    {
      //如果是左括号就入栈
      if(*s == '('
      || *s == '{'
      || *s == '[')
      {
            //入栈
            StackPush(&st,*s);
            s++;
      }
      else
      {   
         if(StackEmpty(&st))   
         {
                StackDestroy(&st);
                return false;
         }
         //出栈
         STDataType tmp = StackTop(&st);
         StackPop(&st);
         if(*s == '}' && tmp != '{'
         || *s == ']' && tmp != '['
         || *s == ')' && tmp != '(')
         {
               StackDestroy(&st);
               return false;
         }         
         else
         {
               s++;
         }         
      }
    }
    //如果栈不是空说明还有左括号
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}


https://blog.51cto.com/u_15443484/4853828

查看完整版本: #yyds干货盘点#算法开启小码农栈血脉