数据结构7:栈

头文件

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

#define CAPACITY_INIT 4

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int size;
	int capacity;
}Stack;

//栈的初始化
void StackInit(Stack* ps);

//压栈
void StackPush(Stack* ps, STDataType x);

//出栈
void StackPop(Stack* ps);

//获取栈顶元素
STDataType StackTop(Stack* ps);

//获取栈中有效数据个数
int StackSize(Stack* ps);

//检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);

//栈的销毁
void StackDestroy(Stack* ps);

实现文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

//栈的初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * CAPACITY_INIT);
	if (ps->a == NULL)
	{
		perror("malloc fail!");
		return;
	}
	ps->size = 0;
	ps->capacity = CAPACITY_INIT;
}

//判断是否需要扩容
void StackChekCapacity(Stack* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
		if (ps->a == NULL)
		{
			perror("realloc fail!");
			return;
		}
		ps->capacity *= 2;
	}
}

//压栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	StackChekCapacity(ps);
	ps->a[ps->size++] = x;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->size--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->size - 1];
}

//获取栈中有效数据个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->size;
}

//检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->size == 0)
		return 1;
	else
		return 0;
}

//栈的销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->size = 0;
	ps->capacity = 0;
	free(ps->a);
}

测试文件

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
#include<stdbool.h>

//int main()
//{
//	Stack a;
//	Stack* ps = &a;
//
//	//初始化
//	StackInit(ps);
//
//	//压栈
//	StackPush(ps, 1);
//	printf("%d ", StackTop(ps));
//
//	StackPush(ps, 2);
//	printf("%d ", StackTop(ps));
//
//	StackPush(ps, 3);
//	printf("%d ", StackTop(ps));
//
//	StackPush(ps, 4);
//	printf("%d ", StackTop(ps));
//
//	StackPop(ps);
//	printf("%d ", StackTop(ps));
//
//
//
//
//	//销毁
//	StackDestroy(ps);
//
//	return 0;
//}

经典题目

在这里插入图片描述

bool isValid(char* s) {
    Stack a;
    Stack* ps = &a;
    StackInit(ps);
    int len = strlen(s);
    for (int i = 0; i < len; i++)
    {
        char tmp = *(s + i);
        if (tmp == '(' || tmp == '[' || tmp == '{')
        {
            StackPush(ps, tmp);
        }
        else
        {
            if (StackEmpty(ps))
                return false;
            char left = StackTop(ps);
            if (left == '(')
                left = ')';
            else if (left == '[')
                left = ']';
            else
                left = '}';
            StackPop(ps);
            if (left != tmp)
                return false;
        }
    }
    if (!StackEmpty(ps))
        return false;
    StackDestroy(ps);
    return true;
}

相关推荐

  1. 数据结构--

    2024-04-22 16:30:06       57 阅读
  2. 数据结构-

    2024-04-22 16:30:06       57 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-22 16:30:06       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-22 16:30:06       106 阅读
  3. 在Django里面运行非项目文件

    2024-04-22 16:30:06       87 阅读
  4. Python语言-面向对象

    2024-04-22 16:30:06       97 阅读

热门阅读

  1. 【运维】docker-compose部署redis

    2024-04-22 16:30:06       37 阅读
  2. 函数指针的一点总结

    2024-04-22 16:30:06       36 阅读
  3. ElementUI的基本使用

    2024-04-22 16:30:06       29 阅读
  4. Python机器学习项目开发实战:无监督学习的聚类

    2024-04-22 16:30:06       30 阅读
  5. HttpComponentsClientHttpRequestFactory

    2024-04-22 16:30:06       32 阅读
  6. vsCode 配置 用户代码

    2024-04-22 16:30:06       32 阅读
  7. Python的pytest框架(3)--fixtrue固件

    2024-04-22 16:30:06       34 阅读
  8. 静态路由

    2024-04-22 16:30:06       33 阅读
  9. C++超级快读快写2.3

    2024-04-22 16:30:06       26 阅读