链栈

基本概念

数据结构的三要素

  • 逻辑结构
    • 线性结构
  • 存储结构
    • 链式存储
  • 数据的运算

费曼理解

1
2
栈结构：
头指针L → [栈顶节点] → [节点2] → ... → [栈底节点] → NULL

就像编绳结一样，一个节点一个结从右往左遍就得从左往右解

内部实现：

1
2
3
4
typedef struct Linknode{
	ElemType data;
	struct Linknode *next;
}*LiStack

复杂度分析：

初始化

1
2
3
4
bool InitStack(LiStack &L){
	L= new Linknode;
	L->next=NULL;
}

判断栈空

1
2
3
4
5
6
7
8
bool isEmpty(LiStack &L){
	if(L-next==NULL){
		return true;
	}
	else{
		return false;
	}
}

入栈

1
2
3
4
5
6
7
void Push(LiStack &L,ElemType e){
	Linknode s;
	s =new Linknode;
	s->data=e;
	s-next=L->next;
	L->next=s;
}

复杂度分析

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

出栈

1
2
3
4
5
6
7
8
9
10
bool Pop(LiStack &L,ElemType &e){
	Linknode s;
	if isEmpty(L)
		return false;
	s=L->next;
	e=s->data;
	L->next=L->next->next;
	delete(s);
	return true;
}

复杂度分析

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

应用场景：