[C++知识库]顺序栈及增删改查（c语言实现）

栈是一种特殊的线性表，只能由栈顶进入栈顶删除，即后进先出。(FIFO)类似手电筒放入电池，先放入的只能最后取出。

?栈可用顺序表和链表两种方式表示即顺序栈和链栈

本文采用两种方式分别建立栈

1、以top作为栈顶指针，创建静态数组，初始化top=-1即可

top类似顺序表中length

#define MAXSIZE 10           //定义最大元素个数
typedef struct stack {
	int data[MAXSIZE];       //用数组存放栈中的元素
	int top;                //栈顶指针
}Stack;

2、以栈顶与栈底双指针操作，动态开辟空间

后面为方便操作将top指针指向最后元素的后继位置

#define MAXSIZE 10           //定义最大元素个数
typedef struct stack{
	SElemType *top;        //栈顶指针 
	SElemType *base;       //栈底指针
	int stacksize;         //当前已经分配的存储空间 
}stack;

初始化栈

静态数组方式只需要将top=-1。不过多赘述

动态开辟空间方式需先开辟一块空间后将top指针与base指针相等即可。

void InitStack(Stack S) {
	S.base = (Stack*)malloc(MAXSIZE);//开辟空间为 MAXSIZE
	if (!S.base) {                    //确定开辟空间成功
		prinff("开辟空间失败");
	}
	else {
		S.base == S.top;
	}
}

?入栈操作（即增加）

静态数组方式：①?判断栈空间是否满 ，注意下标? ②?栈顶指针+1 ③给数组赋值

注意：因为初始化top从-1开始，因此先++

Stack InsertStack(Stack S) {
	if (S.top==MAXSIZE-1) { //判断栈未满，下标为MAXSIZE-1
		printf("栈空间已满");
	}else{
		S.top++;
		S.data[0] = 1;   //加入数值
	}
	return S;
}

动态空间方式：①?判断栈空间是否满,，注意判断条件?②? 赋值? ③栈顶指针+1

注意：由图2可知，要保证S.top始终指向空位置，并且S.top-S.base?值小于MAXSIZE

Stack InsertStack(Stack S,int e) { 
	if (S.top - S.base == MAXSIZE) { //判断栈空间是否满
		printf("栈空间满");
	}
	{
		*S.top = e;           //栈顶值为e
		S.top++;             //栈顶指针+1  等价于*S.top++=e;
		return	 S;
	}

?出栈操作（即删除）

静态数组方式：①?判断栈空间是否满 ，注意下标? ②?栈顶指针+1 ③给数组赋值

Stack DeletStack(Stack S) {
	if(S.top==0){          //判断栈是否为空
		printf("栈已经空了");
	}
	else {
		int e = 0;         //用e存下要删除的元素
		e = S.data[S.top];
		S.top--;	      //栈顶指针向下移动
	}
}

动态空间方式：①?判断栈空间是否满，注意判断条件?②? 栈顶指针移动? ③?拷贝要删除元素给e

Stack DeletStack(Stack S) {
	if(S.top==S.base){    //判断栈为空
		printf("栈为空");
	}
	else {
		int e = 0;
		S.top--;
		e = *S.top;   //等价于 e==*S.top--; 先赋值再--		
	}
}

栈改/查

栈只能查/改栈顶元素，因此直接将栈顶元素返回或修改即可。