目录
一、栈
二、顺序栈的实现
三、链式栈的实现
四、栈的应用场景
一、栈
栈限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈所需要的一般功能：
初始化栈栈是否为空（栈是否为满）入栈出栈遍历栈清空栈
栈的分类：
顺序栈：存储核心是数组，在初始化就需要决定开辟栈空间的大小，在操作的时候需要注意栈空间是否有空余。链式栈：存储核心是链表，可以任意进行入栈与出栈操作
个人对数据结构的一点理解
二、顺序栈的实现
栈的定义
/*栈的定义*/
typedef struct stack
{
int *stack;//指向栈空间
int size;//栈空间大小
int top;//栈顶
}stack, *stack_p;
初始化
/*初始化栈操作，n为需要开辟的空间*/
*stack_p init_stack(int n)
{
stack_p sp = malloc(sizeof(stack));//堆空间
if(sp == NULL)
{
printf("malloc failed\n");
return sp;
}
sp->stack = calloc(n, sizeof(int));//分配n块数据
sp->size = n;//n块数据域
sp->top = -1;//没有存放任何数据 此时 栈顶=栈底
return sp;
}
判断是否为空栈 与 是否为满栈
/*判断栈是否为空*/
bool isEmpty(stack_p sp)
{
return sp->top == -1;
}
/*判断栈是否存放满数据*/
bool isFull(stack_p sp)
{
return sp->top >= sp->size -1;
}
入栈
/*入栈操作, 参数为需要入栈的数据, 以及对应存放的栈*/
bool push(int data, stack_p sp)
{
if(isFull(sp))//入栈前，判断栈空间是否满了
{
printf("stack is full of data\n");
return false;
}
sp->top++;
sp->stack[sp->top] = data;
re
出栈
/*出栈操作*/
bool pop(int *data, stack_p sp)
{
if(isEmpty(sp))//出站前，判断栈空间是否为空
{
printf("stack is empty\n");
return false;
}
*data = sp->stack[sp->top];//先取值
sp->top--;//栈顶往栈底方向移动
return true;
}
遍历栈 与 清空栈
/*显示栈空间中存放的数据*/
void showStackData(stack_p sp)
{
if(isEmpty(sp))//显示前，判断栈是否为空
{
printf("sp is empty\n");
return;
}
int pos;
for(pos=0; pos<=sp->top; pos++)
{
printf("%d\t", sp->stack[pos]);
}
}
/*清空栈*/
void clearStack(stack_p sp)
{
free(sp->stack);
}
三、链式栈的实现
栈的定义与栈节点的定义
/*定义栈存储节点 以及 栈(栈顶与栈底指针)*/
typedef struct stack_Node
{
int data;
struct stack_Node *next;
}stackNode,*stackNode_p;
typedef struct stack
{
stackNode_p top;//栈顶
int size;//有多少个节点
}stack,*stack_p;
栈的初始化
/*初始化栈*/
stack_p init_stack()
{
stack_p sp = malloc(sizeof( stack));
if (sp != NULL)
{
sp->top = NULL;
sp->size = 0;
}
return sp;
}
判断栈是否为空
/*判断栈是否为空*/
bool isEmpty(stack_p sp)
{
return sp->size == 0;
}
入栈
/*
入栈：输入需要入栈的数据
（包含给对应数据创建栈存储节点,不含头结点）
*/
void push(int data, stack_p sp)
{
//创建栈存储节点存放数据
stackNode_p new = malloc(sizeof(stackNode));
if(new != NULL)
{
new->data = data;
//入栈处理
new->next = sp->top;
sp->top = new;
sp->size++;
}
}
出栈
/*出栈*/
bool pop(stack_p sp)
{
//判断栈是否为空
if (isEmpty(sp))
{
printf("stack is empty\n");
return false;
}
//出栈
stackNode_p stNode_p = sp->top;
sp->top = sp->top->next;
sp->size--;
//释放空间
free(stNode_p);
return true;
}
遍历栈
/*遍历栈*/
void showStack(stack_p sp)
{
//判断栈是否为空
if (isEmpty(sp))
{
printf("stack is empty\n");
return;
}
//从栈顶一直打印到栈底
int pos;
stackNode_p tmp = sp->top;
for(pos=0; pos
{
printf("%d\t", tmp->data);
tmp = tmp->next;
}
}
清空栈
/*清空栈*/
bool clearStack(stack_p sp)
{
if (isEmpty(sp))
{
printf("stack is empty\n");
return false;
}
int pos;
int size = sp->size;//记录栈中总数量
stackNode_p tmp;
for(pos=0; pos { //存储栈顶节点 tmp = sp->top; //指向下一数据 sp->top = tmp->next; sp->size--; //释放数据 free(tmp); } return true; } 四、栈的应用场景 1、数制转换 int main(int argc, char const *argv[]) { int data; int tmp; stack_p sp = init_stack(); //输入需要转换进制的数值 printf("请输入需要转换成8进制数的10进制数值\n"); scanf("%d",&data); while(data >0) { push(data%8,sp);//余数入栈 data/=8; } while(1) { if (pop(&tmp,sp) != false) { printf("%d\t", tmp); } else break; } return 0; } 结果： 2、括号匹配 int main(int argc, char const *argv[]) { char data; char tmp_data; stack_p sp = init_stack(); while(1) { printf("请输入需要入栈的括号\n"); data = getchar(); getchar();//吸收回车号 switch(data) { //如果为左括号与左花括号则入栈 case '(': case '{': push(data,sp); showStack(sp); break; case ')': case '}': pop(&tmp_data,sp);//当输入为右括号或者右花括号则出栈对比 showStack(sp); if(data == ')')//将括号反转进行对比 data = '('; else if (data == '}') data = '{'; if (data == tmp_data) printf("匹配成功\n"); else printf("匹配失败\n"); break; } printf("\n"); } return 0; } 测试结果： 3、行编辑程序 待补充 4、迷宫求解 待补充 5、表达式求值 待补充 6、运算符优先级 待补充 7、递归 待补充