数据结构学习心得——顺序栈和链栈

素颜马尾好姑娘i 2022-06-09 00:59 403阅读 0赞

## 栈的定义 ##

栈是限定尽在表尾进行插入或者删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表。  
![这里写图片描述][SouthEast]  
和线性表类似，栈也有两种存储表示方法。  
顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序栈中的位置。这里以top=-1表示空栈。  
链式栈可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

## 代码实现 ##

已下C++代码分别实现了顺序栈，链栈的初始化，入栈和出栈的一系列操作。链栈的入栈操作类似于链表的头插法创建链表。

#include <iostream>
    
    using namespace std;
    
    //顺序栈定义
    typedef struct SqStack
    {
        int data[20];
        int top;
    }SqStack;
    
    //链栈结点定义
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    
    //初始化顺序栈
    void initStack(SqStack &st)
    {
        st.top = -1;
    }
    
    //判断顺序栈空
    int isEmpty(SqStack st)
    {
        if(st.top == -1)
            return 1;
        else
            return 0;
    }
    
    //顺序栈进栈
    int push(SqStack &st,int x)
    {
        if(st.top==20)
        {
            return 0;
        }
        else
        {
            st.data[++st.top]=x;
            return 1;
        }
    }
    
    //顺序栈出栈
    int pop(SqStack &st,int &x)
    {
        if(isEmpty(st))
        {
            return 0;
        }
        else
        {
            x = st.data[st.top--];
            return 1;
        }
    }
    
    //初始化链栈
    void initLNodeStack(LNode *&L)
    {
        L = new LNode;
        L->next = NULL;
    
    }
    //链栈判断栈空
    int isLNodeEmpty(LNode *L)
    {
        if(L->next == NULL)
            return 1;
        else
            return 0;
    }
    
    //链栈进栈
    void pushLNode(LNode *&L,int x)
    {
        LNode *p = new LNode;
        p->data = x;
        p->next = L->next;
        L->next = p;
    
    }
    //链栈出栈
    int popLNode(LNode *&L,int &x)
    {
        if(isLNodeEmpty(L))
        {
            return 0;
        }
        else
        {
            LNode *p = new LNode;
            p = L->next;
            L->next = p->next;
            x = p->data;
            delete p;
            return 1;
        }
    
    }
    int main()
    {
        return 0;
    }

[SouthEast]: /images/20220609/87c8ad985a25409ab40b1740bb578d80.png