一步一步写算法（之线性堆栈）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
前面我们讲到了队列，今天我们接着讨论另外一种数据结构：堆栈。堆栈几乎是程序设计的命脉，没有堆栈就没有函数调用，当然也就没有软件设计。那么堆栈有什么特殊的属性呢？其实，堆栈的属性主要表现在下面两个方面：
（1）堆栈的数据是先入后出
（2）堆栈的长度取决于栈顶的高度
那么，作为连续内存类型的堆栈应该怎么设计呢？大家可以自己先试一下：
（1）设计堆栈节点
typedef struct _STACK_NODE
{
int* pData;
int length;
int top;
}STACK_NODE;
typedef struct _STACK_NODE
{
int* pData;
int length;
int top;
}STACK_NODE; （2）创建堆栈
STACK_NODE* alloca_stack(int number)
{
STACK_NODE* pStackNode = NULL;
if(0 == number)
return NULL;
pStackNode = (STACK_NODE*)malloc(sizeof(STACK_NODE));
assert(NULL != pStackNode);
memset(pStackNode, 0, sizeof(STACK_NODE));
pStackNode->pData = (int*)malloc(sizeof(int) * number);
if(NULL == pStackNode->pData){
free(pStackNode);
return NULL;
}
memset(pStackNode->pData, 0, sizeof(int) * number);
pStackNode-> length = number;
pStackNode-> top= 0;
return pStackNode;
}
STACK_NODE* alloca_stack(int number)
{
STACK_NODE* pStackNode = NULL;
if(0 == number)
return NULL;
pStackNode = (STACK_NODE*)malloc(sizeof(STACK_NODE));
assert(NULL != pStackNode);
memset(pStackNode, 0, sizeof(STACK_NODE));
pStackNode->pData = (int*)malloc(sizeof(int) * number);
if(NULL == pStackNode->pData){
free(pStackNode);
return NULL;
}
memset(pStackNode->pData, 0, sizeof(int) * number);
pStackNode-> length = number;
pStackNode-> top= 0;
return pStackNode;
} （3）释放堆栈
STATUS free_stack(const STACK_NODE* pStackNode)
{
if(NULL == pStackNode)
return FALSE;
assert(NULL != pStackNode->pData);
free(pStackNode->pData);
free((void*)pStackNode);
return TRUE;
}
STATUS free_stack(const STACK_NODE* pStackNode)
{
if(NULL == pStackNode)
return FALSE;
assert(NULL != pStackNode->pData);
free(pStackNode->pData);
free((void*)pStackNode);
return TRUE;
} （4）堆栈压入数据
STATUS stack_push(STACK_NODE* pStackNode, int value)
{
if(NULL == pStackNode)
return FALSE;
if(pStackNode->length = pStackNode->top)
return FALSE;
pStackNode->pData[pStackNode->top ++] = value;
return TRUE;
}
STATUS stack_push(STACK_NODE* pStackNode, int value)
{
if(NULL == pStackNode)
return FALSE;
if(pStackNode->length = pStackNode->top)
return FALSE;
pStackNode->pData[pStackNode->top ++] = value;
return TRUE;
} （5）堆栈弹出数据
STATUS stack_pop(STACK_NODE* pStackNode, int* value)
{
if(NULL == pStackNode || NULL == value)
return FALSE;
if(0 == pStackNode->top)
return FALSE;
*value = pStackNode->pData[-- pStackNode->top];
return TRUE;
}
STATUS stack_pop(STACK_NODE* pStackNode, int* value)
{
if(NULL == pStackNode || NULL == value)
return FALSE;
if(0 == pStackNode->top)
return FALSE;
*value = pStackNode->pData[-- pStackNode->top];
return TRUE;
} （6）统计当前堆栈中包含多少数据
int count_stack_number(const STACK_NODE* pStackNode)
{
return pStackNode->top;
}
int count_stack_number(const STACK_NODE* pStackNode)
{
return pStackNode->top;
}
建议： 堆栈是函数调用的基础，是递归调用的基础，是很多问题的根源，建议朋友
补充：软件开发 , C语言 ,
