顺序栈

基本概念

数据结构的三要素

• 逻辑结构
  • 线性结构
• 存储结构
  • 顺序存储
• 数据的运算

费曼理解

栈就像一个一次只能放或拿一件东西的口袋，你先放进去的只有在后面放进去的拿出来后才能拿出来。

内部实现：

define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int top
}SqStack;

复杂度分析：

初始化栈

void InitStack(SeStack &S){
	S.top=-1;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

判断栈空

bool StackEmpty(SqStack S){
	if(S.top==1)
		return true;
	else
		return false;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

进栈（入栈）

bool Push(SqStack &S,ElepType x){
//边界判断
	if(S.top==MaxSize-1)
		return false;
	S.top=S.top+1;
	S.data[S.top]=x;
	//S.data[++S.top]==x
	return true;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

出栈

bool Pop(SqStack &S,ElepType &x){
	if(S.top==-1)
		return false;
	x=S.data[S.top];
	S.top--;
	return true;
	//只是逻辑上的删除，内存对应地址数据仍然存在
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

获取栈顶元素

bool GetTop(SqStack S,ElemType &x){
	if(S.top==-1)
		return false;
	x=S.data[S.top];
	return true;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

应用场景：