#include<stdio.h>
#include<stdlib.h>
/*
	栈：是只允许在一端进行插入或删除操作的线性表。
	栈顶：允许进行插入或删除的那一端
	栈底：固定的，不允许进行插入或删除的那一端
	栈的特性：后进先出
	存储方式：1. 顺序存储（顺序栈）  2. 链式存储（链式栈）
*/

/*
    在顺序栈的基本操作中，决定是传入一级指针还是只传入栈的变量，主要取决于操作是否需要修改栈的内部状态。
	1. 需要传入一级指针的情况
	当操作需要修改栈的内部状态，比如改变栈顶指针 top 的值或者修改栈中存储的数据时，就需要传入一级指针。
	这是因为在 C 语言里，函数参数传递是值传递，若直接传入栈的变量，函数内部对该变量的修改不会影响到原变量。
	而通过传入指针，函数可以直接访问和修改原变量所指向的内存。

	2. 只需要传入栈的变量的情况
	当操作不需要修改栈的内部状态，仅仅是读取栈的信息时，就可以只传入栈的变量。

*/

/*
   以下是顺序栈实现
   它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前的栈顶元素的位置
*/


#define MaxSize 50
typedef int ElemType;
typedef struct SqStack {
	ElemType data[MaxSize];  //存放栈中元素
	int top;  //栈顶指针（注意，它不是实际意义上的指针变量，进行存放指针变量。这里说它是指针，意思是说，它指示了当前栈顶元素的位置，在第pos个位置。
}SqStack;

// 操作1——初始化
void InitSeqStack(SqStack* s) {
	s->top = -1;  //初始化栈顶的位置
}

/*
    这里设置初始栈顶指针s.top = -1,
	栈空条件是s.top = -1;栈满条件是s.top = MaxSize - 1
	则进栈时指针s.top+1,再将元素加入栈顶；出栈时先取出栈顶元素，后指针s.top - 1
	
	但如果设置初始栈顶指针s.top = 0,
	栈空条件是s.top = 0;栈满条件是s.top = MaxSize
	则进栈时将元素加入栈顶,再指针s.top+1；出栈时先指针s.top - 1，后取出栈顶元素	
*/

// 操作2——判空
int SqStackEmpty(SqStack s) {
	return s.top == -1;
}

// 操作3——判满
int SqStackFull(SqStack s) {
	return s.top == MaxSize - 1;
}

// 操作4——入栈,将元素加到栈顶
int push(SqStack* s, ElemType value) {
	// 1. 判满
	if (SqStackFull(*s))
	{
		printf("栈满，无法入栈!\n");
		return -2;
	}
	// 2. 指针top + 1，再将值加入到栈顶
	s->top++;
	s->data[s->top] = value;
	return 0;  //入栈成功
}

// 操作5——出栈
int pop(SqStack* s, ElemType* value) {
	//1. 判空
	if (SqStackEmpty(*s))
	{
		printf("栈空，无法有元素出栈!\n");
		return -1;
	}
	//2. 先取出栈顶元素，再指针top - 1
	*value = s->data[s->top];
	s->top--;
	return 0;  //出栈成功
}

// 操作6——获取栈顶元素
int getTop(SqStack s,ElemType *value) {
	//1. 判空
	if (SqStackEmpty(s))
	{
		printf("栈空，无法有元素出栈!\n");
		return -1;
	}
	//2. 获取栈顶元素
	*value = s.data[s.top];
	return 0;  
}

// 操作7——打印栈中元素
void printSqStack(SqStack s) {
	if (SqStackEmpty(s))
	{
		printf("栈空!\n");
		return;  //提前结束该函数
	}
	printf("栈中的元素（从栈底到栈顶）为: ");
	for (int i = 0; i <= s.top; i++) {
		printf("%d ", s.data[i]);
	}
	printf("\n");
}

// 操作8——销毁栈
void destroySqStack(SqStack* s) {
	// 由于顺序栈使用的是静态数组，不需要显式释放内存
	// 只需要将栈顶指针置为 -1 表示栈为空
	s->top = -1;
}

int main() {
	SqStack s;
	InitSeqStack(&s);

	// 测试入栈操作
	push(&s, 11);
	push(&s, 22);
	push(&s, 33);
	printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22 33

	// 获取栈顶元素
	ElemType value;
	if (getTop(s,&value) == 0)
	{
		printf("当前栈顶元素为：%d\n", value); // 当前栈顶元素为：33
	}

	//测试出栈操作
	if (pop(&s,&value) == 0)
	{
		printf("出栈的元素为：%d\n", value);  // 出栈的元素为：33
	}
	printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22

	//销毁栈
	destroySqStack(&s);
	printSqStack(s);  // 栈空!

	return 0;
}