栈的顺序存储结构，链式存储结构及实现

【顺序存储结构】

栈空的条件：s->top == -1;
栈满的条件：s->top == MAX_SIZE-1;
进栈：先将栈顶指针top++，再将元素e放置在栈顶指针所指处; 
出栈：先将栈顶元素赋值给e，再让top--。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct stack {
	int data[MAX_SIZE];
	int top;
}STACK, *PSTACK;

//初始化栈 
void init(PSTACK &s) {
	s = (STACK*)malloc(sizeof(STACK));
	s->top = -1;
}

//销毁栈
void destroyStack(PSTACK s) {
	free(s);	
}

//判断栈是否为空
bool isEmpty(PSTACK s) {
	return s->top==-1;
} 

bool isFull(PSTACK s) {
	return s->top == MAX_SIZE-1;  //c++中面向对象另设成员变量size，因为有参构造时size可能与MAX_SIZE不一样 
} 

//进栈
//top指针先++，再压入元素 
bool push(PSTACK s, int e) {
	if(isFull(s))
		return false;
	s->top++;
	s->data[s->top] = e;
	return true;	
}

//出栈并返回出栈元素
//先保存出栈元素，top指针再-- 
bool pop(PSTACK s, int &e) {
	if(isEmpty(s))
		return false;
	e = s->data[s->top]; 
	s->top--;
	return true;
} 

//取栈顶元素
bool getTop(PSTACK s, int &e) {
	if(isEmpty(s))
		return false;
	e = s->data[s->top];
	return true;
} 

//从底部开始遍历栈
bool stackPrint(PSTACK s) {
	if(isEmpty(s))
		return false;
	for(int i=0;i<=s->top;i++) 	
		printf("%d ",s->data[i]); //可以另写一个函数用于输出
	printf("\n");
	return true;
}

int main() {
	int e;
	PSTACK s;
	init(s);
	if(isEmpty(s)) printf("栈为空！\n");
	for(int i=0;i<=10;i+=2)
		if(!isFull(s))
			push(s,i);
	if(isFull(s)) printf("栈满！\n");
	for(int i=0;i<2;i++)
		if(pop(s,e)) { //只需考虑出栈是否成功，栈是否为空 放在pop函数中判断 
			printf("本次出栈元素为%d\n",e);
		}
	if(!stackPrint(s)) printf("栈为空！\n"); //在调用函数时即会执行函数,也会返回状态，所以不用写else  
	return 0;
}

【链式存储结构】

栈空条件：s->next == NULL;
链式栈不要考虑栈满条件
进栈：新增节点插入到头结点之后
出栈：取出首节点的值并释放首节点 

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

typedef struct node {
	int data;
	struct node *next;
}STACK, *PSTACK;

//初始化栈 
void init(PSTACK &s) {
	s = (STACK*)malloc(sizeof(STACK));
	s->next = NULL;
}

//销毁栈(连头结点一起销毁) 
void destroy(PSTACK s) {
	PSTACK q = s, p = s->next;
	while(p) {
		free(q);
		q = p;
		p = p->next;
	}
	free(q);
}

//判断栈是否为空 
bool isEmpty(PSTACK s) {
	return s->next == NULL;
}

//入栈 
void push(PSTACK s, int e) {
	PSTACK p = (STACK*)malloc(sizeof(STACK));
	p->data = e;
	p->next = s->next;
	s->next = p;
}

//出栈 
bool pop(PSTACK s, int &e) {
	if(isEmpty(s))
		return false;
	PSTACK p = s->next;
	e = p->data;
	s->next = p->next;
	free(p);
	return true;
}

//获取栈顶元素 
bool getTop(PSTACK s, int &e) {
	if(isEmpty(s))
		return false;
	e = s->next->data;
	return true;
}

//从栈顶开始遍历栈
bool print(PSTACK s) {
	if(isEmpty(s))
		return false;
	PSTACK p = s->next;
	while(p) {
		printf("%d ",p->data); //可以另写一个函数用于输出	
		p = p->next;
	}
	printf("\n");
	return true;
}

int main() {
	int e;
	PSTACK s;
	init(s); 
	if(isEmpty(s)) printf("栈为空！\n");
	for(int i=1;i<=10;i+=2)
		push(s,i);
	for(int i=0;i<2;i++)
		if(pop(s,e)) {
			printf("本次出栈元素为%d\n",e);
		}
	if(!print(s)) printf("栈为空");
	destroy(s);
	return 0;
}

一些思考:
设计函数时可以添加一些细节，如销毁栈或判断栈是否为空时先判断栈是否创建，但一般在程序最开始和最末尾就是创建栈和销毁栈，所以本段代码不做此判断。