品牌网站制作报价表,页面设计标准规范,系统网站界面设计,做电影网站涉及的侵权问题文章转自编程珠玑#xff0c;作者#xff1a;守望先生前言栈是一种应用广泛的数据结构#xff0c;例如函数的调用就需要使用栈#xff0c;其实我们在介绍《栈的操作栈的常见操作有出栈(POP)#xff0c;从栈中弹出一个元素#xff1b;入栈(PUSH)#xff0c;将一个元素压入… 文章转自编程珠玑作者守望先生前言栈是一种应用广泛的数据结构例如函数的调用就需要使用栈其实我们在介绍《栈的操作栈的常见操作有出栈(POP)从栈中弹出一个元素入栈(PUSH)将一个元素压入栈中访问栈顶元素(TOP)判断栈是否为空等。栈的实现栈是较容易实现的抽象数据结构之一。我们可以选择数组或者链表来实现它们各有特点前者容量有限且固定但操作简单而后者容量理论上不受限但是操作并不如数组方便每次入栈要进行内存申请出栈要释放内存稍有不慎便造成内存泄露。本文对两种实现都做介绍。数组实现栈用数组实现栈是比较容易的。这个时候的栈其实更像是访问受限的数组数组可以通过下标访问查找插入等但是栈只能从栈顶或者说数组的末尾进行操作。我们只需要一个指针记录栈顶即可。有人可能问了既然这里栈是访问受限的数组为什么不直接使用数组呢所谓能力越大责任越大而你暴露的越多风险也越大就是如此。我们来看一下数组实现栈的时候栈的操作都是怎么实现的呢定义栈用数组实现栈时是很容易定义的只要定一个固定长度的数组即可然后使用一个指针或者数组下标标记栈顶topOfStack栈为空时它是-1#define STACK_SIZE 64 /*栈大小*/
#define TOP_OF_STACK -1 /*栈顶位置*/
typedef int ElementType /*栈元素类型*/
typedef struct StackInfo
{int topOfStack; /*记录栈顶位置*/ElementType stack[STACK_SIZE]; /*栈数组也可以使用动态数组实现*/
}StackInfo_st;/*创建栈*/
StackInfo_st stack;
stack.topOfStack TOP_OF_STACK;
入栈入栈操作也很简单只需要先将topOfStack加1然后将元素放入数组即可。当然特别要注意检查此时栈是否已满。将1入栈此时topOfStack 0topOfStack1代码实现#define SUCCESS 0
#define FAILURE -1
/*入栈0表示成功非0表示出错*/
int stack_push(StackInfo_st *s, ElementType value)
{if(stack_is_full(s))return FAILURE;/*先增加topOfStack再赋值*/s-topOfStack;s-stack[s-topOfStack] value;return SUCCESS;
}
出栈或访问栈顶元素与入栈相反先访问元素然后将topOfStack减1但是此时要注意检查栈是否已空。访问栈顶元素可直接使用下标访问而不用将topOfStack减1。/*出栈*/
int stack_pop(StackInfo_st *s,ElementType *value)
{/*首先判断栈是否为空*/if(stack_is_empty(s))return FAILURE;*value s-stack[s-topOfStack];s-topOfStack--;return SUCCESS;
}
/*访问栈顶元素*/
int stack_top(StackInfo_st *s,ElementType *value);
{/*首先判断栈是否为空*/if(stack_is_empty(s))return FAILURE;*value s-stack[s-topOfStack];return SUCCESS;
}
判断栈是否满只要判断topOfStack与数组大小-1的大小即可。/*判断栈是否已满满返回1未满返回0*/
int stack_is_full(StackInfo_st *s)
{return s-topOfStack STACK_SIZE - 1;
}
判断栈是否为空只需要判断topOfStack是否小于等于-1即可。/*判断栈是否为空空返回1非空返回0*/
int stack_is_empty(StackInfo_st *s)
{return s-topOfStack - 1;
}
完整可运行代码代码较长可点击阅读原文查看或访问链表实现栈与数组实现栈不一样的地方是链式栈可以动态扩容基本没有长度限制受限于内存。另外它在入栈以及出栈的时候需要申请或者释放内存。创建栈创建栈很容易只需要声明一个头指针即可它的next指针指向栈顶初始时为空/*定义栈结构*/
typedef struct StackInfo
{ElementType value; /*记录栈顶位置*/struct StackInfo *next; /*指向栈的下一个元素*/
}StackInfo_st;/*创建栈外部释放内存*/
StackInfo_st *createStack(void)
{StackInfo_st *stack malloc(sizeof(StackInfo_st));if(NULL stack){printf(malloc failed\n);return NULL;} /*stack-next为栈顶指针*/stack-next NULL;return stack;
}
入栈入栈只需要为新的元素申请内存空间并将栈顶指针指向新的节点即可。入栈操作/*入栈0表示成功非0表示出错*/
int stack_push(StackInfo_st *s,ElementType value)
{StackInfo_st *temp malloc(sizeof(StackInfo_st));if(NULL temp){printf(malloc failed\n);return FAILURE;}/*将新的节点添加s-next前使得s-next永远指向栈顶*/temp-value value;temp-next s-next;s-next temp;return SUCCESS;
}
出栈或访问栈顶元素出栈时将栈顶指针指向下下个节点返回元素值并释放栈顶指针下个节点的内存。而访问栈顶元素只需要返回栈顶指针指向节点的元素值即可。出栈/*出栈*/
int stack_pop(StackInfo_st *s,ElementType *value)
{/*首先判断栈是否为空*/if(stack_is_empty(s))return FAILURE;/*找出栈顶元素*/*value s-next-value;StackInfo_st *temp s-next;s-next s-next-next;/*释放栈顶节点内存*/free(temp);temp NULL;return SUCCESS;
}
/*访问栈顶元素*/
int stack_top(StackInfo_st *s,ElementType *value)
{/*首先判断栈是否为空*/if(stack_is_empty(s))return FAILURE;*value s-next-value;return SUCCESS;
}
判断栈是否为空判断栈空也很简单只需要判断栈顶指针是否为空即可。/*判断栈是否为空空返回1未空返回0*/
int stack_is_empty(StackInfo_st *s)
{/*栈顶指针为空则栈为空*/return s-next NULL;
}
完整可运行代码代码较长可点击阅读原文查看或访问总结本文介绍了栈的基本操作以及栈的基本实现。后面将会介绍一些栈的具体应用。扫码或长按关注回复「 加群 」进入技术群聊
