首页 > 代码库 > 栈的存储结构和常见操作（c 语言实现）
栈的存储结构和常见操作（c 语言实现）
俗话说得好，线性表（尤其是链表）是一切数据结构和算法的基础，很多复杂甚至是高级的数据结构和算法，细节处，除去数学和计算机程序基础的知识，大量的都在应用线性表。
一、栈
其实本质还是线性表：限定仅在表尾进行插入或删除操作。 俗称：后进先出 (LIFO=last in first out结构)，也可说是先进后出（FILO）。
同样的，栈也分为顺序和链式两大类。其实和线性表大同小异，只不过限制在表尾进行操作的线性表的特殊表现形式。
1、顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，附设指针 base 指示栈底的位置。 同样，应该采用可以动态增长存储容量的结构。且注意，如果栈已经空了，再继续出栈操作，则发生元素下溢，如果栈满了，再继续入栈操作，则发生元素上溢。栈底指针 base 初始为空，说明栈不存在，栈顶指针 top 初始指向 base，则说明栈空，元素入栈，则 top++，元素出栈，则 top--，故，栈顶指针指示的位置其实是栈顶元素的下一位（不是栈顶元素的位置）。
1 #ifndef _____ADT__ 2 #define _____ADT__ 3 #include <stdbool.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 #define STACK_SIZE 50 7 #define STACK_INCREMENT 10 8 9 typedef struct{ 10 int stackSize;//栈容量 11 char *base;//栈底指针 12 char *top;//栈顶指针 13 } SqStack; 14 15 //初始化 16 //本质还是使用动态数组 17 void initStack(SqStack *s) 18 { 19 s->base = (char *)malloc(STACK_SIZE * sizeof(char)); 20 //分配成功 21 if (s->base != NULL) { 22 //空栈 23 s->top = s->base; 24 s->stackSize = STACK_SIZE; 25 } 26 else 27 { 28 puts("分配失败！"); 29 } 30 } 31 32 //判空 33 bool isEmpty(SqStack s) 34 { 35 return s.top == s.base ? true : false; 36 } 37 38 //判满 39 bool isFull(SqStack s) 40 { 41 return (s.top - s.base) >= STACK_SIZE ? true : false; 42 } 43 44 //求当前长度 45 int getLength(SqStack s) 46 { 47 int i = 0; 48 char *q = s.top; 49 50 while (q != s.base) { 51 q--; 52 i++; 53 } 54 55 return i; 56 } 57 58 //求栈顶元素 59 char getTop(SqStack s, char topElement) 60 { 61 if (isEmpty(s)) { 62 puts("栈空！"); 63 } 64 65 topElement = *(s.top - 1); 66 return topElement; 67 } 68 69 //入栈 70 void push(SqStack *s, char topElement) 71 { 72 char *q = NULL; 73 74 if (isFull(*s)) { 75 q = (char *)realloc(s->base, STACK_INCREMENT * sizeof(char)); 76 77 if (NULL == q) { 78 exit(0); 79 } 80 81 s->base = q; 82 s->stackSize = s->stackSize + STACK_INCREMENT; 83 } 84 //进栈 85 *s->top++ = topElement; 86 } 87 88 //出栈 89 void pop(SqStack *s, char *topElement) 90 { 91 if (isEmpty(*s)) { 92 exit(0); 93 } 94 95 s->top--; 96 *topElement = *s->top; 97 } 98 99 //遍历100 void traversal(SqStack s)101 {102 for (int i = 0; i < getLength(s); i++) {103 printf("栈中元素遍历：%c \n", s.base[i]);104 }105 }106 107 //清空108 void cleanStack(SqStack *s)109 {110 if (!isEmpty(*s)) {111 s->top = s->base;112 puts("栈已经清空！");113 }114 }115 116 //销毁117 void destroyStack(SqStack *s)118 {119 if (s->base != NULL) {120 free(s->base);121 s->base = NULL;122 s->top = NULL;123 s->stackSize = 0;124 puts("栈成功销毁！");125 }126 }127 128 #endif /* defined(_____ADT__) */
函数: void exit(int status); 所在头文件：stdlib.h
功 能: 关闭所有文件，终止正在执行的进程。
exit(1)表示异常退出.这个1是返回给操作系统的。
exit(x)（x不为0）都表示异常退出
exit(0)表示正常退出
exit()的参数会被传递给一些操作系统，包括UNIX,Linux,和MS DOS，以供其他程序使用。
exit()和return的区别：
按照ANSI C，在最初调用的main()中使用return和exit()的效果相同。 但要注意这里所说的是“最初调用”。如果main()在一个递归程序中，exit()仍然会终止程序；但return将控制权移交给递归的前一级，直到最初的那一级，此时return才会终止程序。
return和exit()的另一个区别在于，即使在除main()之外的函数中调用exit()，它也将终止程序。
_exit()与exit的区别：
头文件不同：
exit:#include<stdlib.h>
_exit:#include<unistd.h>
_exit()函数:直接使进程停止运行,清除其使用的内存空间,并销毁其在内核中的各种数据结构;
exit()函数则在这些基础上作了一些包装,在执行退出之前加了若干道工序。比如系统调用之前exit（）要检查文件的打开情况,把文件缓冲区中的内容写回文件。
1 #include "ADT.h" 2 3 int main(void) { 4 char temp = ‘0‘; 5 SqStack stack; 6 initStack(&stack); 7 8 printf("%d\n", getLength(stack)); 9 10 push(&stack, ‘b‘);11 push(&stack, ‘k‘);12 push(&stack, ‘y‘);13 14 printf("%d\n", getLength(stack));15 // 函数使用temp之前必须初始化16 temp = getTop(stack, temp);17 printf("%c\n", temp);18 19 traversal(stack);20 21 pop(&stack, &temp);22 printf("%d\n", getLength(stack));23 24 traversal(stack);25 26 cleanStack(&stack);27 28 destroyStack(&stack);29 30 return 0;31 }
测试结果：
0
3
y
栈中元素遍历：b
栈中元素遍历：k
栈中元素遍历：y
2
栈中元素遍历：b
栈中元素遍历：k
栈已经清空！
栈成功销毁！
Program ended with exit code: 0
顺序栈的小结：
1）、尽量使用指向结构的指针做函数参数，这样的操作比结构体变量作函数参数效率高，因为无需传递各个成员的值，只需传递一个结构的地址，且函数中的结构体成员并不占据新的内存单元，而与主调函数中的成员共享存储单元。这种方式还可通过修改形参所指成员影响实参所对应的成员值。
2）、栈清空，一定是栈顶指向栈底，不可颠倒，否则析构出错！
3）、再次注意二级指针和一级指针做函数参数的不同
4）、使用一个指针变量之前，必须初始化，不为指针分配内存，即指针没有指向一块合法的内存，那么指针无法使用，强行运行出错，这就是野指针的危害。类似其他类型变量都是如此，（这也是为什么建议声明变量的同时就立即初始化，哪怕是一个不相干的数值），就怕程序写的复杂的话，一时忘记变量是否初始化，导致出错。
5）、为什么顺序栈（包括顺序表）在初始化函数的传入参数里不用二级指针传参？
个人理解：
首先清楚函数传参的类型，值传递，引用（c++）传递，和指针传递，且函数修改的是实参的一份拷贝，并不是直接去修改实参。
问题是，在之前的链表里，定义结点结构（ Node）和指向结点的指针 p，有 struct Node *p；为了给结点分配内存，把这个指针（p本身占据一份内存空间，在栈区操作系统分配，但是 p 的指向是没有初始化的）p 传入初始化函数内，等于是传入的指向结点Node的一个指针 p 的拷贝 _p，而这个拷贝 _p 本身（假设指针变量p自己在内存的地址是0x1111）和拷贝 _p 存储的（指针 p指向的 内存区域）内容是不一样的，此时给 拷贝 _p 使用malloc函数分配内存，看似是修改了 _p ，实际上是把 _p 指向的内存区域改变了， p 本身在内存的地址（0x1111）没有被改变，故函数执行完毕，栈分配的内存被操作系统回收，然后参数返回给主调函数，那份拷贝 _p 还是以前传入的那份拷贝 _p， 高矮胖瘦那是纹丝未动，故不会对实参起到修改的作用，完全类似值传递，在值传递，就是把实参的本身的值传入函数，如果函数内部对其拷贝进行修改，其实传入的参数本身并没有被改变，虽然函数体内，他的值被修改了，但是一旦函数执行完，栈的内存被系统回收，修改就变得徒劳。
顺序栈里，一般是定义的整个表List结构，struct List p；变量p 就是一个实例化的栈结构，注意 p 已经分配了内存（主调函数 main ，操作系统在栈区给p分配），这和主调函数里链表的指针 p 不一样，链表的指针 p 在 main 函数，只是给指针本身分配了内存空间，但是对 其指向的表结点没有分配，需要在初始化函数初始化！故到了顺序栈里，当给函数传入&p（因为开始main 已经给栈结构分配了内存空间，而&p 是栈结构 p 在内存的地址0x1111，也就是栈本身的首地址，也是 base指向的栈的基址），同样是传入一份拷贝 _&p ，且不是给 _&p malloc 内存，而是给 _&p 指向的内容分配空间—— (&p)->base（表的基地址）分配内存，也就是说，这里堆 p 修改也是没用的，但是对 p 的指向修改，也就是 base，是有用的。而 base 本身就是一个指针，p 其实和 base 值相等，只不过变量的类型不一样，故不需要再传入二级指针。
6）、初始化那里，其实写的不好，主调函数里 s 分配了内存，如果没有对这个结构体初始化，就不代表 s 的成员 base 或者 top 等就是有指向的，更别说 NULL 了。很大程度是指向是垃圾值，不确定的内存区域，故这里的判断
if (s->base != NULL)
在这个前提下，是没有用处的语句。故还是声明变量的同时，最好是初始化，哪怕是0或者 NULL。
2、链栈
其实就是链表的特殊情形，一个链表，带头结点，栈顶在表头，插入和删除（出栈和入栈）都在表头进行，也就是头插法建表和头删除元素的算法。显然，链栈还是插入删除的效率较高，且能共享存储空间。
是栈顶在表头！栈顶指针指向表头结点。栈底是链表的尾部，base 就是尾指针。还有，理论上，链式结构没有满这一说，但是理论上是这样的，也要结合具体的内存，操作系统等环境因素。
1 #ifndef _____ADT__ 2 #define _____ADT__ 3 #include <stdbool.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 7 typedef struct Node{ 8 char data; 9 struct Node *next; //next 指针 10 } Node, *ListStack; 11 12 //初始化头结点，top 指针指向头结点 13 void initStack(ListStack *top) 14 { 15 //top就是头指针！也就是栈顶指针 16 *top = (ListStack)malloc(sizeof(Node)); 17 //就一个结点，也就是空栈，其实和链表一样，没啥意思 18 (*top)->next = NULL; 19 //内容初始化 20 (*top)->data = http://www.mamicode.com/‘0‘; 21 } 22 23 //判空 24 bool isEmpty(ListStack top) 25 { 26 //栈顶指针的next==NULL 就是空栈，没有满的判断，但是也要悠着点。小心内存受不了。 27 return top->next == NULL ? true : false; 28 } 29 30 //入栈 31 void push(ListStack top, char topElement) 32 { 33 ListStack q = NULL; 34 q = (ListStack)malloc(sizeof(Node)); 35 36 if (NULL == q) { 37 exit(0); 38 } 39 //类似头插法建表，进栈 40 q->next = top->next; 41 top->next = q; 42 //赋值 43 top->data =http://www.mamicode.com/ topElement; 44 //栈底永远是表尾指针 45 } 46 47 //出栈 48 void pop(ListStack top, char *topElement) 49 { 50 ListStack p = NULL; 51 52 if (isEmpty(top)) { 53 exit(0); 54 } 55 //栈顶元素出栈，记住，栈顶指针永远是指向栈顶元素的下一位，p 指向栈顶元素 56 p = top->next; 57 *topElement = p->data; 58 //删除这个元素 59 top->next = p->next; 60 free(p); 61 } 62 63 //求当前长度 64 int getLength(ListStack top) 65 { 66 int i = 0; 67 ListStack q = top->next; 68 69 while (q != NULL) { 70 i++; 71 q = q->next; 72 } 73 74 return i; 75 } 76 77 //求栈顶元素 78 char getTop(ListStack top, char topElement) 79 { 80 if (isEmpty(top)) { 81 puts("栈空！"); 82 } 83 84 topElement = top->next->data; 85 return topElement; 86 } 87 88 //遍历 89 void traversal(ListStack top) 90 { 91 ListStack p = top->next; 92 93 for (int i = 0; i < getLength(top); i++) { 94 printf("栈中元素遍历：%c \n", p->data); 95 p = p->next; 96 } 97 } 98 99 //销毁100 void destroyLinkStack(ListStack *top)101 {102 ListStack p = *top;103 ListStack pn = (*top)->next;104 105 while (pn != NULL)106 {107 free(p);108 p = pn;109 pn = pn->next;110 }111 //销毁最后一个112 free(p);113 p = NULL;114 puts("栈成功销毁！");115 }116 117 #endif /* defined(_____ADT__) */
main 函数
1 #include "ADT.h" 2 3 int main(void) { 4 ListStack stack = NULL; 5 initStack(&stack); 6 7 printf("栈长度 = %d\n", getLength(stack)); 8 9 push(stack, ‘a‘);10 push(stack, ‘b‘);11 push(stack, ‘c‘);12 push(stack, ‘d‘);13 14 printf("栈长度 = %d\n", getLength(stack));15 16 traversal(stack);17 18 char temp = ‘0‘;19 printf("栈顶元素 = %c\n", getTop(stack, temp));20 pop(stack, &temp);21 22 printf("栈长度 = %d\n",getLength(stack));23 24 traversal(stack);25 26 destroyLinkStack(&stack);27 28 return 0;29 }
其实链栈和链表是一样的，没什么新鲜的东西。可见，线性表，尤其是链表，是数据结构和算法里的重中之重，后续很多复杂高级的数据结构和算法，都会无数次的用到链表的相关知识和概念。
栈的存储结构和常见操作（c 语言实现）