数据结构第6讲链栈

刺骨的言语ヽ痛彻心扉 2022-05-17 08:20 124阅读 0赞

数据结构 第6讲 链栈

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

![这里写图片描述][70]

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

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

链栈的结构体定义：

![这里写图片描述][70 1]

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

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

1.  链栈初始化

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

bool InitStack(LinkStack &S) //构造一个空栈S

S=NULL;
    
    return true;

1.  入栈

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

![这里写图片描述][70 2]

p = new Snode; //生成新结点  
![这里写图片描述][70 3]  
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;

1.  出栈

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

![这里写图片描述][70 4]

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.  取栈顶元素

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

![这里写图片描述][70 5]

int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针

if (S != NULL) //栈非空
    
        return S->data; //返回栈顶元素的值，栈顶指针不变

else

return -1;

链栈基本操作完整代码：

完整代码：

# include #

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

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<

[70]: /images/20220517/33c9ad5e7c36482485ead4b520334e36.png
[70 1]: /images/20220517/45d0eaca31094d35b7530cf475d9a087.png
[70 2]: /images/20220517/4070d838ddd442eba1d4f4987ac691e3.png
[70 3]: /images/20220517/f64f8c6cb4904e42a370ccfafef716fe.png
[70 4]: /images/20220517/2fde667a488647e184fac482e0616cf2.png
[70 5]: /images/20220517/a868af14c1f841218d2c4cd969a7e76a.png