目录

顺序栈        

链栈  

           栈是限定仅在表尾进行插入或者删除操作的线性表。表尾端称为“栈顶（top）”，表头端称为栈底（bottom）。不含元素的空表称为空栈。

        栈的修改按后进先出的原则进行，即后进先出（last in first out）如下图所示 

顺序栈

下面看顺序栈的结构体定义

typedef struct {
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stacksize;//当前以分配的存储空间
}SqStack;

这里使用一个指针始终指向栈底，和一个栈顶指针指向栈顶元素的上一个位置。若栈顶指针和栈底指针指向同一个位置（top=base），则表示该栈为空栈。每插入一个元素时，指针top增1。

下面直接看代码，栈的最基础的功能。待补全。

//栈的实现

# include <stdio.h>
# include<stdlib.h>
# define STACK_INIT_SIZE 100 //存储空间初始分配量
# define STACKINCREMENT 10 //存储空间分配增量
# define SElemType int
typedef struct {
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stacksize;//当前以分配的存储空间
}SqStack;

void InitStack(SqStack &S) {
	S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base) printf("创建失败");
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

void createStack(SqStack &S, int num) {
	SElemType  elem;
	printf("请输入元素内容");
	while (num > 0) {
		scanf_s("%d", &elem);//修改SElemType注意修改这里------------
		*(S.top)++ = elem;
		num--;
	}
	printf("创建成功\n");
}

SElemType Get_Top(SqStack &S) {
	SElemType e;
	if (S.base == S.top) {
		printf("抱歉，栈空，无元素");
		return NULL;
	}
	e = *(S.top - 1);
	return e;
}

void Push(SqStack &S, SElemType elem) {
	if (S.top - S.base >= S.stacksize) {//栈满
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base) {
			printf("扩容失败");
		}
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*(S.top)++ = elem;
	printf("插入成功");
}

void Pop(SqStack& S) {
	SElemType elem;
	if (S.top == S.base) {
		printf("栈已经空了");
	}
	elem = *--S.top;
	printf("%d已被弹出\n", elem);
	printf("栈顶元素为%d\n", *(--S.top));
	*++S.top;//将头指针上移一个
}

void print(SqStack S) {
	while (*S.top != *S.base) {
		printf("%d ", *S.base++);
	}
	printf("\n");
}

int main() {
	int in = 0;
	int num = 0;
	SElemType elem = 0;
	SqStack S;
	printf("1---创建栈\n");
	printf("2---得到栈顶元素 \n");
	printf("3---插入元素\n");
	printf("4---弹出元素\n");
	printf("11---打印栈\n");
	printf("请输入数字:\n");
	while (in != -1) {
		switch (in){
			case 1:
				InitStack(S);
				printf("请输入个数\n");
				scanf_s("%d", &num);
				createStack(S, num);break;
			case 2:
				printf("栈顶元素是%d\n", Get_Top(S));break;
			case 3:
				printf("请输入插入的元素");
				scanf_s("%d", &elem);//修改SElemType注意修改这里------------
				Push(S, elem);break;
			case 4:
				Pop(S);break;
			case 11:
				print(S);break;
		}
		scanf_s("%d", &in);
	}
	return 0;
}

链栈

        在实现链栈后，其实其就是一个简单的单链表，即插入和删除都只操作最后一个元素即可。

        链栈比顺序栈更灵活一点。即每次插入一个元素时，使用malloc函数申请一个新的空间。删除元素时，我是这样的思路，pop函数传入一个链栈的头指针，该指针指向栈底元素。设栈底元素为a。此时不知道后面有几个元素。假设后面存在元素以abcd的顺序排列。当a的next不为空时（b存在），此时分两种情况。第一种，如果a的next的next不为空。即存在c。则将a的next的next设为空（b的next=null）。此时c就与栈没有关系了。第二种，如果a的next的next为空，即不存在c。则将a的next设为空。此时b与栈就没有关系了。

#include<stdio.h>
#include <malloc.h>
#define ElemType int
typedef struct Node{
	ElemType data;
	Node* next;
}*LinkStack, Node;//链栈


LinkStack InitLinkStack() {
	LinkStack Ls;
	Ls = (LinkStack)malloc(sizeof(Node));
	Ls->next = NULL;
	return Ls;//返回头结点
}

void createLinkStack(LinkStack L, int num) {
	ElemType Edata;
	LinkStack assoL = L;//栈底的副本
	Node* newL;
	printf("请分别输入元素\n");
	while (num > 0) {
		scanf_s("%d", &Edata);
		newL = (Node*)malloc(sizeof(Node));
		newL->next = NULL;
		newL->data = Edata;
		assoL->next = newL;//将新元素给栈顶
		num--;
		assoL = newL;
	}
	//assoL = L;
}

void printStack(LinkStack L) {
	LinkStack assoL = L;//栈底的副本
	while (assoL->next != NULL) {
		assoL = assoL->next;
		printf("%d ", assoL->data);
		
	}
	//assoL = L;
}

void push(LinkStack L, ElemType Edata) {
	LinkStack assoL = L;//栈底的副本
	while (assoL->next != NULL) {
		assoL = assoL->next;
	}//找到栈顶
	Node* newL = (Node*)malloc(sizeof(Node));
	newL->next = NULL;
	newL->data = Edata;
	assoL->next = newL;
	//assoL = L;
}

void pop(LinkStack L) {
	LinkStack assoL = L;//栈底的副本
	if (assoL->next == NULL) {
		printf("栈以空");
		return;
	}
	while (assoL->next != NULL) {
		if (assoL->next->next != NULL) {
			assoL = assoL->next;
		}
		else {
			assoL->next = NULL;
			break;
		}
	}
	printf("弹出成功\n");
}
//获取栈顶元素
ElemType getTop(LinkStack L) {
	Node* assoL = L;
	while (assoL->next != NULL) {
		assoL = assoL->next;
	}
	return assoL->data;
}


int main() {
	LinkStack L = NULL;
	int num = 0;
	int in = 0;
	ElemType data = 0;
	printf("请输入数字：\n");
	printf("1---创建栈：\n");
	printf("2---插入：\n");
	printf("3---弹出：\n");
	printf("4---获取栈顶元素：\n");
	printf("9---打印栈：\n");
	printf("-1---退出：\n");
	while (in != -1) {
		switch (in) {
		case 1:
			L = InitLinkStack();
			printf("请输入元素的个数\n");
			scanf_s("%d", &num);
			createLinkStack(L, num);
			break;

		case 2:
			printf("请输入插入的元素：\n");
			scanf_s("%d", &data);
			push(L, data);
			printf("插入成功\n");
			break;
		case 3:
			pop(L);
			break;
		case 4:
			data = getTop(L);
			printf("栈顶元素：%d\n", data);
			break;
		case 9:
			printf("栈内元素是：\n");
			printStack(L);
			printf("\n");
			break;

		case -1:
			return 0;
		}
		scanf_s("%d", &in);
	}
}