【考研复习 - 数据结构】栈的基本概念及顺序栈的代码实现

【考研复习 - 数据结构】栈的基本概念及顺序栈的代码实现 栈的概念（栈是一种逻辑结构） 栈的定义

• 只允许一端进行插入或者删除操作的线性表

栈的特点

• 后进先出（Last In First Out）(LIFO)

栈的基本操作

• InitStack(&S);【创建】
• DestroyStack(&S);【销毁】
• Push(&S, x);【入栈】
• Pop(&S, &x);【出栈】
• StackEmpty(S);【判空】

栈的常考题

【选择题】

• 题目给出元素的进栈顺序，判断哪个选项的出栈顺序正确

顺序栈的代码实现 （顺序栈是一种存储结构） 顺序栈的定义（数组实现，以栈顶指针指向 -1 为例，最后有栈顶指向 -1和 0 的关键代码实现总结）

#define MaxSize 10		// 定义顺序栈中元素的最大个数
typedef struct{
	int data[MaxSize];	// 使用静态数组存放栈中的元素
	int top;			// 栈顶指针，指向栈顶元素
}SqStack;

一、初始化操作

void InitStack(SqStack &S){
	S.top = -1;			// 将顺序栈的栈顶指针指向-1
}

二、判空

bool StackEmpty(SqStack S){
	if(S.top == -1){
		return true;	// 为空栈，返回true
	}else{
		return false;	// 不为空栈，返回false
	}
}

三、判满

bool StackFull(SqStack S){
	if(S.top == MaxSize - 1){
		return true;	// 满栈，返回true
	}else{
		return false;	// 栈未满，返回false
	}
}

四、进栈操作

bool Push(SqStack &S, int x){
	if(S.top == MaxSize - 1){
		return false;	// 若栈满，则不能再执行进栈操作，返回false
	}
	
	S.data[++S.top] = x;// 先将栈顶指针+1（向上移动一个存储单位），再将元素x插入到当前栈顶指针所指向的位置
	// 上面这一步代码也可以拆分成下面这两步代码，实现效果一样
	// S.top = S.top + 1;
	// S.data[S.top] = x;

	return true;		// 进栈操作执行成功，返回true
}

五、出栈操作

bool Pop(SqStack &S, int &x){
	if(S.top == -1){
		return false;	// 若栈空，则不能再执行出栈操作，返回false
	}
	
	x = S.data[S.top--];// 先将当前栈顶指针所指向的元素赋值给元素x，再将栈顶指针-1（向下移动一个存储单位）
	// 上面这一步代码也可以拆分成下面这两步代码，实现效果一样
	// x = S.data[S.top];
	// S.top = S.top - 1; 

	return true;		// 出栈操作执行成功，返回true
}

六、读取栈顶元素（与出栈操作相似，但是不需要移动栈顶指针）

bool GetTop(SqStack &S, int &x){
	if(S.top == -1){
		return false;	// 若栈空，则不能再执行读取栈顶元素操作，返回false
	}
	
	x = S.data[S.top];	// 将当前栈顶指针所指向的元素赋值给元素x
	
	return true;		// 读取栈顶元素操作执行成功，返回true
}

栈顶指向 -1和 0 的关键代码实现总结 一、栈顶指针指向 -1（S.top = -1）

• 初始化：S.top = -1;
• 判空：if(S.top == -1)
• 判满：if(S.top == MaxSize - 1)
• 入栈：S.data[++S.top] = x;
• 出栈：x = S.data[S.top--]
• 读取栈顶元素：x = S.data[S.top];

二、栈顶指针指向 0（S.top = 0）

• 初始化：S.top = 0;
• 判空：if(S.top == 0)
• 判满：if(S.top == MaxSize)
• 入栈：S.data[S.top++] = x;
• 出栈：x = S.data[--S.top];
• 读取栈顶元素：x = S.data[S.top]

每日一复习点分享，欢迎各位大佬指正错误，希望各位考研人能够一起前行！！！