数据结构与算法（6）链栈

本博客中使用单链表完成栈的构建

栈结构

typedef char Elemtype; typedef struct Node{ Elemtype data; struct Node *next; }StackNode, *LinkStack;

栈的各种运算实现与测试代码

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; typedef char Elemtype; typedef struct Node{ Elemtype data; struct Node *next; }StackNode, *LinkStack; /* 链栈的初始化 */ Status InitStack(LinkStack *s) { (*s) = (LinkStack)malloc(sizeof(StackNode)); (*s)->next = NULL; return OK; } /* 销毁链表 */ Status DestoryStack(LinkStack *s) { LinkStack p; while (*s){ p = (*s)->next; free(*s); (*s) = p; } return OK; } /* 栈空检测 */ Status EmptyStack(LinkStack s) { if (s->next == NULL) return TRUE; else return FALSE; } /* 压栈 */ Status Push(LinkStack *s, Elemtype e) { LinkStack new_node; new_node = (LinkStack)malloc(sizeof(StackNode)); if (!new_node) return ERROR; new_node->data = e; //新结点作为首元结点 new_node->next = (*s)->next; (*s)->next = new_node; return OK; } /* 弹栈 */ Status Pop(LinkStack *s, Elemtype *e) { LinkStack p; //注意在弹栈的时候要进行非空检测 if (EmptyStack(s)) return ERROR; p = (*s)->next; //指向首元结点 *e = p->data; (*s)->next = p->next; free(p); return OK; } /* 显示栈中数据内容 */ Status DispStack(LinkStack s) { LinkStack p; if (EmptyStack(s)) return ERROR; p = s->next; while (p){ printf("%c ", p->data); p = p->next; } printf("\n"); return OK; } /* 显示栈顶数据内容 */ Elemtype GetTop(LinkStack s) { if (EmptyStack(s)) return ERROR; else return s->next->data; } int main() { LinkStack s; Elemtype e; printf("初始化链栈\n"); InitStack(&s); //初始化s为头结点指针 printf("压栈\n"); Push(&s, 'a'); Push(&s, 'b'); Push(&s, 'c'); Push(&s, 'd'); Push(&s, 'e'); Push(&s, 'f'); Push(&s, 'g'); Push(&s, 'h'); printf("显示栈数据元素\n"); DispStack(s); Pop(&s, &e); printf("弹栈操作 %c\n", e); Pop(&s, &e); printf("弹栈操作 %c\n", e); Pop(&s, &e); printf("弹栈操作 %c\n", e); printf("显示栈数据元素\n"); DispStack(s); printf("栈顶内容 %c\n", GetTop(s)); printf("销毁链栈\n"); DestoryStack(&s); system("pause"); return 0; }