数据结构：栈的实现及应用场景
学习数据结构：如数组、链表和栈 #生活技巧# #工作学习技巧# #编程学习路径#
目录
一、栈
二、顺序栈的实现
三、链式栈的实现
四、栈的应用场景
一、栈栈限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈所需要的一般功能：
初始化栈栈是否为空（栈是否为满）入栈出栈遍历栈清空栈栈的分类：
顺序栈：存储核心是数组，在初始化就需要决定开辟栈空间的大小，在操作的时候需要注意栈空间是否有空余。链式栈：存储核心是链表，可以任意进行入栈与出栈操作
typedef struct stack
{
int *stack;
int size;
int top;
}stack, *stack_p;
初始化*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));
sp->size = 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<sp->size; 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<size; 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、递归
待补充网址：数据结构：栈的实现及应用场景 https://www.yuejiaxmz.com/news/view/765737
相关内容
数据结构：顺序栈的基本操作数据个性化推荐系统应用场景及架构实现...
栈与队列在IT中的实际应用场景与Python示例
达观数据个性化推荐系统应用场景及架构实现
金融机构常用数据安全技术及典型应用场景 – 数治网
实时数据分析：实时数据流与实时应用场景
互联网征信+应用场景=征信大数据
C++栈实现详解
23种设计模式总结及应用场景
场景数字化：构建场景驱动的发展模式
