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 -2typedef 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);#endif

Stack.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;   // 栈底指针，栈构造和销毁后为NULLSElemType *top;   // 栈顶指针int stacksize;    // 当前栈的容量，分配的空间数		
}SqStack;void Stack_test(void);#endif

3、初始化栈

// 初始化栈 
// - 在函数内部修改外部栈空间的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 s,SElemType *e) 
{if(s.top == s.base) {return ERROR;}--(s.top);*e = *(s.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;   // 栈底指针，栈构造和销毁后为NULLSElemType *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