【数据结构】_栈的结构与实现

目录

1. 栈的相关概念与结构

2. 栈的实现

2.1 栈实现的底层结构选择

2.2 Stack.h

2.3 Stack.c

2.4 Test_Stack.c

1. 栈的相关概念与结构

1、栈：一种特殊的线性表，只允许在固定的一端插入和删除数据；

允许进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；

栈中的元素遵守后进先出LIFO（Last In First Out）的原则；

2、压栈：栈的插入操作叫做进栈、压栈、入栈。入数据在栈顶；

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

2. 栈的实现

2.1 栈实现的底层结构选择

1、若采用数组实现栈，则可将数组头视为栈底，数组尾视为栈顶，出入栈都在数组尾进行操作。

2、若采用单链表实现栈，则将链尾视为栈底，入栈利用头插实现，出栈利用头删实现。

（若将链首视为栈底，入栈通过尾插实现，但出栈较为麻烦）

3、若采用双链表实现栈，则无论将哪端视为栈底，出栈、入栈等方法的实现都非常方便；

相较而言，数组、单链表的方式均可较为便利实现栈。相对而言数组的实现效果更优，数组在尾上插入数据的效率高且代价小。采用数组实现栈。

2.2 Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack {
	// 动态开辟数组
	STDataType* a;
	// top表示栈顶元素的下一个元素的下标
	int top;
	int capacity;
}ST;
void STInit(ST* pst);
void STDestory(ST* pst);
// 压栈
void STPush(ST* pst,STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取栈元素个数
int STSize(ST* pst);

2.3 Stack.c

#include"Stack.h"
// 初始化
void STInit(ST* pst) {
	assert(pst);
	pst->a = NULL;
	// top表示栈顶元素的下一个元素的下标
	pst->top = 0;
	// capacity表示栈内元素个数（等价于栈顶元素的下一个元素的下标）
	pst->capacity = 0;
}
// 销毁
void STDestory(ST* pst) {
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
// 压栈
void STPush(ST* pst, STDataType x) {
	assert(pst);
	// 满则扩容
	if (pst->top == pst->capacity) {
		int newCapacity = pst->capacity == 0? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * (sizeof(STDataType)));
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	// 入栈数据
	pst->a[pst->top] = x;
	pst->top++;
}
// 出栈
void STPop(ST* pst) {
	assert(pst);
	// 判栈非空
	assert(pst->top>0);
	pst->top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {
	assert(pst);
	assert(pst->top>0);
	return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst) {
	if (pst->top == 0) {
		return true;
	}
	return false;
	//return pst->top == 0;
}
// 获取栈元素个数
int STSize(ST* pst) {
	assert(pst);
	return pst->top;
}

2.4 Test_Stack.c

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

注：在使用数组实现栈的方式中，定义栈时的top表示栈顶位置，关于top的具体含义与初始化、销毁、压栈、出栈等操作需要进行对应：

若top表示栈顶元素的下标，则初始化时(栈内无元素)，top=-1，插入时在a[top++]处入栈元素；

若top表示栈顶元素的下一个元素的下标，则初始化时top为0，插入时在a[top]处入栈元素；

（易有top表示栈顶元素下标，但将top初始化为0的错误写法，注意勿混淆）