【数据结构】栈详解

Hello everybody!今天给大家讲讲数据结构中一个比较重要的知识：栈。希望宝子们在看过这篇文章后能够有所收获！

1.栈的概念及结构

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

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

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

2.实现栈

由于实现栈需要较长的代码，因此我们要像公司中做大型项目一样创建一个头文件：Stack.h和两个源文件：Stack.c Test.c。

头文件中需要包含所需要的库文件，接口的声明，栈的声明。总之就是要我们清晰的看到栈的结构和功能。

而源文件Stack.c需要实现在头文件中声明的函数。

源文件Test.c用于测试栈的功能是否正常。

当然源文件需要包含头文件，这样才能把它们关联起来。

创建三个文件使得代码逻辑更加清晰，有利于后期代码的维护。

2.1接口的声明&栈的声明

栈只需要在栈顶压栈和出栈，综合考虑：以顺序表的方式实现栈最优。

2.2接口的实现

在头文件中我们声明个栈的各种接口，在源文件中，我们需要实现这些接口。

目前我们实现了STInit和STPush两个接口并测试了其功能，一切正常。

这是剩下的接口，思路比较简单。

这是测试后的结果。

3.代码

头文件：

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;//用STDataType代替int。便于以后更改数据类型
typedef struct Stack {
    STDataType* a; //整型指针，用于存放栈中的数据。
    int top;//记录栈顶的位置
    int capacity;//记录栈的容量
}ST;


void STInit(ST* pst);//初始化
void STDestroy(ST* pst);//销毁
void STPush(ST* pst, STDataType x);//压栈
void STPop(ST* pst);//出栈
STDataType STTop(ST* pst);//输出栈顶元素的值
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//输出栈中有效元素的个数

源文件：

#include "Stack.h"
void STInit(ST* pst) {
	assert(pst);//检验pst是否为空指针
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = -1;//当栈为空的时候栈顶位置为-1。当栈中有一个元素的时候，栈顶位置为0。
}
void STPush(ST* pst, STDataType x) {
	assert(pst);
	if (pst->top + 1 == pst->capacity) {
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//当容量为0时，赋予4值的个空间，不为零时，按2倍增加
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);//扩容
		if (tmp == NULL) {//判断扩容是否成功
			perror("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	
	pst->a[pst->top+1] = x;
	pst->top++;
}

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

STDataType STTop(ST* pst) {
	assert(pst);
	assert(pst->top > -1);//判断栈是否为空
	return  pst->a[pst->top];
}

bool STEmpty(ST* pst) {
	assert(pst);
	return pst->top + 1==0;//pst->top+1代表栈中的元素个数，等于0为空，不等于0为非空。
}

int STSize(ST* pst) {
	assert(pst);
	return pst->top + 1;
}

void STDestroy(ST* pst) {
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = -1;
	pst->capacity = 0;
}

源文件

#include "Stack.h"
int main() {
	ST plist;
	STInit(&plist);
	STPush(&plist, 1);
	STPush(&plist, 2);
	STPush(&plist, 3);
	STPush(&plist, 4);
	STPush(&plist, 5);
	
	
	
	while (!STEmpty(&plist)) {
		printf("%d", STTop(&plist));
		STPop(&plist);
	}
	STDestroy(&plist);
	return 0;
}