一、栈是什么？
栈：是一种特殊的线性表。其只允许在固定的一端进行插入和删除操作。进行数据的插入和删除的一端称为栈顶，另外的一端称为栈底。栈中的数据元素遵循先进后出（后进先出）的原则
之前在学习C语言的时候，就i听说过的两种概念
1.压栈：栈的插入操作叫做进栈、压栈、入栈等，插入数据在栈顶
2.出栈：栈的删除操作叫做出栈。出数据也在栈顶
二、栈的实现
1.实现的方式
有两种
1.我们可以通过顺序表的形式实现，因为进行尾插尾删除，代价小，就算是更改或者删除栈中指定的元素，不过也是移动位置而已。
如图所示：
结构体代码如下：
#define MAX 100 #define CAp 4 ///初始化的时候capacity的容量 #define Make 2//每一次增加的newCapacity的容量 //静态 typedef struct Stacknode { int data[MAX];//数据域 int size;//表示元素个数 }Stack; //动态 typedef struct Stacknode2 { int* data;//数据域 int size;//表示元素个数 int capacity;//表示当前容量 }Stack1;
2.通过链表的形式进行实现栈表
结构体如下:
//创建基础结构 typedef struct node { int data; struct node* next; }ST; //栈实际上就是一个只能进行头插头删的单向链表 //创建栈的头尾结点 结构体 typedef struct stack { struct node* top;//栈顶元素地址 struct node* bottom;//栈底元素地址 int size;//栈的元素个数 };
2.实现栈的函数
以链表实现栈为例，在本文结尾处，一并放置用数组实现栈的完整代码
1.初始化栈
结构体如上，使用的是上文的结构体类型
代码如下：
//初始化栈 struct stack* create_stack() { struct stack* s = (struct stack*)malloc(sizeof(struct stack)); s->size = 0; s->bottom = s->top = NULL; return s; }
使用malloc函数，申请空间，将s的size大小置为0，bottom和top表示栈底栈顶都指向NULL
2.入栈
如图所示：
代码如下：
//创建新的结点 struct node* create_node(int data) { struct node* newnode = (struct node*)malloc(sizeof(struct node)); newnode->next = NULL; newnode->data = data; return newnode; } //入栈 //入栈首先要将准备入栈的元素封装成结点，和链表没有差别 void stackPush(struct stack* s, int x) { ST* newnode = create_node(x); newnode->next = s->top; s->top = newnode; s->size++; }
3.出栈
如图所示：
代码如下：
//出栈 void stackPop(struct stack* s, int* x) { //判断是否为空栈 如果是 空栈的话就 使得输出 Pop failed if (s->size == 0) { printf("Pop failed\n"); exit(-1); } //创建结点临时变量 赋值得到栈顶元素 ST* tmp = s->top; *x = tmp->data;//得到数值 s->top = tmp->next; s->size--; }
4.查看栈顶元素
代码如下：
//查看栈顶元素 void stackTop(struct stack* s, int* x) { if (s->size == 0) { printf("空栈~~\n"); exit(-1); } *x = s->top->next->data; }
5.打印栈和清空栈
代码如下：
//清空栈 void make_stack_empty(struct stack* s) { s->size = 0; s->bottom = s->top ; //将栈底等于栈顶就可以 然后将size为0 } void stackPrint(struct stack* s) { //打印栈表 ST* list = s->top; printf("top -> "); while (list!=NULL) { printf("%d -> ", list->data); list = list->next; } }
