数据结构之数据栈C源代码
玩转算法与数据结构之数据栈
—HIT2000鲁天伟
前面我们讲了单链表，双向链表，循环链表。这几种链表形式向我们展示了一种数据线性存储方式。现实世界中，人们利用建筑材料建造房子用来住人，住人房子有大有小，在计算机世界人们利用计算机语言也是建房子给数据住。每个房子都有地址，但是房子中住的人是可以变的。计算机一样，定义变量，计算机根据变量数据类型的大小分配一块连续内存，用来存放相应类型的数据。并把这块内存的首地址作为这个数据变量的寻址地址。链表这种存储方式只要知道表头结点的地址，就能按顺序知道其它结点的地址和地址中存储的数据。如果一直增加结点可以一直连下去，直到把计算机中能用的内存地址用完。如果数据链太长，是否对我们是有用的，是否好管理，好操作呢？如果这条链无限长，相当于把整个内存作为一个容器来存放这些数据。也就是可以用无限制长度的链表作无限数据存储，结点可以一直增加。这个是数组这种数据类型不具备的功能，数组初始化后就定长了，到达指定长度，无法继续拓展。而且数组插入，删除数据还要调整后面数据在数组中的位置，这点上无限制长度链表要比数组灵活方便的多。数据链太长了是否不太好管理呢，因此我们要根据需要，使用不同大小形状的容器来灵活的管理。其中一种是数据栈，用来存放管理数据。类似货栈，用来存货的，粮栈用来存粮的。但是无论货栈还是粮栈都是有大小限制的。我们定义的数据栈也限制它的大小，一个数据栈装满了数据，没装完可以再建一个新的数据栈来装数据。装数据的时候，模拟粮仓装粮食一样，最先装进去的粮食在最下面，在取用时最后装进去的粮食，由于在上面所以会先取到。也就是让数据先进后出，类似给弹夹装子弹，一颗一颗压下去。压到最上面一颗满了，就不能装了。打子弹的时候从先用弹夹最上面的子弹，弹夹子弹打空了，也就不能再打出子弹了。也就是在进行装填数据时还要一直记录数据的个数，看是否为空，是否超过最大值。
如此，我们给出栈的定义：
栈有高度，宽度，数据进出的顺序是先进后出，栈满不可再增加数据，栈空不可再弹出数据。每次录入一条记录，每次弹出只有一条记录。
具体解释：栈是一个有限大小的数据容器，高度的定义是可输入数据记录的条数。宽度的定义是每层一条记录。这一条记录可以包含1个或多个数据元素，如下三种情况，每个花括号内是一条记录：
a)比如{1}，{2}，{3} ，每条记录只有一个种数据类型，例子中是整型。
b)比如{1,2,3}，{4,5,6}，{7,8,9}，每条记录含有3个同种数据类型的数据，例子中是整型。
c)比如{1,‘a’,”blue”},{2,’b’,’yellow’},{3,’c’,”red”} 每条记录含有不同的数据类型的三个元素，例
子中，每条记录包含1个整型数据，1个字符型数据，1个字符串型数据。
先进后出的录入顺序：可以把数据记录按顺序一条一条的录入，录数据时候从前向后录入（一层一层录入），取数据的时候从后向前按顺序一条一条的取。其它教材上都是把栈讲成是立着的数组图，我这边把栈放平，左边是栈底，右边是栈顶，这样让大家更好理解，和我们计算机输入和书写习惯保持一致。栈底数据是录入的第一条记录，然后从左向右录入，栈顶数据是当前存储的最右边的数据。取出栈顶数据，也就是从数据栈最右边取出记录。被取出记录的原相邻的左侧记录成为新的栈顶数据。
栈满：当栈录入的记录条数超过最大值时，判定栈容量已满，不能再增加数据。
栈空：当栈中已经没有数据记录时，判定栈已空，不能再取出数据。
如下图：
将a,b,c,d四个数据放入（入栈），大小为4的栈中，从左向右逐个放入。到第四个栈满。不能再放入，取数据（出栈）的时候，图从右向左看。也就是要在每次放入或取出数据时，要记录栈顶的位置，数据入栈前要判断是否栈满，栈满不能入栈。出栈前判断栈是否为空，空则不能输出数据。
对于一个有限长度的数据集合，我们如何实现它的存储呢。可以用数组，也可以用链表。
a)如果用数组有如下几种情况：
1、如果每条记录中只有一个种类型的数据，且只有一个数据，我们可以采用简单的数
组来存放。比如{2},{3},{4}, 可以用int stack[Maxsize], Maxsize是栈的最大记录条数。
2、如果每条记录中有多个数据，且数据类型相同，比如整型{1,2,3}这是一条记录，我
们可以用三维数数组来作，比如int stack[3][Maxsize] , 或是int stack[Maxsize][3]来
作为存储容器。
3、如果每条记录中有多个数据，且数据类型不相同，比如{1,‘a’,2.5}这是一条记录我们
可以用结构体数组来作为存储容器。例如：
Struct record{ /*定义记录的结构体*/
Int a;
Char b;
Float c
};
Struct record stack[Maxsize];
用这种结构体数组来存储记录数据。
4、针对第3种情况每条记录中含有多个数据，也可以用三个基础数据类型数组来实存
储。例如：
Int stack1[Maxsize];
Char stack2[Maxsize];
Float stack3[Maxsize];
以上是用数组作为存储容器的4种情况，采用不同的存储方式，配合不同的入栈和出栈方法（存储容器不一样，当然要配合不同的装填和取用的方法），但方法都要遵循先进后出的原则。入栈前栈不能满，出栈时栈不能空的原则。
因此可以定义方法如下：/*以最简单的一维数组为例。*/
#define MaxSize 25 /*定义栈的容量最大录入记录数*/
Int Data[MaxSize]; /*栈数组*/
Int top; /*栈顶标志*/
Int push(int * Data,int indata,int *topaddr); /*在栈中压入数据*/
Int pop(int * Data,int * outdata,int * topaddr); /*在栈中弹出数据*/
Int isEmpty(int top); /*判断栈是否为空*/
Int isFull(int top); /*判断栈是否为满*/
因为栈数组和栈顶标志是配合使用的，是一对一的关系，也可以封装到一起，如下面的写法：
#define MaxSize 25 /*定义栈的容量最大录入记录数*/
struct stack{ /*把静态变量封装在栈的结构体里*/
Int data[MaxSize]; /*栈数组*/
Int top; /*栈顶标志*/
}；
typedef struct stack StackArray;
typedef StackArray * Stack;
int push(Stack stackaddress,int indata); /*在栈中压入数据*/
int pop(Stack stackaddress,int * outdataaddr); /*从栈中弹出数据*/
Int isEmpty(Stack stackaddress); /*判断栈是否为空*/
Int isFull(Stack stackaddress); /*判断栈是否为满*/
b)如果用链表来作存储介质。
#define MaxSize 25 /*定义栈的容量最大录入记录数*/
struct list{ /*定义链表结点*/
int data; /*定义结点数据变量*/
int * next; /*定义指向下个结点的指针变量*/
};
Typedef struct list listNode;
Typedef listNode * stack;
stack push(stack Stack,int indata,int * topaddr);
stack pop(stack Stack,int * outdata,int * topaddr);
int isEmpty(int top);
int isFull(int top);
链表的结点个数根据入栈和出栈的操作在0到MaxSize值之间动态的增加，减少。数组是一次按最大值把内存申请出来。
以上所有方法中的判断栈满isFull和判断栈空isEmpty的方法根据编码习慢，可以选择实现也可以不实现。因为判断的语句比较简单，也可以在push和pop方法中直接判断栈的空满情况。写出来就是让大家关注到栈的容量问题。
下面分别用数组和链表来实现数据栈。
1）如下是可执行的栈的数组实现源代码。
/*====================begin===========================*/
#include
#define MaxSize 8
/*======将数据压入数组栈中======*/
void push(int* stack,int data,int* topaddr){
if(*topaddr * topaddr=*topaddr+1; stack[*topaddr]=data; } else printf("The stack is full\n"); } /*======从数组栈中取数据======*/ void pop(int* stack,int* temp,int*topaddr){ if(*topaddr==-1) printf("the stack is empty\n"); else{ * temp = stack[*topaddr]; *topaddr=*topaddr-1; } } /*======打印数组栈中数据=====*/ void printstack(int* stack,int top){ int i; if(top==-1){ printf("The stack is empty\n"); } else{ for(i=0;i<=top;i++){ printf("%d ",stack[i]); } printf("\n"); } } void main(){ int a; int b; int c; int top=-1;/*数组栈的栈顶标识*/ int stack[MaxSize];/*数组0号位置为栈底,栈可录入MaxSize条记录*/ do{ printf("please input your choice\n1.push\n2.pop\n3.print\n4.quit\n"); scanf("%d",&a); switch(a){ case1:printstack(stack,top); printf("input the data you want to push\n"); scanf("%d",&b); push(stack,b,&top); printstack(stack,top); break; case2:printstack(stack,top); pop(stack,&c,&top); printf("The pop data is %d\n",c); printstack(stack,top); break; case3:printstack(stack,top); break; case4:break; default:printf("please input choice from 1 to 4\n");break; } }while(a!=4); getch(); } /*=====================end============================*/ 2）栈的链表实现如下： /*====================begin===========================*/ #include #include #define MaxSize 8 struct list{/*定义链表结点*/ int data;/*定义结点数据变量*/ struct list * next;/*定义结点指向下个结点的指针变量*/ }; typedef struct list Node;/*链表结点别名*/ typedef Node * link;/*链表结点指针别名*/ /*======将数据压入数组栈中======*/ link push(link stack,int data,int* topaddr){ link newNode; if(* topaddr==MaxSize){ printf("Stack if full\n"); } else{ newNode=(link)malloc(sizeof(Node)); newNode->data=data; newNode->next=NULL; if(stack==NULL){ stack=newNode; } else{ newNode->next=stack; stack=newNode; } *topaddr=*topaddr+1; } return stack; } /*======从数组栈中取数据======*/ link pop(link stack,int* temp,int* topaddr){ link pointer; if(stack==NULL){ printf("Stack is empty\n"); } else{ * temp=stack->data; pointer=stack; stack=stack->next; free(pointer); *topaddr=*topaddr-1; } return stack; } /*======打印数组栈中数据=====*/ void printList(link stack){ link pointer; if(stack==NULL) printf("The stack is empty\n"); else{ pointer=stack; while(pointer!=NULL){ printf("%d ",pointer->data); pointer=pointer->next; } printf("\n"); } } /*======递归反转打印数组栈=====*/ void printcoverse(link stack){ if(stack!=NULL){ printcoverse(stack->next); printf("%d ",stack->data); } } void main(){ int a,b,c; link stack=NULL;/*初始化栈顶指针为0,当前是空栈*/ int top=0;/*结点计数器初始化*/ do{ printf("choice:\n1.push\n2.pop\n3.printnomal\n4.printconvers\n5.quit\ n"); scanf("%d",&a); switch(a){ case1: printList(stack); printf("input data you want to push\n"); scanf("%d",&b); stack=push(stack,b,&top); printList(stack); break; case2:printList(stack); stack=pop(stack,&c,&top); printList(stack); break; case3:printList(stack);break; case4:printcoverse(stack);printf("\n");break; case5:break; default:printf("Please input your choice from 1 to 5\n"); break; } }while(a!=5); getch(); } /*=====================end============================*/ 我自己使用的环境是运用notepad++编辑，在notepad++里调用Dev-CPP里的编译和运行。具体网上有教程很简单，两个软件安装完成后，简单在计算机里配一下环境变量即可。使用graphviz软件进行数据结构图形的绘画，这个软件非常好，推荐大家使用。 当然程序在VC6.0，Tubo C，还有Win-TC中也都能正常运行。用C语言的编译运行工具都可以用上面的源代码。 源代码文件如下： stackArray.c stackList.c 2020-9-15 HIT2000 软件学院鲁天伟