C语言-实现栈的基本操作(顺序栈)

下面用两种方式来构建顺序栈，分别是将top定义为指针类型和将top定义成指针下标两种形式，实现栈的基本操作。

目录

方法一：

1.1结构定义

1.2 完整代码

1.3测试用代码（用来逐步测试以上栈功能的实现）

1.4 输出结果参考

 方法二：

2.1结构定义

2.2 完整代码

2.3测试用代码（用来逐步测试以上栈功能的实现）

2.4 输出结果参考

方法一：

在这种方法中，设定了flag来对是否为空栈进行判断，在Pop(返回栈顶元素并删除函数)可以将flag的值设为0，即栈空

1.1结构定义

typedef struct {
	Elemtype *base;//栈底指针
	Elemtype *top;//栈顶指针
	int stacksize;//栈大小
} SqStack;

1.2 完整代码

#include 
#include 
#include 
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR -1
int flag = 0; //用于判断是否为空栈，空栈为0，非空为1
typedef char Elemtype;

typedef struct {
	Elemtype *base;//栈底指针
	Elemtype *top;//栈顶指针
	int stacksize;//栈大小
} SqStack;

SqStack InitStack(); //空栈构造函数
void DestroyStack(SqStack *s); //销毁栈函数
void ClearStack(SqStack *s); //清除栈
Elemtype Pop(SqStack *s); //删除栈顶元素并返回其值，否则返回ERROR
int StackEmpty(SqStack *s); //判断是否为空栈,是返回1，否 返回0
int StackLength(SqStack *s);//返回栈的长度
void Push(SqStack *s, Elemtype e); //添加元素入栈
Elemtype GetTop(SqStack *s);//返回栈顶元素
int StackTraverse(SqStack *s);//从栈底向栈顶访问每个元素
SqStack InitStack() {
	SqStack s;
	s.base = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(Elemtype));
	if (s.base != NULL) { //分配内存成功
		s.top = s.base;//栈空的判断
		flag = 0;
		s.stacksize = STACK_INIT_SIZE;
		return s;
	} else
		printf("error!n");
}

void DestroyStack(SqStack *s) {
	if (s->base != NULL) {
		free(s->base);
	}
}

void ClearStack(SqStack *s) {
	while (StackEmpty(s) != 1) {
		Pop(s);
	}
}

int StackEmpty(SqStack *s) {
	if (s->base == s->top && flag == 0)
		return 1;
	else
		return 0;
}

void Push(SqStack *s, Elemtype e) {
	if (s->top - s->base >= s->stacksize) { //栈满，追加空间
		s->base = (Elemtype *)malloc((STACKINCREMENT + s->stacksize) * sizeof(Elemtype));
		if (s->base != NULL) {
			s->top = s->base + s->stacksize ; //将top指针归位到栈顶
			s->stacksize += STACKINCREMENT;
		} else
			printf("error!n");
	}
	if (s->top == s->base && flag == 0) { //如果重新出入的话要改变base指针
		*s->top = e;
		*s->base = *s->top;
		flag = 1;
	} else {
		s->top++;
		*s->top = e;
		flag = 1;
	}
}

Elemtype Pop(SqStack *s) {
	int e;
	if (s->top != s->base) {
		e = *s->top;
		s->top--;
		return e;
	} else if (flag == 1) {
		e = *s->top;
		flag = 0;
		return e;
	}
	printf("error!n");
}


int StackLength(SqStack *s) {
	int len = 1;
	Elemtype *temp;
	temp = s->base;
	while (temp != s->top) {
		len++;
		temp++;
	}
	return len;
}

Elemtype GetTop(SqStack *s) {
	int e;
	if (s->base != s->top) {
		e = *s->top;
		return e;
	} else if (flag == 1) {
		e = *s->top;
		return e;
	} else
		printf("error!n");
}

int StackTraverse(SqStack *s) {
	Elemtype *pf;
	if (StackEmpty(s) == 0) {
		pf = s->base;
		while (pf != s->top) {
			printf("%c ", *pf);
			pf++;
		}
		printf("%c", *pf);
		return 1;
	}
	printf("栈为空！");
	return 0;
}

1.3测试用代码（用来逐步测试以上栈功能的实现）

#include "堆栈.h"

main() {
	//测试初始化一个空栈
	printf("测试InitStack(SqStack *s)：n");
	SqStack s;
	s = InitStack();
	Elemtype e, ch[15], ch1[15];
	puts("请输入要压入栈中的字符串");
	scanf("%s", ch);
	for (int i = 0; i < strlen(ch); i++) {
		printf("存入第%d个字符：%cn", i + 1, ch[i]);
		Push(&s, ch[i]);
	}
	//测试int StackTraverse(SqStack *s)从栈底向栈顶访问每个元素
	//测试Elemtype GetTop(SqStack *s)返回栈顶元素
	printf("测试从栈中访问元素:n");
	Elemtype e1;
	e1 = GetTop(&s);
	printf("栈顶的元素为：%cn", e1);
	printf("栈的长度为: %dn", StackLength(&s));
	printf("请确认您的输入:");
	StackTraverse(&s);
	printf("n");
	//测试 Elemtype Pop(SqStack *s)，逐个弹出栈顶的元素
	printf("测试逐个弹出栈顶元素:n");
	int a;//储存每次弹出的元素
	while (flag != 0) {//如果栈非空
		a = Pop(&s);
		printf("%c ", a);
	}
	printf("n");
	//测试ClearStack(SqStack *s)清空栈操作
	puts("重新为栈赋值:");
	puts("请输入要压入栈中的字符串:");
	scanf("%s", ch1);
	for (int i = 0; i < strlen(ch1); i++) {
		printf("存入第%d个字符：%cn", i + 1, ch1[i]);
		Push(&s, ch1[i]);
	}
	//验证下是否重新入栈成功
	printf("请确认您的输入:");
	StackTraverse(&s);
	printf("n");
	ClearStack(&s);
	printf("执行后结果:");
	StackTraverse(&s);
	//测试销毁栈
	DestroyStack(&s);
	printf("done!");
}

1.4 输出结果参考

 方法二：

在这种方法中，将s.top设置成整型代表指针的下标，栈空时是s.top的值为-1，不存在时s.data为NULL

2.1结构定义

typedef struct {
	Elemtype *data;
	int top;//栈顶指针，这里用int类型表示指针的下标
	int stacksize;
} SqStack;

2.2 完整代码

#include 
#include 
#include 
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char Elemtype;

typedef struct {
	Elemtype *data;
	int top;//栈顶指针，这里用int类型表示指针的下标
	int stacksize;
} SqStack;
Elemtype Pop(SqStack *s);

SqStack InitStack() {
	SqStack s;
	s.data = (Elemtype *)malloc(STACK_INIT_SIZE * sizeof(Elemtype));
	s.top = -1; //表示栈空
	s.stacksize = STACK_INIT_SIZE;
	if (s.data != NULL)
	{}
	else
		printf("Init error!n");
	return s;
}

void DestroyStack(SqStack *s) {
	free(s->data);
}

int StackEmpty(SqStack *s) {
	if (s->top == -1)
		return 1;
	else
		return 0;
}

void ClearStack(SqStack *s) {
	while (StackEmpty(s) != 1) {
		Pop(s);
	}
}

void Push(SqStack *s, Elemtype e) {
	if (s->top >= s->stacksize) {
		s->data = (Elemtype *)malloc((STACK_INIT_SIZE + STACKINCREMENT) * sizeof(Elemtype));
		s->stacksize += STACKINCREMENT;
		if (s->data != NULL) {}
		else
			printf("Push error!n");
	} else {
		s->top++;
		s->data[s->top] = e;
	}
}

Elemtype Pop(SqStack *s) {
	if (StackEmpty(s) != 1 && s->top >= 0) {
		Elemtype e = s->data[s->top];
		s->top--;
		return e;
	}
	printf("Pop error!n");
}

int StackLength(SqStack *s) {
	int len = 0, temp = s->top;
	while (temp >= 0) {
		len++;
		temp--;
	}
	return len;
}

Elemtype GetTop(SqStack *s) {
	if (StackEmpty(s) != 1) {
		return s->data[s->top];
	} else
		printf("GetTop error!n");
}

int StackTraverse(SqStack *s) {
	if (StackEmpty(s) == 1) {
		printf("栈为空！n");
		return 0;
	}
	int temp = 0;
	while (temp <= s->top) {
		printf("%c ", s->data[temp]);
		temp++;
	}
	return 1;
}

2.3测试用代码（用来逐步测试以上栈功能的实现）

#include "数组堆栈.h"

main() {
	//测试初始化一个空栈
	printf("测试InitStack(SqStack *s)：n");
	SqStack s;
	s = InitStack();
	Elemtype e, ch[15], ch1[15];
	puts("请输入要压入栈中的字符串");
	scanf("%s", ch);
	for (int i = 0; i < strlen(ch); i++) {
		printf("存入第%d个字符：%cn", i + 1, ch[i]);
		Push(&s, ch[i]);
	}
	//测试int StackTraverse(SqStack *s)从栈底向栈顶访问每个元素
	//测试Elemtype GetTop(SqStack *s)返回栈顶元素
	printf("测试从栈中访问元素:n");
	Elemtype e1;
	e1 = GetTop(&s);
	printf("栈顶的元素为：%cn", e1);
	printf("栈的长度为: %dn", StackLength(&s));
	printf("请确认您的输入:");
	StackTraverse(&s);
	printf("n");
	//测试 Elemtype Pop(SqStack *s)，逐个弹出栈顶的元素
	printf("测试逐个弹出栈顶元素:n");
	int a;//储存每次弹出的元素
	while (StackEmpty(&s) != 1) { //如果栈非空
		a = Pop(&s);
		printf("%c ", a);
	}
	printf("n");
	//测试ClearStack(SqStack *s)清空栈操作
	puts("重新为栈赋值:");
	puts("请输入要压入栈中的字符串:");
	scanf("%s", ch1);
	for (int i = 0; i < strlen(ch1); i++) {
		printf("存入第%d个字符：%cn", i + 1, ch1[i]);
		Push(&s, ch1[i]);
	}
	//验证下是否重新入栈成功
	printf("请确认您的输入:");
	StackTraverse(&s);
	printf("n");
	ClearStack(&s);
	printf("执行后结果:");
	StackTraverse(&s);
	//测试销毁栈
	DestroyStack(&s);
	printf("done!");
}

2.4 输出结果参考

 有错误的话欢迎指正喔！！