4、数据结构与算法解析(C语言版)--栈
栈的数据存储遵循“后进先出的规则”，这在计算机里面是非常有用的，比如word等编辑软件的"撤销"功能，就是使用栈进行实现的。
1、创建项目
main.h
#ifndef _MAIN_H
#define _MAIN_H
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 // 无意义
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef int SElemType;
#endif main.c
#include "Stack.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
Stack_test();
return 0;
}Stack.h
#ifndef _STACK_H
#define _STACK_H
#include "main.h"
void Stack_test(void);
#endifStack.c
#include "Stack.h"
void Stack_test(void)
{
}2、创建栈结构
#ifndef _STACK_H
#define _STACK_H
#include "main.h"
#define STACK_INT_SIZE 10 // 栈初始容量为10
#define STACK_INCREMENT 2 // 空间不够每次增加两个
// 栈结构类型
typedef struct
{
SElemType *base; // 栈底指针，栈构造和销毁后为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前栈的容量，分配的空间数
}SqStack;
void Stack_test(void);
#endif3、初始化栈
// 初始化栈
// - 在函数内部修改外部栈空间的base、top、stacksize因此需要传入外部栈空间地址
void InitStack(SqStack *s)
{
s->base = (SElemType *)malloc(STACK_INT_SIZE *sizeof(SElemType));
if(!s->base)
{
printf("申请栈空间失败\r\n");
exit(OVERFLOW);
}
s->top = s->base;
s->stacksize = 0;
} 测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
}4、向栈中添加元素
// 向栈中添加元素
// - 在函数内部修改外部栈空间的base、top、stacksize因此需要传入外部栈空间地址
void Push(SqStack *s,SElemType e)
{
if(s->top - s->base == s->stacksize )
{
// 栈满
SElemType *temp;
temp = (SElemType *)realloc(s->base,(s->stacksize + STACK_INCREMENT)*sizeof(SElemType));
if(!temp)
{
printf("申请栈空间失败\r\n");
exit(OVERFLOW);
}
s->base = temp; // 申请成功，修改s->base指向
s->top = s->base + s->stacksize; // 更改新的top指针指向
s->stacksize += STACK_INCREMENT;
}
// 将元素推入栈中
*(s->top) = e;
// 栈顶指针移动
(s->top)++;
}5、访问栈数据
// 访问栈数据
void StackTraverse(SqStack s)
{
SElemType *p = s.base;
while(p < s.top)
{
printf("%d ",*p);
p++;
}
printf("\n");
} 测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
StackTraverse(st);
}
6、获取栈顶元素不移除
Status GetTop(SqStack s,SElemType *e)
{
if(s.top > s.base)
{
// 栈不为空
*e = *(s.top-1);
return OK;
}
return ERROR;
}测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
SElemType res;
GetTop(st,&res);
printf("栈顶元素：%d\n",res);
}7、移除栈顶元素
// 移除栈顶元素
// 接收栈顶数据到外部空间中
Status Pop(SqStack *sp,SElemType *e)
{
if(sp->top == sp->base)
{
return ERROR;
}
--(sp->top);
*e = *(sp->top);
return OK;
}测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
SElemType res;
Pop(st,&res);
printf("移除的栈顶元素：%d\n",res);
}8、获取栈的数据长度
// 获取栈的数据长度
int StackLength(SqStack s)
{
return s.top - s.base;
}测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
int res = StackLength(st);
printf("当前栈的长度是：%d\n",res);
}9、空栈判断
// 空栈判断
Status StackEmpty(SqStack s)
{
if(s.top == s.base)
{
return TRUE;
}
else
{
return FALSE;
}
} 测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
int res = StackLength(st);
printf("当前栈的长度是：%d\n",res);
Status res1 = StackEmpty(st);
if(res1)
{
printf("栈为空\n");
}
else
{
printf("栈不为空\n");
}
}10、将栈设置为空
// 将栈设置为空
void ClearStack(SqStack *s)
{
s->top = s->base;
}测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
printf("清空栈中数据开始 ---- \n");
ClearStack(&st);
printf("清空栈中数据结束 ---- \n");
int len = StackLength(st);
printf("清空后栈的长度是：%d\n",len);
}11、销毁栈空间
// 销毁栈空间
void DestoryStack(SqStack *s)
{
free(s->base);
s->top = NULL;
s->base = NULL;
s->stacksize = 0;
}
测试代码：
void Stack_test(void)
{
SqStack st;
InitStack(&st);
int i = 0;
for(i=1;i<8;i++)
{
Push(&st,i);
}
printf("栈中元素有：");
StackTraverse(st);
printf("销毁栈空间开始 ---- \n");
DestoryStack(&st);
printf("销毁栈空间结束 ---- \n");
int len = StackLength(st);
printf("清空后栈的长度是：%d\n",len);
}注意写的所有函数记得在Stack.h中进行声明。
#ifndef _STACK_H
#define _STACK_H
#include "main.h"
#define STACK_INT_SIZE 10 // 栈初始容量为10
#define STACK_INCREMENT 2 // 空间不够每次增加两个
// 栈结构类型
typedef struct
{
SElemType *base; // 栈底指针，栈构造和销毁后为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前栈的容量，分配的空间数
}SqStack;
void Stack_test(void);
void InitStack(SqStack *sp) ;
void Push(SqStack *sp,SElemType e);
void StackTraverse(SqStack s);
Status Pop(SqStack s,SElemType *e) ;
int StackLength(SqStack s) ;
Status StackEmpty(SqStack s);
void ClearStack(SqStack *s) ;
void DestoryStack(SqStack *s);
#endif