栈和队列的应用 —— 链栈

栈和队列的应用 —— 链栈

栈可以采用顺序存储(顺序栈)，也可以采用链式存储(链栈)。

顺序栈和链栈

顺序栈是分配一段连续的空间，需要两个指针，base指向栈底，top指向栈顶。

而链栈每个节点的地址都是不连续的，只需一个栈顶指针即可。链栈的节点和单链表节点一样，包含两个域：数据域和指针域。可以把链栈看作一个不带头节点的单链表，但只能在头部进行插入、删除、取值等操作，不可以在中间和尾部操作。

【链表的数据结构定义】

链栈的节点定义和单链表一样，只不过它只能在栈顶那一端操作。

【链表的基本操作】

• 初始化
• 入栈
• 出栈
• 取栈顶元素

【以 int 类型为例】

① 初始化。

初始化一个空栈，链栈是不需要头节点的，因此只需让栈顶指针为空即可。

[算法代码]

bool InitStack(LinkStack &S){ //构造一个空栈S
	S = NULL;
	return true;
}
1
2
3
4

② 入栈。

入栈指将新节点压入栈顶，因为链栈中的第1个节点为栈顶，因此将新节点插入第1个节点的前面，然后修改栈顶指针指向新节点即可。这有点像摞盘子，将新节点摞到栈顶之上，新节点成为新的栈顶。

[完美图解]

首先，生成新节点。入栈前要创建一个新节点，将元素e 存入该节点的数据域

p = new Snode; //生成新节点，用p指针指向该节点
p->data = e //将元素e 放在新节点数据域
1
2

然后，将新节点插入第1个节点的前面，修改栈顶指针指向新节点

“p ->next=S ”指将S 的地址赋值给p 的指针域，即新节点p 的next指针指向S ；
“S =p ”指修改新的栈顶指针为p 。

[算法代码]

bool Push(LinkStack &S , int e){ //入栈，在栈顶插入元素 e
	LinkStack p;
	p = new Snode; //生成新节点
	p->data = e; //将e 存入新节点的数据域中
	p->next = S;  //将新节点p 的next 指针指向S，即将S的地址赋值给新节点的指针域
	S = p; //修改新栈顶指针为p
	return true;  //入栈成功
}
1
2
3
4
5
6
7
8

③ 出栈

出栈指将栈顶元素删除，栈顶指针指向下一个节点，然后释放该节点空间。

其中，“p =S ”指将S 的地址赋值给p ，即p 指向栈顶元素节点；
“S =S ->next”指将S 的后继节点的地址赋值给S ，即S 指向它的后继节点；
“delete p ”指最后释放p 指向的节点空间。

[算法代码]

bool Pop(LinkStack &S , int &e){ //出栈，删除S的栈顶元素，用e保存其值
	LinkStack p;
	if(S == NULL){ //栈为空
		return false;
	}
	e = S->data; //用e 暂存栈顶元素数据
	p = S; //用p 保存栈顶元素地址，以备释放
	S = S-> next; //修改栈顶指针，指向下一个节点
	delete p; //释放原栈元素的空间
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

④ 取栈顶元素。

取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈顶指针并没有改变，如下图所示。
而出栈指删除栈顶元素，栈顶指针指向下一个元素。

[算法代码]

int GetTop(LinkStack S){ //取栈顶元素，不改变栈顶指针
	if(S != NULL){ //栈非空
		return S->data; //返回栈顶元素的值，栈顶指针不变
	}
	else{
		return -1;
	}
}
1
2
3
4
5
6
7
8

顺序栈和链栈的所有基本操作都只需常数时间，所以在时间效率上难分伯仲。在空间效率方面，顺序栈需要预先分配固定长度的空间，有可能造成空间浪费或溢出；链栈每次都只分配一个节点，除非没有内存，否则不会溢出，但是每个节点都需要一个指针域，结构性开销增加。

因此，如果元素个数变化较大，则可以采用链栈，否则可以采用顺序栈。在实际应用中，顺序栈比链栈应用得更广泛。