3.C_数据结构_栈

概述

什么是栈：

栈又称堆栈，是限定在一段进行插入和删除操作的线性表。具有后进先出(LIFO)的特点。

相关名词：

• 栈顶：允许操作的一端
• 栈底：不允许操作的一端
• 空栈：没有元素的栈

栈的作用：

• 可以检测逻辑图中是否有回路
• 可以将非线性问题线性化 

入栈与出栈示意图：

入栈：先指针+1，再入栈数据。出栈：先出栈数据，再指针+1

顺序栈

1、基本内容

顺序栈就是以数组形式进行存储的栈数据结构。

顺序栈结构体如下：

typedef int data_t;
typedef struct{data_t* pData;//数据int max_len;  //最大数据长度int top;      //栈顶位置
}sqstack,*stacklink;

顺序栈代码的文件构成：

• sqstack.h：数据结构的定义、运算函数接口
• sqstack.c：运算函数接口的实现
• test.c：使用数据结构实现的应用功能代码

顺序栈相关函数：

1、整个栈的创建和删除

• 创建：stacklink stack_create(int len);
• 删除：int stack_delete(stacklink pStack);

2、入栈、出栈

• 入栈：int stack_push(stacklink pStack,data_t data);
• 出栈：int stack_pop(stacklink pStack,data_t* data);

3、其他

• 栈清空：int stack_clean(stacklink pStack);
• 判断栈是否为空：int stack_isempty(stacklink pStack);

2、功能实现  

2.1 创建/删除栈

2.1.1 创建 

创建栈与创建线性表一样，都是先申请空间，之后赋值初始值

注意：在申请栈成功后，如果申请数据空间失败，需要释放申请的栈空间 

具体代码实现如下：

/** stack_create:创建一个栈* param len:栈的长度* @ret NULL--err  other--栈的地址* */
stacklink stack_create(int len){stacklink pStack = NULL;//1.申请空间//1.1 栈的空间pStack = (stacklink)malloc(sizeof(sqstack));if(pStack == NULL){printf("stack malloc err\n");return NULL;}//1.2 数据的空间pStack->pData = (data_t*)malloc(sizeof(data_t)*len);if(pStack->pData == NULL){printf("data malloc err\n");free(pStack);//此时pStack已经申请成功，应该释放空间return NULL;}//2.初始化memset(pStack->pData,0,sizeof(data_t)*len);pStack->max_len = len;pStack->top = -1;//-1代表空栈return  pStack;
}

2.1.2 删除

 删除栈就是释放所申请的空间。

注意：这里申请的空间是栈空间和数据空间，所以要释放两次

具体代码实现如下： 

/** stack_delete:栈的释放* param pStack:要进行释放的栈* @ret  -1--err 0--success* */
int stack_delete(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.释放空间free(pStack->pData);//释放数据空间free(pStack);       //释放栈空间pStack = NULL;return 0;
}

2.2 入栈与出栈

2.2.1 入栈

入栈就是先将指针+1，再将数据入栈。

具体代码实现如下：

/** stack_push:入栈* param pStack:所需入栈的栈的位置* param data:所需入栈的数据* @ret  -1--err  0--success* */
int stack_push(stacklink pStack,data_t data){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.判断栈空间是否已满if(pStack->top == (pStack->max_len-1)){printf("stack is full\n");return -1;}//3.入栈pStack->top++; 					    	//栈顶移动*(pStack->pData + pStack->top) = data;  //数据入栈return 0;
}

2.2.2 出栈

入栈就是先将数据出栈，再将指针-1。

具体代码实现如下：

/** stack_pop:出栈* param pStack:要进行出战的栈的位置* param data:出栈数据存储的位置* @ret  -1--err  0--success* */
int stack_pop(stacklink pStack,data_t* data){//1.判断栈空间是否为空if(pStack == NULL || data == NULL){printf("pStack is NULL\n");return -1;}//2.判断栈是否为空栈if(pStack->top == -1){printf("stack is empty\n");return -1;}//3.出栈*data = *(pStack->pData + pStack->top);//数据出栈pStack->top--; 						 //顶部移动return 0;
}

2.3 其他

2.3.1 栈清空

栈清空就是让栈的指针指向-1。

栈情况并不需要清空数组中的数据，因为之后写入新数据会自动覆盖旧数据

具体代码实现如下：

/** stack_clean:清空栈* param pStack:要进行清空的栈* @ret  -1--err  0--success* */
int stack_clean(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}//2.清空栈pStack->top = -1;//设为空栈不需要清空return 0;
}

2.3.2 判断栈是否为空

空栈就是指针指向-1。

具体代码实现如下：

/** stack_isempty:判断栈是否为空栈* param pStack:需要进行判断的栈* @ret  -1--err  1--空栈  0--非空栈* */
int stack_isempty(stacklink pStack){//1.判断栈空间是否为空if(pStack == NULL){printf("pStack is NULL\n");return -1;}if(pStack->top == -1){return 1;}else{return 0;}
}

链式栈

1、基本内容

链式栈就是以链表形式进行存储的栈数据结构。

链式栈结构体如下：

typedef int data_t;
typedef struct node{data_t data;  		//数据struct node* pNext;  //链表指针
}listnode,*stacklink;

链式栈代码的文件构成：

• linkstack.h：数据结构的定义、运算函数接口
• linkstack.c：运算函数接口的实现
• test.c：使用数据结构实现的应用功能代码

链式栈相关函数：

1、整个栈的创建和删除

• 栈结点创建：stacklink stacknode_create(void);
• 删除：int stack_delete(stacklink* pStack);

2、入栈、出栈

• 入栈：int stack_push(stacklink* pStack,data_t data);
• 出栈：int stack_pop(stacklink* pStack,data_t* data);

2、功能实现  

2.1 创建/删除栈

2.1.1 栈结点创建

使用链式栈时，不是一次性创建一整个栈，而是有一个数据入栈就创建一个栈的结点。

具体代码实现如下：

/** stacknode_create:创建栈结点* @ret  NULL--err  other--栈的地址* */
stacklink stacknode_create(void){stacklink pStack = NULL;//1.申请空间pStack = (stacklink)malloc(sizeof(listnode));if(pStack == NULL){printf("malloc err\n");return NULL;}//2.初始化memset(pStack,0,sizeof(listnode));pStack->pNext = NULL;return pStack;
}

2.1.1 删除整个栈

删除整个栈就是释放全部的申请空间。

具体代码实现如下：

/** stack_delete:释放整个栈* param pStack:要进行删除的栈* @ret  -1--err  0--success* */
int stack_delete(stacklink* pStack){stacklink point = *pStack;//1.栈空间判断if(*pStack == NULL){printf("pStack is NULL\n");return -1;}//2.释放空间while(point != NULL){point = point->pNext;free(*pStack);*pStack = point;}*pStack = NULL;return 0;
}

2.2 入栈与出栈

2.2.1 入栈

链式栈的入栈就是创建一个新结点，并把这个结点进行头插，这样出栈时每次访问头就可以实现后进先出的特点。

具体代码实现如下：

/** stack_push:入栈,头插法* param pStack:要进行插入的栈* param data:要入栈的数据* @ret  -1--err  0--success* */
int stack_push(stacklink* pStack,data_t data){stacklink pTmp = NULL;//1. 开辟新的结点pTmp = stacknode_create();if(pTmp == NULL){return -1;}pTmp->data = data;//2.开始入栈,//2.1 有栈空间,进行头插if(*pStack != NULL){pTmp->pNext = *pStack;}//2.2 没有栈空间,当前结点就是头*pStack = pTmp;//最终都要把头指向最新的结点return 0;
}

2.2.2 出栈

链式栈的出栈就访问链表的头，访问之后将头部结点进行删除。

具体代码实现如下：

/** stack_pop:出栈,取出链表头并释放空间* param pStack:要进行出栈的栈* param data:出栈的数据存放的位置* @ret  -1--err  0--success* */
int stack_pop(stacklink* pStack,data_t* data){stacklink pTmp = NULL;//1.栈空间判断if(*pStack == NULL){printf("pStack is NULL\n");return -1;}//2.开始出栈*data = (*pStack)->data;//出栈数据pTmp = (*pStack)->pNext;free(*pStack);//释放空间*pStack = pTmp;//改变链表头return 0;
}