05.栈介绍+实现

目录

一、栈的概念

二、栈的实现

1、头文件定义

2、功能函数实现

3、主函数测试

一、栈的概念

        栈是一种特殊的线性表，只能在栈顶进行插入和删除操作，遵循后进先出的原则。

        入栈：栈的插入操作，也叫进栈/压栈，栈顶操作。

        出栈：栈的删除操作，栈顶操作。

二、栈的实现

        栈可以用数组或链表实现，数组实现更有优势，尾部插入代价小。

        栈的实现类似于顺序表。

1、头文件定义

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

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		//栈顶
	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);
//检测栈是否为空
bool StackEmpty(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);

2、功能函数实现

栈顶定义有两种方式：top初始化为-1，即top指的是栈顶元素的下标。

                                    top初始化为0，即top指的是栈顶元素的下标+1，即栈的数据个数。（用）

#include "Stack.h"

//栈初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(Stack* 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 == NULL)
		{
			perror("realloc fail\n");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->a);
	ps->top--;
}

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

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

//检测栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//销毁栈
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3、主函数测试

#include "Stack.h"

int main()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 4);
	StackPush(&st, 3);
	StackPush(&st, 2);
	StackPush(&st, 1);
	printf("先入栈四个数4，3，2，1，然后出栈，出栈顺序应为1，2，3，4\n");
	while (!StackEmpty(&st))
	{
		STDataType x = StackTop(&st);
		printf("%d ", x);
		StackPop(&st);
	}
	StackDestory(&st);
	return 0;
}

分别建立名为Stack.h的头文件和Stack.c的源文件，和一个主函数文件。运行上述代码：