栈—链式结构

╰+哭是因爲堅強的太久メ 2024-04-17 17:48 71阅读 0赞

1、定义

将链表的头部作为栈顶，尾部作为栈底，可带头结点，也可不带头结点

特点：  
\*先进后出  
\*存储单元逻辑上连续但地址不一定连续  
\*链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成  
![在这里插入图片描述][20190828124316683.png]  
2、优点

\*一般不会出现栈满情况，除非没有空间导致malloc分配失败。  
\*采用链栈存储方式的优点是，当栈中元素个数变化较大，准确数字难以确定时，链栈较顺序堆栈方便。

3、代码

stack.h

#ifndef STACK_H
    #define STACK_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 10
    
    typedef int Status;
    typedef int DataType;
    typedef struct stack{ 
        DataType data;
        struct stack *next;
    }Stack;
    
    int GetStackLength(Stack *head);                    //获取栈的长度
    Status DestroyStack(Stack *head);                   //销毁栈
    Status InitiateStack(Stack **head);                 //初始化栈
    Status IfStackIsEmpty(Stack *head);                 //判断栈是否为空
    Status PushStackData(Stack *head, DataType elem);   //入栈
    Status PopStackData(Stack *head, DataType *elem);   //出栈
    Status GetStackElement(Stack *head, DataType *elem);//取栈顶元素
    
    #endif // MAINWINDOW_H

stack.c

#include "stack.h"
    
    //初始化栈
    Status InitiateStack(Stack **head)
    { 
        *head = (Stack *)malloc(sizeof(Stack));
        (*head)->next = NULL;
    
        return TRUE;
    }
    
    //获取栈的长度
    int GetStackLength(Stack *head)
    { 
        int length = 0;
        Stack *p = head;
    
        if (p == NULL)
            return length;
    
        while(p->next != NULL)
        { 
            length++;
            p = p->next;
        }
        return length;
    }
    
    //入栈
    Status PushStackData(Stack *head, DataType elem)
    { 
        Stack *p = head;
        Stack *q = NULL;
    
        q = (Stack *)malloc(sizeof(Stack));
        q->data = elem;
    
        q->next = p->next;
        p->next = q;
    
        return TRUE;
    }
    
    //出栈
    Status PopStackData(Stack *head, DataType *elem)
    { 
        Stack *p = head->next;
        if (p == NULL)
        { 
            printf("堆栈已空出错！");
            return FALSE;
        }
    
        head->next = p->next;
        *elem = p->data;
        free(p);
    
        return TRUE;
    }
    
    //判断栈是否为空
    Status IfStackIsEmpty(Stack *head)
    { 
        if (head->next == NULL)
            return FALSE;
        else
            return TRUE;
    }
    
    //取顶元素
    Status GetStackElement(Stack *head, DataType *elem)
    { 
        Stack *p = head->next;
        if (p == NULL)
        { 
            printf("堆栈为空! \n");
            return FALSE;
        }
        else
        { 
            *elem = p->data;
            return TRUE;
        }
    }
    
    //销毁栈
    Status DestroyStack(Stack *head)
    { 
        Stack *p = head;
        Stack *p1 = NULL;
    
        while(p != NULL)
        { 
            p1 = p;
            p = p->next;
            free(p1);
        }
        
        return TRUE;
    }

main.c

#include "stack.h"
    
    int main(int argc, char *argv[])
    { 
        Stack *myStack;
        int i, x;
        InitiateStack(&myStack);
    
        for(i = 0; i < 10; i++)
        { 
            PushStackData(myStack, i+1);
        }
    
        GetStackElement(myStack, &x);
        printf("当前栈顶数据元素为：%d\n", x);
    
        printf("依次出栈的数据元素序列如下：\n");
        while(IfStackIsEmpty(myStack))
        { 
            PopStackData(myStack, &x);
            printf("%d ", x);
        }
    
        return 0;
    }

[20190828124316683.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/47ee1d7279794346803d24f189f30243.png