一、栈的基本概念

栈是只允许在一端进行插入或删除操作的线性表
逻辑结构：与线性表相同
数据的运算：插入、删除操作有所区别
特点：后进先出

二、栈的顺序存储的实现

1.栈的定义和初始化

注意：在内存中还要申请top栈顶指针空间，top记录的是数组的下标
栈顶指针记录的是数组的下标

#define MaxSize 10       //定义栈中元素的最大个数

typedef struct 
{
	int data[MaxSize];  //静态数组存放栈中元素
	int top;            //栈顶指针

}SqStack;

void InitStack()
{
     S.top = -1;    //初始化栈顶指针
}

void testStack()
{
     SqStack S;    //声明一个顺序栈
     InitStack(S);

}

2.判断栈空

bool StackEmpty(SqStack S){
	if(s.top == -1){    //栈空
		return true;
	}else{
		return false;
	}
}

3.入栈和出栈操作

//新元素入栈
bool push(SqStack &s,int x)
{
	if(S.top == MaxSize-1){ //是否栈满
		return false;
	}
	S.top = S.top + 1;   //指针先加1
	S.data[S.top] = x;   //新元素入栈    S.data[++S.top] = x; 
	return true;
}

//出栈操作
bool Pop(SqStack &S,int &x)//注意引用符号
{
	if(S.top == -1){  //栈空
		return false;
	}
	x = S.data[S.top]; //栈顶元素先出栈  x = S.data[S.top--]
	S.top = S.top - 1; //指针减1
	return true;
}

4.读栈顶元素

//读栈顶元素
bool GetTop(SqStack S,int &x)
{
	if(S.top == -1){
		return false;
	}
	x = S.data[S.top]; //x记录栈顶元素
	return true;
}

三、共享栈

为提高内存空间利用率，两个栈共用一片空间

#define MaxSize 10       //定义栈中元素的最大个数

typedef struct 
{
	int data[MaxSize];  //静态数组存放栈中元素
	int top0;            //0号栈栈顶指针
    int top1;           //1号栈栈顶元素

}ShStack;

void InitStack(ShStack &S)
{
	S.top0 = -1;
	S.top1 = MaxSize;
}

栈满条件：top0 + 1 == top1