栈

栈的概念

​ 栈是是一种只能在一端进行插入和删除操作的特殊线性结构，允许进行插入和删除操作的一端为栈顶，另外一段为栈底。

栈

​ 向一个栈插入新元素又称作进栈、入栈或 压栈，是把新元素放到栈顶元素的上面。删除元素称作出栈或退栈，是把栈顶元素删除掉。
​

栈Push

​ 栈中元素个数为零时称为空栈，栈也被称为先进后出表。
​

栈Pop

栈的实现

• 顺序栈

  • 结构

    /**
     顺序栈
     */
    typedef struct 
    {
        int top;
        int data[MaxSize];
        
    }SeqStack;
    

  • 初始化

    SeqStack* Init_seqStack(){
       SeqStack *s;
       s = (SeqStack *)malloc(sizeof(SeqStack));
       if (!s)
       {
         printf("创建失败\n");
         return NULL;
       }else{
         s->top = -1;
         printf("创建成功\n");
         return s;
       }
    }
    

  • 进栈

    /*
       压栈
     */
    void push_stack(SeqStack *s,int value){
        //判断是否栈满
        if (s->top == MaxSize - 1)
        {
            printf("栈满\n");
            return;
        }
        s->top++;
        s->data[s->top] = value;
        printf("进栈%d\n",value);
    }
    
    

  • 退栈

    /*
      出栈
     */
    void pop_stack(SeqStack *s){
        if (s->top <= 0)
        {
            printf("栈空\n");
            return;
        }
        printf("出栈%d\n",s->data[s->top]);
        s->top--;
       
    }
    

  • 空栈

    bool isEmptyStack(SeqStack s){
        return (s.top == -1);
    }
    

  • 获取栈顶元素

    int getStackTop(SeqStack s){
        return s.data[s.top];
    }
    

• 链式栈

  • 结构

    /**
     链式栈结点
     */
    typedef struct StackNode
    {
        int  data;
        struct StackNode *next;
    }StackNode,*LinkStackNode;
    
    /*
      链式栈
     */
    typedef struct
    {
        LinkStackNode top;
        int length;
    }LinkStack;
    

  • 初始化

    LinkStack* InitLinkStack()
    {
        LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack));
        if (s == NULL)
        {
          printf("创建失败\n");
          return NULL;
        }
        s->top=NULL;
        s->length=0;
        return s;
    }
    

  • 进栈

    void push_stackNode(LinkStack *s,int value){
       LinkStackNode node = (LinkStackNode )malloc(sizeof(StackNode));
       if (node == NULL)
       {
          printf("压栈失败\n");
          return;
       }
    
       node->data = value;
       node->next = s->top;
       s->top = node;
       s->length = s->length + 1;
    }
    

  • 退栈

    void pop_stackNode(LinkStack *s){
    
       if (s->length == 0)
       {
          printf("空栈\n");
          return;
       }
       LinkStackNode node = s->top;
       s->top = node->next;
       s->length--;
       free(node);
    }
    
    

  • 空栈

    bool isLinkStackEmpty(LinkStack S){
        if (S.count == 0)
            return true;
        else
            return false;
    }
    
    

  • 获取栈顶元素

    int getStackTop(LinkStack S){
        if(S.top == NULL)
            printf("空栈\n");
            return -1;
        else
          return S.top->data;
       
    }