数据结构——栈

大家好我是小锋，今天我们来学习一下栈，

栈的概念及结构 

初始化

//初始化
void stackinit(stack* ps) {
	assert(ps);
	ps->val = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

压栈

//压栈
void stackpush(stack* ps,CMMlet a) {
	assert(ps);
	if (ps->capacity == ps->top) {
		int n = ps->val == NULL ? 4 : ps->capacity * 2;
		CMMlet* cur = (CMMlet*)realloc(ps->val, n * sizeof(CMMlet));
		if (cur == NULL) {
			printf("%s", strerror(errno));
			return;
		}
		ps->val = cur;
		ps->capacity = n;
	}
	ps->val[ps->top] = a;
	ps->top++;
}

这里的操作都是顺序表的常规操作了我就不细说了

出栈

//出栈
void stackpop(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	ps->top--;
}

这里我们主要注意（栈为空时不能继续出栈了）

这里我们可以写一个函数来判断，

//检测栈是否为空（空返回0，非空返回非0）
int stackEmpty(stack* ps) {
	assert(ps);
	return ps->top;
 
}

获取栈顶元素

//获取栈顶元素
CMMlet stacktop(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	return ps->val[ps->top - 1];
}

获取栈中有效元素个数

//获取栈中有效元素个数
int stacksize(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	return ps->top;
}

销毁栈

//销毁栈
void stackdestroy(stack* ps) {
	assert(ps);
	assert(!stackEmpty(ps));
	free(ps->val);
	ps->val = NULL;
}

我们写个函数来验证一下我们写的栈是否可以正常操作

先写个函数输出表中的数据（这违背了栈的概念所有不在栈的操作中只是为了方便测试）

// 打印栈
void stackdy(stack* ps) {
	for (int i = 0; i < ps->top; i++) {
		printf("%d", ps->val[i]);
	}
	printf("\n");
}
 
//测试函数
 
void stackcs() {
	stack ps;
	//初始化
	stackinit(&ps);
	//压栈
	stackpush(&ps, 1);
	stackpush(&ps, 2);
	stackpush(&ps, 3);
	stackpush(&ps, 4);
	stackpush(&ps, 5);
	stackdy(&ps);
	//出栈
	stackpop(&ps);
	stackpop(&ps);
	stackdy(&ps);
	//获取栈顶
	CMMlet n=stacktop(&ps);
	printf("%d\n", n);
	//获取元素个数
 
	stacksize(&ps);
	//销毁栈
	stackdestroy(&ps);
}
 
int main() {
	stackcs();
	return 0;
}

下面就是本期的所有代码，大家可以自己尝试一下

test.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
 
# include<stdio.h>
# include<stdlib.h>
# include<assert.h>
# include<string.h>
# include<errno.h>
 
 
 
 
#define N 10
typedef int CMMlet;
typedef struct stack stack;
静态版本
//struct stack {
//	int top;//栈顶
//	CMMlet val[N]
//};
//动态版本
struct stack {
	int top;//栈顶
	CMMlet* val;
	int capacity;//容量
};
 
//初始化
void stackinit(stack* ps);
//压栈
void stackpush(stack* ps, CMMlet a);
//出栈
void stackpop(stack* ps);
//获取栈顶元素
CMMlet stacktop(stack* ps);
//获取栈中有效元素个数
int stacksize(stack* ps);
//检测栈是否为空（空返回0，非空返回非0）
int stackEmpty(stack* ps);
//销毁栈
void stackdestroy(stack* ps);

test.c

# include"test.h"
 
//初始化
void stackinit(stack* ps) {
	assert(ps);
	ps->val = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
 
//压栈
void stackpush(stack* ps,CMMlet a) {
	assert(ps);
	if (ps->capacity == ps->top) {
		int n = ps->val == NULL ? 4 : ps->capacity * 2;
		CMMlet* cur = (CMMlet*)realloc(ps->val, n * sizeof(CMMlet));
		if (cur == NULL) {
			printf("%s", strerror(errno));
			return;
		}
		ps->val = cur;
		ps->capacity = n;
	}
	ps->val[ps->top] = a;
	ps->top++;
}
 
//出栈
void stackpop(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	ps->top--;
}
 
//获取栈顶元素
CMMlet stacktop(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	return ps->val[ps->top - 1];
}
 
//获取栈中有效元素个数
int stacksize(stack* ps) {
	assert(ps);
	assert(stackEmpty(ps));
	return ps->top;
}
 
//检测栈是否为空（空返回0，非空返回非0）
int stackEmpty(stack* ps) {
	assert(ps);
	return ps->top;
 
}
 
 
//销毁栈
void stackdestroy(stack* ps) {
	assert(ps);
	free(ps->val);
	ps->val = NULL;
	ps->top = ps->capacity = 0;
}

cs.c

#include"test.h"
 
 
 
// 打印栈
void stackdy(stack* ps) {
	for (int i = 0; i < ps->top; i++) {
		printf("%d", ps->val[i]);
	}
	printf("\n");
}
 
//测试函数
 
void stackcs() {
	stack ps;
	//初始化
	stackinit(&ps);
	//压栈
	stackpush(&ps, 1);
	stackpush(&ps, 2);
	stackpush(&ps, 3);
	stackpush(&ps, 4);
	stackpush(&ps, 5);
	stackdy(&ps);
	//出栈
	stackpop(&ps);
	stackpop(&ps);
	stackdy(&ps);
	//获取栈顶
	CMMlet n = stacktop(&ps);
	printf("%d\n", n);
	//获取元素个数
	int a = stacksize(&ps);
	printf("%d\n", a);
	stackdy(&ps);
	//销毁栈
	stackdestroy(&ps);
}
 
int main() {
	stackcs();
	return 0;
}

   以上就是全部内容了，如果有错误或者不足的地方欢迎大家给予建议。