C语言实现栈

  • 开发
  • 23

1栈的概念及结构

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

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

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

2.栈的实现

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

2.1头文件StackQueue.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;

//扩容函数
void checkCapacity(ST* pst);

//打印
void STPrint(ST* pst);

//初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

//取栈顶的数据
STDataType STTop(ST* PST);

//判断栈是否为空
int STEmpty(ST* pst);

//判断栈有多少个数据
int STSize(ST* pst);

        栈的结构类似与之前的顺序表，只是结构体中的size换成了top，其实size和top可以进行等价。 

2.2函数实现文件StackQueue.c

2.2.1 初始化和销毁

2.2.1.1初始化

        函数实现：

void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

        测试代码：

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化
}

int main()
{
	test();
	return 0;
}

2.2.1.2销毁

        函数实现： 

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);

	pst->top = 0;
	pst->capacity = 0;
	pst->a = NULL;
}

        先将动态开辟的空间进行释放，然后将指针a置为NULL，top和capacity置为0.

 2.2.2入栈和出栈

2.2.2.1入栈

        函数实现：

//扩容函数
void checkCapacity(ST* pst)
{
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;

		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}
}

//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	//判断是否需要扩容
	checkCapacity(pst);

	pst->a[pst->top] = x;
	pst->top++;
}

        打印函数：

//打印
void STPrint(ST* pst)
{
	assert(pst);

	for (int i = 0; i < pst->top; i++)
	{
		printf("%d ", pst->a[i]);
	}
	printf("\n");
}

        测试代码：

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);

	STPrint(&s);
}

int main()
{
	test();
	return 0;
}

2.2.2.2出栈

        函数实现：

void STPop(ST* pst)
{
	assert(pst && pst->top); //断言栈内不能为空

	pst->top--;
}

        测试代码：

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);

	STPop(&s);

	STPrint(&s);
}

int main()
{
	test();
	return 0;
}

 2.2.3取栈顶的数据

        函数实现：

//取栈顶的数据
STDataType STTop(ST* pst)
{
	assert(pst && pst->top);

    //top指向的是最后一个元素的后面一个位置
	return pst->a[pst->top - 1];
}

         测试代码：

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);

	STPrint(&s);

	printf("%d ",STTop(&s));


}

int main()
{
	test();
	return 0;
}

2.2.4判断栈是否为空

        函数实现：

//判断栈是否为空
int STEmpty(ST* pst)
{
	assert(pst);

	if (pst->top == 0)
	{
		return 0;
	}
	else
	{
		return -1;
	}
}

        测试代码：

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);

	STPrint(&s);

	int i = STEmpty(&s);
	if (i == 0)
	{
		printf("栈为空!\n");
	}
	else
	{
		printf("栈不为空!\n");
	}
}

int main()
{
	test();
	return 0;
}

2.2.5判断栈有多少个数据        

        函数实现：

//判断栈有多少个数据
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

        测试代码： 

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	STPush(&s, 5);
	STPush(&s, 5);
	STPush(&s, 5);

	STPrint(&s);

	printf("%d ", STSize(&s));
}

int main()
{
	test();
	return 0;
}

 2.3参考代码

//StackQueue.h

#pragma once

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

typedef int STDataType;

//后进先出
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//扩容函数
void checkCapacity(ST* pst);

//打印
void STPrint(ST* pst);

//初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

//取栈顶的数据
STDataType STTop(ST* PST);

//判断栈是否为空
int STEmpty(ST* pst);

//判断栈有多少个数据
int STSize(ST* pst);

//StackQueue.c

#include "StackQueue.h"

//打印
void STPrint(ST* pst)
{
	assert(pst);

	for (int i = 0; i < pst->top; i++)
	{
		printf("%d ", pst->a[i]);
	}
	printf("\n");
}

//初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);

	pst->top = 0;
	pst->capacity = 0;
	pst->a = NULL;
}

//扩容函数
void checkCapacity(ST* pst)
{
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;

		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}
}
//入栈和出栈
//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	//判断是否需要扩容
	checkCapacity(pst);

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst && pst->top);

	pst->top--;
}

//取栈顶的数据
STDataType STTop(ST* pst)
{
	assert(pst && pst->top);

	return pst->a[pst->top - 1];
}

//判断栈是否为空
int STEmpty(ST* pst)
{
	assert(pst);

	if (pst->top == 0)
	{
		return 0;
	}
	else
	{
		return -1;
	}
}

//判断栈有多少个数据
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
//test.c

#include "StackQueue.h"

void test()
{
	ST s;
	STInit(&s); //初始化

	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	STPush(&s, 5);
	STPush(&s, 5);
	STPush(&s, 5);


	//STPop(&s);

	STPrint(&s);


	//int i = STEmpty(&s);
	//if (i == 0)
	//{
	//	printf("栈为空!\n");
	//}
	//else
	//{
	//	printf("栈不为空!\n");
	//}

	//printf("%d ",STTop(&s));

	printf("%d ", STSize(&s));

	STDestroy(&s);
}

int main()
{
	test();
	return 0;
}

阅读全部

相关推荐

  4. C语言——栈的实现

    2024-07-09 23:12:02       50 阅读

  6. C语言-栈的实现

    2024-07-09 23:12:02       20 阅读

  8. 【C/C++】C语言实现顺序栈

    2024-07-09 23:12:02       27 阅读

  10. C语言栈实现就近匹配原则

    2024-07-09 23:12:02       51 阅读

最近更新

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

    2024-07-09 23:12:02       50 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 23:12:02       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-09 23:12:02       43 阅读

  19. Python语言-面向对象

    2024-07-09 23:12:02       54 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-09 23:12:02       50 阅读

热门阅读

  5. 深入解析Spring Boot的application.yml配置文件

    2024-07-09 23:12:02       23 阅读

  9. Docker技术简介

    2024-07-09 23:12:02       19 阅读

  14. Qt 的 qmake的语法简介与例子介绍

    2024-07-09 23:12:02       22 阅读

  16. C#用链表和数组分别实现堆栈

    2024-07-09 23:12:02       21 阅读

  18. 详细阐述 Spring Boot 的核心概念、优势、开发流程、常见配置以及最佳实践

    2024-07-09 23:12:02       15 阅读

  19. Go bytes包

    2024-07-09 23:12:02       24 阅读

  21. C#面 :ASP.Net Core中有哪些异常处理的方案？

    2024-07-09 23:12:02       21 阅读

  23. Redis

    2024-07-09 23:12:02       22 阅读

  29. 未来已来：期待GPT-5在人工智能领域的突破与创新

    2024-07-09 23:12:02       27 阅读

  30. 大语言模型应用--AI工程化落地

    2024-07-09 23:12:02       20 阅读