C/C++数据结构之链栈详解
C/C++数据结构之链栈详解
链栈是采用链式存储结构实现的栈，通常用单链表来表示。与顺序栈相比，链栈不需要预先分配固定大小的内存空间，可以动态分配空间，更加灵活。本文将详细介绍链栈的定义、特点、表示和实现，以及链栈与递归的关系，并通过代码示例帮助读者更好地理解和掌握链栈这一数据结构。
一.链栈的定义和特点
链栈是指采用链式存储结构实现的栈，通常用单链表来表示。由于对栈的操作是在栈顶插入和删除元素，以链表的头部作为栈顶是最方便的。链栈包含了节点，数据域，指针域。
链栈与顺序栈不同，不需要预先分配固定大小的内存空间，可以动态分配空间，节约内存空间。需要考虑指针指向和内存动态分配，比顺序栈复杂一点。
二.链栈的表示和实现
1.链栈的存储结构
链栈由一个单链表构成，其中数据域用于存储数据元素，指针域用于指向下一个结点，由此构成链式结构。
前面单链表的内容就不多赘述，直接上算法描述：
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
其中SElemType，StackNode为定义结构，需要加上：
typedef int Status;
typedef int SElemType;
2.初始化
链栈的初始化操作就是构造一个空栈，因为不用设置头节点，所以直接将栈顶指针置空就行。
代码部分：
Status InitStack(LinkStack &S)
{
S=NULL;
return OK;
}
3.入栈
和顺序栈的入栈操作不同，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个节点空间。
①为入栈元素e分配空间，用指针p指向。
②将新节点数据域赋为e。
③将新节点插入栈顶。
④修改栈顶指针为p
代码部分：
Status Push(LinkStack &S,SElemType e)
{
LinkStack p;
p=new StackNode; //生成新节点
p->data=e; //将新节点数据域置为e
p->next=S; //将新节点插入栈顶
S=p; //修改栈顶指针为p
return OK;
}
4.出栈
和顺序栈一样，链栈在出栈前需要判断栈是否为空，链栈在出栈后需要释放出栈元素的栈顶元素的栈顶空间。
①判断栈是否为空，若空返回ERROR。
②将栈顶元素赋给e。
③临时保存栈顶元素的空间。
④修改栈顶指针，指向新的栈顶元素。
⑤释放原栈顶元素的空间。
代码部分：
Status Pop(LinkStack &S,SElemType &e)
{
LinkStack p;
if(S==NULL)
return ERROR; //栈空
e=S->data; //将栈顶元素赋给e
p=S; //用p临时保存栈顶元素空间
S=S->next; //修改栈顶指针
delete p; //释放原栈顶元素空间
return OK;
}
5.取栈顶元素
与顺序栈一样，当栈非空时，取栈顶元素操作返回当前元素的值，栈顶指针S保持不变。
代码部分：
SElemType GetTop(LinkStack S)
{
if(S!=NULL)
return S->data;
}
6.遍历链栈
①用一个while循环，当栈为空时退出循环。
②创建一个结点指向栈顶元素。
③输出结点p的数据域。
④结点p向后移。
Status OutStack(LinkStack &S)//遍历栈
{
LinkStack p;
p=S;
while(p!=NULL) //循环条件
{
cout << p->data<<; //输出数据
p=p->next; //结点后移
}
return OK;
}
三.栈与递归
栈有一个重要作用是在程序设计语言中实现递归。递归是算法设计常用的手段，它通常可把一个大型复杂问题的描述和求解变得简洁和清晰。
1.定义是递归的
有很多数学函数是递归定义的，比如阶乘函数：
long Fact(long n)
{
if(n==0) return 1; //递归终止条件
else return n*Fact(n-1); //递归步骤
}
2.数据结构是递归的
对于链表，其节点LNode的定义由数据域data和指针域next组成，而指针域是一种指向LNode类型的指针，即LNode的定义又用到了自身。所以链表是一种递归的数据结构。
遍历输出链表中各个结点的递归算法
①如果p为NULL，递归终止。
②否则输出p->data，p指针向后继结点继续递归。
算法描述：
void TraverList(LinkList p)
{
if(p==NULL) return; //递归终止
else
{
cout << p->data << endl; //输出当前结点的数据域
TraverList(p->next); //p指向后继结点继续递归
}
}
四.链栈的简单操作
编写程序，实现顺序栈和链栈的初始化、入栈、出栈、取栈顶元素操作。
1.完整代码
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <windows.h>
#include <cstring>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
Status InitStack(LinkStack &S)
{
S=NULL;
return OK;
}
Status Push(LinkStack &S,SElemType e)
{
LinkStack p;
p=new StackNode;
p->data=e;
p->next=S;
S=p;
return OK;
}
Status Pop(LinkStack &S,SElemType &e)
{
LinkStack p;
if(S==NULL)
return ERROR;
e=S->data;
p=S;
S=S->next;
delete p;
return OK;
}
SElemType GetTop(LinkStack S)
{
if(S!=NULL)
return S->data;
}
Status OutStack(LinkStack &S)//遍历栈
{
LinkStack p;
p=S;
while(p!=NULL)
{
cout << p->data<<" ";
p=p->next;
}
return OK;
}
int main()
{
SetConsoleOutputCP(CP_UTF8);
LinkStack s;
int choose,i,num,flag=0;
SElemType a,t;
cout << "1.初始化" << endl;
cout << "2.入栈" <<endl;
cout << "3.读栈顶元素" << endl;
cout << "4.全部出栈" << endl;
cout << "5.部分出栈" << endl;
cout << "6.遍历栈元素" << endl;
cout << "0.退出" << endl;
choose =-1;
while(choose!=0)
{
cout << "请选择：" <<endl;
cin >> choose;
switch(choose)
{
case 1:
if(InitStack(s))
{
cout << "成功对栈进行初始化" << endl;
flag=0;
}
else cout << "初始化栈失败" << endl;
break;
case 2:cout << "进栈的元素数目是：" << endl;
cin >> num;
for(i=1;i<=num;i++)
{
cout << "请输入第 "<<i<<"个元素：" << endl;
cin >> a;
Push(s,a);
}
flag=1;
cout << "输入元素结束" << endl;
break;
case 3:
if(flag!=0)
cout << "栈顶元素为：\n" << GetTop(s) << endl;
else cout << "栈中无元素，请重新选择" <<endl;
break;
case 4:if(flag!=0)
{
flag=0;
cout << "依次弹出的栈顶元素为：" << endl;
while(Pop(s,t))
cout << t << " ";
cout << endl;
}else
cout << "栈中无元素，请重新选择" << endl;
break;
case 5:
if(flag==0)
cout << "栈中无元素，请重新选择" << endl;
else
cout << "出栈元素数目是：" << endl;
cin >> num;
cout << "依次弹出的栈元素为：" << endl;
for(i=1;i<=num;i++)
{
if(Pop(s,t))
cout << t << " ";
else
flag=0;
}
cout << endl;
break;
case 6:
if(flag==0)
cout << "栈中无元素，请重新选择" <<endl;
else
cout << "栈中元素依次为：" << endl;
OutStack(s);
cout << endl;
break;
}
}
return 0;
}