数据结构之栈定义及基本操作实现
终于有可以有时间写点数据结构的学习总结了，前段时间⼀直在紧张的忙⼀些项⽬，都没有空出时间来学习数据结构，现在终于可以稍微喘⼝⽓了，还是数据结构有意思，这两天看了点栈的东西，写下来总结⼀下，有错误的地⽅希望看到的朋友指出来，感激不尽。
根据学习，栈就是⼀种线性数据结构，栈的运算只能在表的⼀段进⾏，所以这种数据结构具有“后进先出”的特点。
接下来是栈的c语⾔实现。其中栈由⼀个top节点和bottom节点组成，这两个节点分别指向栈的顶部和底部。其中栈的组成结点是由结构体实现，结构体由数据库和指向下⼀个结点的指针域构成，下⾯是结点的c语⾔实现：
1/*
2定义实现栈的结点
3*/
4 typedef struct Node{
5int data;
6struct Node * pNext;
7 }NODE,* PNODE;
有了实现栈的结点，那么接下来就是该如何实现栈（具体的解释看代码）：
1/*
2定义栈的结构，此处采⽤链表实现静态栈，所以仅仅需要给出栈的头部指针和底部指针即可
3*/
4 typedef struct Strack{
5 PNODE pTop;
6 PNODE pBottom;
7 }STRACK,* PSTRACK;
栈的基本操作：栈的初始化，压栈、栈的遍历、出栈等操作
1/*
2对栈初始化的函数
3对栈初始化仅仅是令栈中的top和bottom指针指向⼀个确定的地址，并且此地址指向的是栈的头结点（头结点的引⼊可以
4⼤⼤⽅便对栈的操作）。
5*/
6void init_strack(PSTRACK pS){
7 pS->pTop=(PNODE)malloc(sizeof(NODE)); //定义⼀个新结点，这个结点就是栈的头结点，并且让pTop指向这个结点
8if(pS->pTop==NULL){
9 printf("内存分配失败");
10 exit(-1);
11 }
女人服装
12el{
13 pS->pBottom=pS->pTop; //令bottom和top都指向头结点，则初始化栈完成，栈中没有任何有效结点
14 pS->pTop->pNext=NULL;
15 }
16
17 }
18
19/*
20压栈函数
21因为栈具有“先进后出、后进先出”的特性，所以，在将元素压⼊栈时，也只能将栈压⼊栈的顶部
22由此，压栈函数就是令栈的top指针指向新结点，新结点的指针域指向未压⼊栈时的最顶部的元素。
23*/
24int push(PSTRACK pS,int val){
25 PNODE pNew=(PNODE)malloc(sizeof(NODE)); //定义⼀个新结点
26if(pNew->pNext==NULL){
27 printf("内存分配失败");
28 exit(-1);
29 }
30 pNew->data= val;
31 pNew->pNext=pS->pTop; //指针赋值的顺序不可以乱，为保证top所指向的地址不丢失，所以⾸先让新结点的指针域指向pS->pTop所指向的结点
32 pS->pTop=pNew; //令top指针指向新的结点
33return0; //0表⽰当前push成功
34 }
35
36/*
37栈的遍历函数
38因为只是遍历输出，所以不能破坏栈原有的结构，所以我们只有定义⼀个新的结点p，让其指向栈顶元素，
39然后遍历下移⼀个输出其指向的元素的值，循环条件就是p=ps->pBottom
40*/
41void traver(PSTRACK ps){
42 PNODE p=ps->pTop; //让新定义的结构体指针指向栈顶元素
43while(p!=ps->pBottom){
44 printf("%d ", p->data);
45 p=p->pNext; //让当前指针指向当前节点的下⼀个结点
46 }
离婚女人电视剧
47 printf("\n");
48return;
49 }
50
51
52/*
53判断当前栈是否为空的函数
54若为空，返回true
55否则，返回fal
56*/
57bool isEmpty(PSTRACK ps){
58if(ps->pTop==ps->pBottom){
59return true;
60 }
61el{
62return fal;
63 }
64 }
65
66/*
67弹栈函数：弹栈简单的说就是将第⼀个数值弹出，然后将ps->pTop指向原第⼀个结点的下⼀个结点（即弹栈后的第⼀个结点），
68然后在将被弹出的元素在内存中释放掉。
69*/
70bool pop(PSTRACK ps,int *pVal){
71if(isEmpty(ps)){ //判断当前栈是否为空，若为空，则返回fal
72return fal;
73 }
74el{
75 PNODE p=ps->pTop; //定义⼀个结点，这个结点在每次弹栈时都是指向栈顶，这样可以保证不会造成被弹出元素的丢失
76 ps->pTop=p->pNext; //让top结点指向栈顶元素
77 *pVal=p->data;
78free(p); //将被弹出元素释放
白贵宾79 p=NULL;
80return true;
81 }
82 }
上述就实现了对栈的基本操作，当然具体的应⽤还要看具体的算法要求。
上述是在⼤学时学习的，下⾯的是⼯作两年后再次学习时的理解，可能会有不同的见解，都写出来吧。
1、栈的定义：⼀种可以实现“先进后出”的数据存储结构，数据的插⼊和删除只能在数据的⼀端进⾏。
内存分为静态内存和动态内存。
静态内存在栈中分配；动态内存在堆中分配。
栈：由操作系统⾃动分配释放，存放函数的参数值，局部变量的值等。
堆：⼀般由程序猿分配释放，若程序猿不释放，程序结束时由OS回收（类似于c语⾔中的malloc函数分配的空间）。
2、栈的分类：
（1）静态栈：以数组作为数据的存储。
（2）动态栈：以链表作为数据的存储⽅式。
3、栈的相关操作（该处采⽤链表的动态栈）：
⼀点说明：
因为⽤链表实现栈，其实其本质就是⼀个链表，只不过对该链表的插⼊（push）和删除（pop）操作都在该链表的⼀端进⾏（该段被称为栈顶，且⼈为限制就只在该栈顶进⾏操作），所以该链表就会具有了“先进后出”的特性，则被称为栈结构。
所以，严格来说，栈仅仅需要⼀个栈顶，该栈顶指向该链表的被称为栈顶端的节点（所以，该栈顶也是⼀个该Node类型的指针）。
（1）栈中每个节点的结构：
（2）栈的结构：阎维文的歌
因为通过栈顶可以找到该栈的所有元素，所以，该栈对应的链表应该是⼀个⾃上⽽下指向的链表。
该栈仅需要⼀个stop指针，指向栈顶元素。
（3）栈的初始化操作：
（4）栈的push操作：
（5）栈的pop操作：
（6）栈是否为空及栈的遍历操作：
其实在栈中可以增加⼀个PNODE类型的指针sbuttom，让该指针⽤于指向栈低节点，在判断⾮空时，只要判断sc->stop == sc->sbuttom时，就表⽰top和buttom重合了，指向了最底部的节点。其实，该b
uttom节点可以通过最后⼀个节点的next指针域是否为NULL来判断（next指针域为NULL时，就表⽰该节点没有下⼀个节点了，是栈低节点）。
代码：
1 #include <stdio.h>
2 #include <sys/malloc.h>
3 #include <stdlib.h>
4
5/*
6栈结构及其操作:
7当前采⽤链表进⾏栈中数据的存储。
8*/
9
10
11/*新闻日记
12定义栈中每⼀个节点的结构
13*/
14 typedef struct Node{
15int data; //数据域
16struct Node * pnext; //指针域，指向栈中下⼀个节点
17 }NODE, * PNODE; //定义两个别名，⽅便操作
18
19/*
20定义栈的结构：
21因为⽤链表实现栈，其实其本质也是⼀个链表，只不过该链表的插⼊（push）和删除（pop）操作只能在链表的⼀端（该端被称作栈顶）进⾏操作，所以该链表具有“先进后出”的特性，被称作栈（个⼈理解）。 22所以，严格来说，栈仅仅需要⼀个指向栈顶（链表的⼀端）struct Node *类型的指针就可以知道该栈中的所有数据。
再被狐狸骗一次23*/
24 typedef struct Stack{
25struct Node * stop; //栈的栈顶（指向栈中最顶部的那个元素）
26 } STACK;
27
28//栈的初始化操作
29struct Stack init_stack();
30
31//push操作
32void stack_push(STACK *sc, int data);
33
34//pop操作
35int pop(STACK *sc);
36
37//遍历操作
38void trvel_stack(STACK *sc);
39
40//判断是否为空操作
41int is_empty(STACK *sc);
42
43int main(int argc, char const *argv[])
44 {
45 STACK sc;
46 sc = init_stack();
47
48//push⼏个数据
49 stack_push(&sc, 1);
50 stack_push(&sc, 3);
51 stack_push(&sc, 7);
52 stack_push(&sc, 2);
53 stack_push(&sc, 10);
54
宣传推广方案55//遍历
56 trvel_stack(&sc);
57
58//pop⼀个数据出来
59 pop(&sc);
60
61 trvel_stack(&sc);
62
63return0;
64 }
65
66/*
67栈的初始化操作
68*/
69struct Stack init_stack(){
70//先定义⼀个栈
71 STACK sc;
72
73//初始化栈中的第⼀个节点(栈低节点)，该节点并没有什么实际意义，不存放数据
74 PNODE pbottom = (PNODE)malloc(sizeof(NODE));
75if (pbottom == NULL) {
76 printf("内存分配失败\n");
77 exit(1);
78 }
79 pbottom->pnext = NULL;
80
81//将栈顶指向该元素
82 sc.stop = pbottom;
83
84return sc;
85 }
86
87/*
88栈的push操作
89*/
90void stack_push(STACK *sc, int data){
91 printf("调⽤了！\n");
92
93//新创建⼀个节点
94 PNODE pnew = (PNODE)malloc(sizeof(NODE));
95 printf("%p\n", pnew);
96if (pnew == NULL) {
97 printf("内存分配失败\n");
98 exit(1);
99 }
100 pnew->data = data;
101
102//将新节点指向原top节点，将栈的top指向该新节点
103 pnew->pnext = sc->stop;
104 sc->stop = pnew;
105 }
106
107/*
寥若晨星是什么意思
108栈的pop操作
109*/
110int pop(STACK *sc){
111int res;
112//判断栈是否为空
113if (is_empty(sc) == 1){
114 printf("栈为空，不可pop\n");
115 exit(1);
116 } el {
117 PNODE ptmp = sc->stop; //先将需要被pop出的节点存储起来
118 sc->stop = sc->stop->pnext; //将栈的top指向下⼀个节点
119 res = ptmp->data;
120free(ptmp); //将地址释放
121return res;
122 }
123 }
124
125/*
126判断栈是否为空的操作
127*/
128int is_empty(STACK *sc){
129 PNODE p = sc->stop;
130if (p == NULL || p->pnext == NULL) {
131return1; //true表⽰为空
132 } el {
133return0; //fal表⽰⾮空
