数据结构--链式栈(C语言) 数据结构

栈是一种“先入后出”的重要数据结构，包含有栈顶和栈底，栈顶指向最后放入的元素，栈底指向最先放入的元素。不能随意访问，只能访问栈顶元素，其操作只能对栈顶元素使用。
重要的操作有入栈和出栈。入栈(push)：将元素压入栈中，同时将栈顶指向此元素。出栈(pop)：将栈顶元素弹出，同时将栈顶指向下一个元素。
【数据结构--链式栈(C语言)】
文章图片

（图片来自网络）
实现：

//stack.h

#ifndef STACK_H #define STACK_H#include #include typedef struct node { int data; struct node *next; }Node; void create_stack(Node **); int isempty(Node *); void push_stack(Node *,int); int pop_stack(Node *); int gettop(Node *); int getnum(Node *); void clear_stack(Node *); void destroy_stack(Node **); #endif

/************************************** *链式栈的实现较为简单，其基本思想是： *使用栈顶指针作为链表的头指针 *使用第一个入栈的元素作为栈底 *入栈操作是将新元素插入栈顶结点后（头插法） *出栈是将栈顶结点的下一个元素删除 **************************************/ //stack.c #include "stack.h"//初始化栈顶 //top:栈顶结点的地址（址传递） void create_stack(Node **top) { *top =(Node *)malloc(sizeof(Node)); (*top)->next = NULL; (*top)->data = https://www.it610.com/article/0; //整个栈中元素的数量 }//判断栈是否为空 //top:栈顶结点 //return:非空返回1,空或栈顶为初始化返回0 int isempty(Node *top) { if(!top) {//栈顶结点未初始化 printf("The stack is not init!\n"); return 0; } if(!top->data) {//栈中元素数量为0 printf("The stack is empty!\n"); return 0; } return 1; }//入栈操作，采用头插法，新元素插入到栈顶元素后 //top:栈顶结点 //value:新元素的值 void push_stack(Node *top,int value) { if(!top) {//判断栈顶是否初始化 printf("The stack is not init!\n"); return ; } Node *p = (Node *)malloc(sizeof(Node)); //头插法，插入新元素 p->next = top->next; top->next = p; p->data = https://www.it610.com/article/value; top->data++; }//出栈操作，删除头结点后元素，并返回值 //top:栈顶结点 //return:栈为空或栈顶未初始化返回-1，正常返回出栈值 int pop_stack(Node *top) { if(!isempty(top)) return -1; //准备删除栈顶后结点 Node *p = top->next; top->next = p->next; //释放出栈结点 value = https://www.it610.com/article/p->data; free(p); p = NULL; top->data--; //栈中元素数减1 return value; }//得到位于栈顶元素值 //top:栈顶结点 //return:栈顶元素值，异常返回-1 int gettop(Node *top) { if(!isempty(top)) return -1; return top->next->data; }//清空栈 //top:栈顶结点 void clear_stack(Node **top) { if(!*top) { printf("The stack is not init!\n"); return; } while(top->next)//循环出栈，直到只剩top结点 pop_stack(*top); top->next = NULL; }//得到栈中元素数量 //top:栈顶结点 //return:正常返回数量，异常返回-1 int getnum(Node *top) { if(!top) { printf("The stack is not init!\n"); return -1; } return top->data; }//销毁栈 //top:栈顶元素指针的值 void destroy_stack(Node **top) { if(!(*top)) { printf("The stack is not init!\n"); return ; } clear_stack(*top); //清空栈 free(*top); //释放头结点 *top = NULL; }

//测试 //stack_test.c #include "stack.h"int main() { Node *top = NULL; int selection; int value; while(1) { printf("\t\t\t1.CreateStack\n"); printf("\t\t\t2.Push\n"); printf("\t\t\t3.Pop\n"); printf("\t\t\t4.ClearStack\n"); printf("\t\t\t5.IsEmpty\n"); printf("\t\t\t6.GetNumOfStack\n"); printf("\t\t\t7.DestroyStack\n"); printf("input:"); scanf("%d",&selection); switch(selection) { case 1: create_stack(&top); break; case 2: printf("input data:"); scanf("%d",&value); push_stack(top,value); break; case 3: printf("data:%d\n",pop_stack(top)); break; case 4: clear_stack(top); break; case 5: isempty(top); break; case 6: printf("num:%d\n",getnum(top)); break; case 7: destroy_stack(&top); break; } } return 0; }