链栈的简单实现（C语言）

单链表复习
链接: 单链表的简单实现.

基本操作

入栈

// 入栈（结点头插）
bool Push(LiStack S, ElemType e){
    LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
    if(S->next == NULL){  // 判断栈空
        // 先创建第一个结点
        p->data = e;       
        p->next = NULL;     // 后继指向空
        S->next = p;
    }else{  // 后续结点都是在头结点和第一个结点之间插入
        p->next = S->next;  // p指向头指针原后继
        p->data = e;        // 存入数据
        S->next = p;        // 头指针后继指向p
    }
    return true;
} 

创建栈

// 创建栈
bool CreateStack(LiStack S){
    ElemType e;
    scanf("%d", &e);    // 读入数据   
    while(e != 9999){   // 输入9999停止  
        Push(S, e);         // 调用入栈函数进行入栈
        scanf("%d", &e);    // 读入数据
    }
    return true;
}

出栈

// 出栈
bool Pop(LiStack S, ElemType *e){
    if(S == NULL || S->next == NULL) return false;
    LinkNode *p = S->next;
    S->next = p->next;  // 指向下一个结点
    free(p);
    return true;
}

读取栈顶元素

// 读取栈顶元素
bool GetTop(LiStack S, ElemType *e){
    if(S == NULL) return false;
    *e = S->next->data; // 栈顶元素赋给e通过指针传回主函数
    return true;
}

输出栈

// 输出栈
void PrintStack(LiStack S){
    LinkNode *p;
    p = S->next;
    while(p != NULL){           // 遍历栈           
        printf("%d ", p->data); // 输出数据域
        p = p->next;
    }
    printf("\n");
}

定义

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LiStack;

初始化

// 初始化
bool InitStack(LiStack *S){
    (*S) = (LiStack)malloc(sizeof(LinkNode));   // 申请空间
    if(*S == NULL) return false;    // 分配失败
    (*S)->next = NULL;              // 初始指向空
    return true;
}

完整代码

// 链栈
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LiStack;

// 初始化
bool InitStack(LiStack *S){
    (*S) = (LiStack)malloc(sizeof(LinkNode));   // 申请空间
    if(*S == NULL) return false;    // 分配失败
    (*S)->next = NULL;              // 初始指向空
    return true;
}

// 入栈（结点头插）
bool Push(LiStack S, ElemType e){
    LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
    if(S->next == NULL){  // 判断栈空
        // 先创建第一个结点
        p->data = e;       
        p->next = NULL;     // 后继指向空
        S->next = p;
    }else{  // 后续结点都是在头结点和第一个结点之间插入
        p->next = S->next;  // p指向头指针原后继
        p->data = e;        // 存入数据
        S->next = p;        // 头指针后继指向p
    }
    return true;
} 

// 创建栈
bool CreateStack(LiStack S){
    ElemType e;
    scanf("%d", &e);    // 读入数据   
    while(e != 9999){   // 输入9999停止  
        Push(S, e);         // 调用入栈函数进行入栈
        scanf("%d", &e);    // 读入数据
    }
    return true;
}

// 出栈
bool Pop(LiStack S, ElemType *e){
    if(S == NULL || S->next == NULL) return false;
    LinkNode *p = S->next;
    S->next = p->next;  // 指向下一个结点
    free(p);
    return true;
}

// 读取栈顶元素
bool GetTop(LiStack S, ElemType *e){
    if(S == NULL) return false;
    *e = S->next->data; // 栈顶元素赋给e通过指针传回主函数
    return true;
}

// 输出栈
void PrintStack(LiStack S){
    LinkNode *p;
    p = S->next;
    while(p != NULL){           // 遍历栈           
        printf("%d ", p->data); // 输出数据域
        p = p->next;
    }
    printf("\n");
}


int main(){
    LiStack S;      // 声明
    InitStack(&S);  // 初始化 
    int status;     // 操作码
    ElemType e;     // 元素
    while(1){
        printf("Please enter a status code:\n1.CreateStack      2.Push        3.Pop\n");
        printf("4.GetTop           5.PrintStack  0.Exit\n");
        scanf("%d", &status);
        if(status == 0) break;
        switch (status){
        case 1:     // 创建栈
            printf("Please enter the elements one by one in order!\n");
            CreateStack(S); 
            PrintStack(S);
            break;
        case 2:     // 入栈
            printf("Please enter the element value you want to push\n");
            scanf("%d", &e);
            if(Push(S, e)){
                printf("Push successfully!\n");
            }else{
                printf("Failed to Push!\n");
            }
            PrintStack(S);
            break;
        case 3:     // 出栈
            if(Pop(S, &e)){
                printf("Element value %d Pop successfully\n", e);
            }else{
                printf("Failed to Pop!\n");
            }
            PrintStack(S);
            break;
        case 4:     // 读取栈顶元素
            if(GetTop(S, &e)){
                printf("The top elem is %d\n", e);
            }else{
                printf("The LiStack is empty!\n");
            }
            break;
        case 5:     // 输出表
            PrintStack(S);
            break;
        default:
            printf("Error!\n");
            break;
        }
    }
    return 0;
}

运行展示