数据结构第6讲链栈

rainchxy

发布于 2018-09-13 15:59:02

4930

发布于 2018-09-13 15:59:02

文章被收录于专栏：趣学算法趣学算法

数据结构第6讲链栈

进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。顺序栈和链栈图解：

顺序栈是分配一段连续的空间，需要两个指针，base指向栈底，top指向栈顶。而链栈每个结点的地址是不连续的，只需要一个栈顶指针即可。

从上图可以看出，链栈的每个结点都包含两个域，数据域和指针域，是不是和单链表一模一样？那么我们就可以按单链表的定义。

链栈的结构体定义：

链栈的结点定义和单链表一样，只不过它只能在栈顶操作而已。

下面讲解链栈的初始化、入栈，出栈，取栈顶元素等操作（元素以int类型为例）。

1. 链栈初始化

初始化一个空栈，只需要让栈顶指针为空即可。

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

2. 入栈

入栈前要创建一个新结点，将元素e存入该结点的数值域：

p = new Snode; //生成新结点

p->data = e; //将e放在新结点数据域

然后将该结点的指针域指向S，再修改S指针指向该结点。

bool Push(LinkStack &S, int e) //在栈顶插入元素e
{
    LinkStack p;
    p = new Snode; //生成新结点
    p->data = e; //将e放在新结点数据域
    p->next = S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域
    S = p; //修改栈顶指针为p
    return true;
}

3. 出栈

出栈就是要把栈顶元素删除，让栈顶指针指向下一个结点，然后释放该结点空间。因此先用指针p指向栈顶元素（S指针指向的结点），即p=S；然后栈顶指针S指向它的下一个结点，即S=S->next；最后释放p指向的结点，即delete 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;
}

4. 取栈顶元素

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

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

链栈基本操作完整代码：

完整代码：
#include<iostream>
using namespace std;
typedef struct Snode {
    int data; //数据域
    struct Snode *next; //指针域
}Snode,*LinkStack;
bool InitStack(LinkStack &S) //构造一个空栈S
{
    S=NULL;
    return true;
}
bool Push(LinkStack &S, int e) //在栈顶插入元素e
{
    LinkStack p;
    p = new Snode; //生成新结点
    p->data = e; //将e放在新结点数据域
    p->next = S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域
    S = p; //修改栈顶指针为p
    return true;
}
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;
}
int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{
    if (S!=NULL) //栈非空
        return S->data; //返回栈顶元素的值，栈顶指针不变
else
return -1;
}
int main()
{
    int n,x;
    LinkStack S;
    InitStack(S);//初始化一个顺序栈S
    cout <<"请输入元素个数n："  <<endl;
    cin>>n;
    cout <<"请依次输入n个元素，依次入栈："  <<endl;
    while(n--)
{
        cin>>x; //输入元素
        Push(S, x);
    }
    cout <<"元素依次出栈：" <<endl;
    while(S!=NULL)//如果栈不空，则依次出栈
{
cout<<GetTop(S)<<"\t";//输出栈顶元素
Pop(S, x); //栈顶元素出栈
}
    return 0;
}

运行结果：