【数据结构】计算机考研随记【栈】

// LIFO:Last IN First Out 后进先出 

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

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

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

// 还有一种初始化方法
// 让top指向下一个可以插入元素的位置，而不是最后一个位置 
// 即初始化时S.top=0，之后判断栈满|空的条件分别改变就行 

// 判断栈空
bool StackEmpty(SqStack S) {
	return (S.top==-1);  // top=-1表示栈空
}

// 判断栈满
bool StackFull(SqStack S) {
	return (S.top==Maxsize-1);  // top=Maxsize-1表示栈满
}

// 新元素入栈
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];  // 栈顶元素先出栈
	S.top=S.top-1;  // 指针再减1
	// 高级写法
	// x=S.data[S.top--];
	return true;
}

// 读取栈顶元素
bool GetTop(SqStack S,int &x){
	if(S.top==-1)return false; // 栈空报错
	x=S.data[S.top];  // x记录栈顶元素 
	return true;
} 
//
//int main() {
//	SqStack S;  // 声明一个顺序栈
//	return 0;
//}

typedef struct Linknode {
	int data;  // 数据域
	struct Linknode *next;  // 指针域
} *LiStack;  // 栈类型定义

// 对应在单链表那一节的内容
// 区别在于只能在表头的位置插入和删除，表示进栈出栈

// 推荐采取不带头结点的单链表实现。 

// 共享栈就是同一片内存空间中逻辑上的两个栈双向奔赴的过程
#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 

//int main() {
//	ShStack S;  // 声明一个共享栈
//	return 0;
//}