栈的概念：数据先进后出，以高地址为栈顶。存储方式分为链式存储和顺序存储
顺序存储栈的容器：
顺序栈的头文件：
#pragma once #include<string.h> #include<stdlib.h> #define MAX 1024 //顺序栈 struct SeqStack{ void *data[MAX]; int size; }; #ifdef __cplusplus extern "C"{ #endif //初始化栈 void *Init_SeqStack(); //入栈 void Push_SeqStack(void *stack, void *data); //出栈 void Pop_SeqStack(void *stack); //获得大小 int Size_SeqStack(void *stack); //获得栈顶元素 void *Top_SeqStack(void *stack); //销毁栈 void Destroy_SeqStack(void *stack); #ifdef __cplusplus } #endif
顺序栈头文件的实现：
#include"SeqStack.h" //初始化栈 void *Init_SeqStack(){ struct SeqStack *stack = malloc(sizeof(struct SeqStack)); stack->size = 0; for (int i = 0; i < MAX; i ++){ stack->data[i] = 0; } return stack; } //入栈 void Push_SeqStack(void *stack, void *data){ if (0 == stack){ return; } if (0 == data){ return; } struct SeqStack *s = (struct SeqStack *)stack; s->data[s->size] = data; s->size++; } //出栈 void Pop_SeqStack(void *stack){ if (0 == stack){ return; } struct SeqStack *s = (struct SeqStack *)stack; s->size--; } //获得大小 int Size_SeqStack(void *stack){ if (0 == stack){ return -1; } struct SeqStack *s = (struct SeqStack *)stack; return s->size; } //获得栈顶元素 void *Top_SeqStack(void *stack){ if (0 == stack){ return NULL; } struct SeqStack *s = (struct SeqStack *)stack; return s->data[s->size - 1]; } //销毁栈 void Destroy_SeqStack(void *stack){ if (0 == stack){ return; } free(stack); }
测试文件：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<stdlib.h> #include"SeqStack.h" struct Person{ char name[64]; int age; }; void test(){ //测试数据 struct Person p1 = { "aaa", 10 }; struct Person p2 = { "bbb", 20 }; struct Person p3 = { "ccc", 30 }; struct Person p4 = { "ddd", 40 }; struct Person p5 = { "eee", 50 }; //初始化栈 void *stack = Init_SeqStack(); //数据入栈 Push_SeqStack(stack, &p1); Push_SeqStack(stack, &p2); Push_SeqStack(stack, &p3); Push_SeqStack(stack, &p4); Push_SeqStack(stack, &p5); //输出栈中所有元素 while (Size_SeqStack(stack) > 0){ //获得栈顶元素 struct Person * person = (struct Person *)Top_SeqStack(stack); //输出栈顶元素 printf("Name:%s Age:%d ",person->name,person->age); //弹出栈顶元素 Pop_SeqStack(stack); } //销毁栈 Destroy_SeqStack(stack); } int main(){ test(); system("pause"); return EXIT_SUCCESS; }
链式栈的实现：
链式栈的头文件：
#pragma once #include<stdlib.h> struct LinkNode{ struct LinkNode *next; }; //链式栈 struct LStack{ struct LinkNode header; int size; }; typedef void* LinkStack; #ifdef __cplusplus extern "C"{ #endif //初始化 LinkStack Init_LinkStack(); //入栈 void Push_LinkStack(LinkStack stack, void *data); //出栈 void Pop_LinkStack(LinkStack stack); //获得栈顶元素 void *Top_LinkStack(LinkStack stack); //大小 int Size_LinkStack(LinkStack stack); //销毁栈 void Destroy_LinkStack(LinkStack stack); #ifdef __cplusplus } #endif
头文件的实现：
#include"LinkStack.h" //初始化 LinkStack Init_LinkStack(){ struct LStack *stack = (struct LStack *)malloc(sizeof(struct LStack)); stack->header.next = NULL; stack->size = 0; return stack; } //入栈 void Push_LinkStack(LinkStack stack, void *data){ if (NULL == stack){ return; } if (data == NULL){ return; } struct LStack *s = (struct LStack *)stack; struct LinkNode *d = (struct LinkNode *)data; d->next = s->header.next; s->header.next = d; s->size++; } //出栈 void Pop_LinkStack(LinkStack stack){ if (NULL == stack){ return; } struct LStack *s = (struct LStack *)stack; if (s->size == 0){ return; } //缓存下待删除节点 struct LinkNode *pDel = s->header.next; s->header.next = pDel->next; s->size--; } //获得栈顶元素 void *Top_LinkStack(LinkStack stack){ if (NULL == stack){ return NULL; } struct LStack *s = (struct LStack *)stack; return s->header.next; } //大小 int Size_LinkStack(LinkStack stack){ if (NULL == stack){ return -1; } struct LStack *s = (struct LStack *)stack; return s->size; } //销毁栈 void Destroy_LinkStack(LinkStack stack){ if (NULL == stack){ return; } free(stack); stack = NULL; }
测试文件：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<stdlib.h> #include"LinkStack.h" struct Person{ struct LinkNode node; char name[64]; int age; }; void test(){ //创建数据 struct Person p1 = { NULL, "aaa", 10 }; struct Person p2 = { NULL, "bbb", 20 }; struct Person p3 = { NULL, "ccc", 30 }; struct Person p4 = { NULL, "ddd", 40 }; struct Person p5 = { NULL, "eee", 50 }; //初始化链式栈 LinkStack stack = Init_LinkStack(); //数据入栈 Push_LinkStack(stack, &p1); Push_LinkStack(stack, &p2); Push_LinkStack(stack, &p3); Push_LinkStack(stack, &p4); Push_LinkStack(stack, &p5); //输出栈容器中元素 while (Size_LinkStack(stack) > 0){ //获得栈顶元素 struct Person *person = (struct Person *)Top_LinkStack(stack); //打印 printf("Name:%s Age:%d ", person->name, person->age); //弹出栈顶元素 Pop_LinkStack(stack); printf("Size:%d ", Size_LinkStack(stack)); } printf("---------------- "); printf("Size:%d ", Size_LinkStack(stack)); //销毁栈 Destroy_LinkStack(stack); } int main(){ test(); system("pause"); return EXIT_SUCCESS; }
以链表作为底层容器，实现栈的操作：
容器头文件和头文件的实现：见数据结构链表的实现
栈的头文件：
#pragma once #include"LinkList.h" struct StackNode{ struct LinkNode node; }; typedef void *LinkStack; //初始化 LinkStack Init_LinkStack(); //入栈 void Push_LinkStack(LinkStack stack, void *data); //出栈 void Pop_LinkStack(LinkStack stack); //获得栈顶元素 void *Top_LinkStack(LinkStack stack); //大小 int Size_LinkStack(LinkStack stack); //销毁栈 void Destroy_LinkStack(LinkStack stack);
栈的头文件实现：
#include"LinkStack.h" //初始化 LinkStack Init_LinkStack(){ return Init_LinkList(); } //入栈 void Push_LinkStack(LinkStack stack, void *data){ Insert_LinkList(stack, 0, data); } //出栈 void Pop_LinkStack(LinkStack stack){ RemoveByPos_LinkList(stack, 0); } //获得栈顶元素 void *Top_LinkStack(LinkStack stack){ return Get_LinkList(stack, 0); } //大小 int Size_LinkStack(LinkStack stack){ return Size_LinkList(stack); } //销毁栈 void Destroy_LinkStack(LinkStack stack){ Destroy_LinkList(stack); }
测试代码：
define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<stdlib.h> #include"LinkStack.h" struct Person{ struct StackNode node; char name[64]; int age; }; void test(){ //创建测试数据 struct Person p1 = { NULL, "aaa", 10 }; struct Person p2 = { NULL, "bbb", 20 }; struct Person p3 = { NULL, "ccc", 30 }; struct Person p4 = { NULL, "ddd", 40 }; struct Person p5 = { NULL, "eee", 50 }; //初始化栈 LinkStack stack = Init_LinkStack(); //数据入栈 Push_LinkStack(stack , &p1); Push_LinkStack(stack, &p2); Push_LinkStack(stack, &p3); Push_LinkStack(stack, &p4); Push_LinkStack(stack, &p5); //输出栈中元素 while (Size_LinkStack(stack) > 0){ //获得栈顶元素 struct Person *person = (struct Person*)Top_LinkStack(stack); //输出元素 printf("Name:%s Age:%d ",person->name,person->age); //弹出栈顶元素 Pop_LinkStack(stack); } printf("Size%d ",Size_LinkStack(stack)); //销毁栈 Destroy_LinkStack(stack); } int main(){ test(); system("pause"); return EXIT_SUCCESS; }