返回首页 一步一步写算法

线性堆栈

前面我们讲到了队列,今天我们接着讨论另外一种数据结构:堆栈。堆栈几乎是程序设计的命脉,没有堆栈就没有函数调用,当然也就没有软件设计。那么堆栈有什么特殊的属性呢?其实,堆栈的属性主要表现在下面两个方面:

(1)堆栈的数据是先入后出

(2)堆栈的长度取决于栈顶的高度

那么,作为连续内存类型的堆栈应该怎么设计呢?大家可以自己先试一下:

(1)设计堆栈节点

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;
}

(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;
}

(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;
}

(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;
}

(6)统计当前堆栈中包含多少数据

int count_stack_number(const STACK_NODE* pStackNode)
{
    return pStackNode->top;
}

建议: 堆栈是函数调用的基础,是递归调用的基础,是很多问题的根源,建议朋友们平时有时间好好练习一下。

上一篇: 线性队列 下一篇: 单向链表