【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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;
}
建議： 堆棧是函數調用的基礎，是遞歸調用的基礎，是很多問題的根源，建議朋友們平時有時間好好練習一下。
