C语言栈的两种实现：顺序栈与链式栈详解

#include<stdio.h>
#include<stdlib.h>
#define maxsize 64

// 定义栈结构体
typedef struct
{
	int data[maxsize]; // 固定大小的数组存储数据
	int top;           // 栈顶指针
} sqstack, *sqslink;

// 初始化栈（设置为空）
void Clearstack(sqslink s)
{
	s->top = -1;
}

// 判断栈是否为空
int Emptystack(sqslink s)
{
	if (s->top < 0)
		return 1; // 空栈返回1
	else
		return 0; // 非空栈返回0
}

// 进栈操作
int Push(sqslink s, int x)
{
	// 检查栈是否已满
	if (s->top >= maxsize - 1)
		return 0; // 满栈，入栈失败
	else
	{
		s->top++;               // 栈顶指针上移
		s->data[s->top] = x;    // 存入数据
		return 1;               // 入栈成功
	}
}

// 出栈操作
int Popstack(sqslink s)
{
	int n;
	// 检查栈是否为空
	if (Emptystack(s) > 0)
		return NULL; // 空栈无法出栈
	else
	{
		n = s->data[s->top]; // 保存栈顶数据
		s->top--;             // 栈顶指针下移
		return n;             // 返回出栈数据
	}
}

void main()
{
	sqslink s1;
	// 动态分配内存
	s1 = (sqslink)malloc(sizeof(sqstack));
	Clearstack(s1); // 初始化
	
	printf("%d\n", s1->top); // 输出初始top值，应为-1
	
	// 循环进栈测试
	for(int i = 0; i <= 10; i++)
	{
		Push(s1, i);
		printf("%d is pushed into stack\n", i);
	}
	
	printf("top is point to %d\n", s1->top); // 当前栈顶位置
	printf("\n");
	
	// 执行一次出栈
	int n = Popstack(s1);
	printf("number %d is poped\n", n);
	printf("top is point to %d\n", s1->top); // 出栈后top位置变化
}

#include<stdio.h>
#include<stdlib.h>

// 定义节点结构体
typedef struct node
{
	int data;
	struct node *next;
} snode, *slink;

// 用于封装出栈结果的结构体，同时返回新栈顶和被弹出的节点
struct Node
{
	slink i; // 新的栈顶指针
	slink n; // 被弹出的旧节点
};

// 清空栈（简化处理，仅重置指针，实际应用中需遍历释放内存）
void Clearstack(slink top)
{
	top = NULL;
}

// 判断栈是否为空
int Emptystack(slink top)
{
	if (top == NULL) return 1;
	else return 0;
}

// 进栈操作
slink Push(slink top, int x)
{
	slink node = NULL;
	node = (slink)malloc(sizeof(snode));
	node->data = x;
	node->next = top; // 新节点指向原来的栈顶
	top = node;       // 更新栈顶为新节点
	printf("*************************\n");
	printf("%d", top->data);
	printf("*************************\n");
	return top; // 返回新的栈顶指针
}

// 出栈操作
struct Node Pop(slink top)
{
	slink node = NULL;
	struct Node result;
	
	if (Emptystack(top))
	{
		result.i = node; // 空栈处理
	}
	else
	{
		int n;
		node = top;          // 记录当前栈顶
		top = node->next;    // 栈顶移动到下一节点
		result.i = top;      // 记录新的栈顶
		result.n = node;     // 记录被弹出的节点
		return result;       // 返回包含新旧栈顶和弹出节点的结果
	}	
}

void main()
{
	slink top_ = NULL;
	
	// 循环进栈
	for(int i = 0; i < 10; i++)
	{
		top_ = Push(top_, i);
		printf("%d is pushed in to the stack\n", i);
	}	
	
	int e;
	e = top_->data; // 查看当前栈顶数据
	printf("top is pointint to %d\n", e);
	printf("\n");
	
	// 执行出栈
	slink node = NULL;
	printf("*************************\n");
	struct Node result = Pop(top_);
	
	if ((result.i) != NULL)
	{
		top_ = result.i;   // 更新外部栈顶指针
		node = result.n;   // 获取被弹出的节点

		e = top_->data;     // 查看新栈顶
		printf("top is pointint to %d\n", e);
		
		int e_node;
		e_node = node->data; // 查看被弹出节点的数据
		printf("the node Poped 's data is pointint to %d\n", e_node);
		free(node);          // 释放内存，防止泄漏
	}
	else
	{
		printf("stack is empty");
	}
}