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

栈有两种基本操作：

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

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。本文采用的是数组栈。

2.1 动态结构定义


typedef int STDataType;// typedef定义STDataType类型
 
typedef struct Stack
{
	int* a;       // 定义动态存储数组
	int top;      // 记录栈顶    
	int capacity; // 记录容量
}ST;

2.2 栈的初始化


void StackInit(ST* ps)
{
	assert(ps);
 
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

2.3 入栈


void StackPush(ST* ps, STDataType data)
{
	assert(ps);
 
	// 判断是否栈满，栈满则需要扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
 
	ps->a[ps->top++] = data;
}

2.3 出栈（压栈）


void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	
	ps->top--;
}

2.4 获取栈顶元素


STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
 
	return ps->a[ps->top - 1];
}

2.5 获取栈中有效元素个数


int StackSize(ST* ps)
{
	assert(ps);
 
	return ps->top;
}

2.6 检测栈是否为空


bool StackEmpty(ST* ps)
{
	assert(ps);
 
	return ps->top == 0;
}

2.7 栈的销毁


void StackDestroy(ST* ps)
{
	assert(ps);
 
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

3. 栈的使用

搞定所有栈的相关函数后，我们来建立一个text函数来测试一下，在这之前需要调用之前我们所定义的栈的相关函数。


void test()
{
	ST st;
	StackInit(&st);
 
    // 入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
 
    // 输出栈中的值，每输出一个，就出栈一个
	while (!StackEmpty(&st)) // 当栈为空时停止输出
 	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
 
	StackDestroy(&st);
}

4. 完整源码

Stack.h


#pragma once
 
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
 
typedef int STDataType;
 
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;
 
// 初始化栈
void StackInit(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType data);
// 出栈
void StackPop(ST* ps);
// 获取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);

Stack.c


#include "Stack.h"
 
void StackInit(ST* ps)
{
	assert(ps);
 
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
void StackPush(ST* ps, STDataType data)
{
	assert(ps);
 
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
 
	ps->a[ps->top++] = data;
}
 
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	
	ps->top--;
}
 
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 StackEmpty(ST* ps)
{
	assert(ps);
 
	return ps->top == 0;
}
 
void StackDestroy(ST* ps)
{
	assert(ps);
 
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

test.c


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

5. 最终实现效果

后续内容等博主继续学习后分享给大家。请大家继续关注，不断督促，共同进步！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/589304