数据结构之栈

1：栈的结构体定义：

typedef struct Satck{
	int* base;
	int top;
	int length;
}Stack;
//base记录的是栈的开辟的空间的首地址
//栈的下标从0开始，top总是指在栈中已经存储的元素的下一个位置，由于栈是先进后出类型，
//所以base所指的位置在已存储的元素的上边。刚开始栈为空，元素数为0所以栈的top指向0位置
因此top的大小也为栈存储的元素的数量
//length则代表着栈最多的可以存储的元素的上限

2：栈的初始化

void InitStack(Stack &a){
	a.base=(int*)malloc(5*sizeof(int));
	a.length=5;
	a.top=0;
}
//由于我们要存储的是int类型的变量，所以我们开辟int类型的大小为5的空间，最大长度wei5
初始化后栈为空，所以top指向0

3：判断栈是否为空

bool isempty(Stack &a){
	if(a.top==0){
		return true;
	}
	return false;
}
//很简单看看top是否为0即可

4：获取栈的已经存储的元素的数量

int length(Stack &a){
	return a.top;
}
//top就是栈的已经存储的元素的数量

5：入栈

void offer(Stack &a,int b){
	if(a.top>=a.length){
		a.base=(int*)realloc(a.base,(a.length+5)*sizeof(int));
		a.length=a.length+5;
	}
	a.base[a.top]=b;
	a.top++;
}//把元素b放进栈a里边的操作
首先我们要判断top是否已经到达我们开辟得到空间极限也就是top的大小是否已经到达length了，如果已经等于length我们再添加一个元素，top++的话，就已经超过我们开辟的空间大小，所以我们再top等于length时，来对栈进行扩容操作，如何操作呢，使用realloc函数来再源地址上进行扩容，会保护源地址的存储的元素不会丧失。
realloc返回的和malloc一样，但是要传入的参数首先是原地址，其次是开辟的空间大小（在这里要加上源地址存储的空间大小）。
我们把元素存入top位置里边，然后top加加

6：出栈

void poll(Stack &a,int &dd){
	if(a.top==0){
		return;
	}
	a.top--;
	dd =a.base[a.top]; 
}
//首先在出栈前要先一步判断栈是否为空，如果为空栈就不需要出栈了，直接结束程序
否则top--出栈

7：获取栈的栈顶元素但是不出栈

void peek(Stack &a,int &dd){
	if(a.top==0){
		return;
	}
	dd=a.base[a.top-1];
}//获取栈顶元素，首先判断栈是否为空，若是空，就不需要在再操作了，不为空，获取栈顶元素

8：总代码以及样例展示

#include
using namespace std;
typedef struct Satck{
	int* base;
	int top;
	int length;
}Stack;
void offer(Stack &a,int b){
	if(a.top>=a.length){
		a.base=(int*)realloc(a.base,(a.length+5)*sizeof(int));
		a.length=a.length+5;
	}
	a.base[a.top]=b;
	a.top++;
}
void poll(Stack &a,int &dd){
	if(a.top==0){
		return;
	}
	a.top--;
	dd =a.base[a.top]; 
}
void peek(Stack &a,int &dd){
	if(a.top==0){
		return;
	}
	dd=a.base[a.top-1];
}
bool isempty(Stack &a){
	if(a.top==0){
		return true;
	}
	return false;
}
int length(Stack &a){
	return a.top;
}
void InitStack(Stack &a){
	a.base=(int*)malloc(5*sizeof(int));
	a.length=5;
	a.top=0;
}
void test(){
	Stack ss;
	InitStack(ss);
  cout<<isempty(ss)<
	cout<<length(ss)<
	offer(ss,1);
	offer(ss,2);
	offer(ss,3);
	cout<0]<<" "<1]<<" "<2]<<"  "<" "<
    int e;
	poll(ss,e);
	cout<" "<
    peek(ss,e);
    cout<" "<
 
}
int main(){
	test();
	return 0;
}