栈的实现

本文通过多文件编写形式，其中mystack.h文件是一些成员变量的定义和函数的定义。mystack.c文件用于函数的实现

参考C++中栈的函数接口，使用C语言创建对应的数据结构：

1. stack.push()：往栈头添加元素
2. stack.pop()：从栈头移除第一个元素
3. stack.top()：返回栈顶元素
4. stack.empty()：判断栈是否为空
5. stack.size()：返回栈的大小

mystack.h文件：

#ifndef MYSTACK_H
#define MYSTACK_H

//函数声明
int stack_pop(void);
int stack_push(int x);
int stack_top(void);
int stack_empty(void);
int stack_size(void);

//链表数据结点
typedef struct ListNode {
	struct ListNode* next;
	int val;
}ListNode;

//构建栈的结构体，其中函数指针指向具体实现的函数
typedef struct MyStack {
	int (*pop)(void);
	int (*push)(int);
	int (*top)(void);
	int (*empty)(void);
	int (*size)(void);
	ListNode head;
}MyStack;

MyStack stack;

int stack_init(void);

#endif

mystack.c文件：

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

int stack_init() {
	//将函数指针指向函数本体
	stack.pop = stack_pop;
	stack.push = stack_push;
	stack.empty = stack_empty;
	stack.top = stack_top;
	stack.size = stack_size;

	//头结点中存储栈中元素个数
	stack.head.val = 0;
	stack.head.next = NULL;
	return 0;
}

//弹出栈中第一个元素
int stack_pop() {
	int result = 0;
	if (stack.head.val == 0) {
		printf("栈中没有元素，无法弹出");
		exit(-1);
	}
	else {
		ListNode* p = stack.head.next;
		stack.head.next = p->next;
		result = p->val;
		free(p);
		stack.head.val--;
	}
	return result;
}

//创建新结点，运用头插法插入到栈最前端
int stack_push(int x) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->val = x;
	p->next = stack.head.next;
	stack.head.next = p;
	stack.head.val++;
	return 0;
}

//若栈中有元素，返回0。否则返回1
int stack_empty() {
	if (stack.head.val)
		return 0;
	return 1;
}

//若栈中没有元素返回-1。否贼返回首元素的val
int stack_top() {
	if (!stack.head.val) {
		printf("栈中没有元素");
		return -1;
	}
	return stack.head.next->val;
}

//返回头结点存储的栈中元素个数
int stack_size() {
	return stack.head.val;
}