一步一步写算法(之线性堆栈)

原文:一步一步写算法(之线性堆栈)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

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

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

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


【预告: 下面一篇博客介绍链表的内容】

时间: 2024-10-27 14:30:20

一步一步写算法(之线性堆栈)的相关文章

一步一步写算法(之线性结构的处理)

原文:一步一步写算法(之线性结构的处理) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     我们知道,在内存中的空间都是连续的.也就是说,0x00000001下面的地址必然是0x00000002.所以,空间上是不会出现地址的突变的.那什么数据结构类型是连续内部空间呢,其实就是数组,当然也可以是堆.数组有很多优势,它可以在一段连续空间内保存相同类型的数据,并且对这些数据进行管理.所以从这个意义上说,掌握了数组才能说明你数据结构入门了.

一步一步写算法(之线性队列)

原文:一步一步写算法(之线性队列) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     这里的线性结构实际上指的就是连续内存的意思,只不过使用"线性"这个词显得比较专业而已.前面一篇博客介绍了现象结构的处理方法,那么在这个基础之上我们是不是添加一些属性形成一种新的数据结构类型呢?答案是肯定的,队列便是其中的一种.     队列的性质很简单:     (1)队列有头部和尾部     (2)队列从尾部压入数据     (3)队列

一步一步写算法(之 算法总结)

原文:一步一步写算法(之 算法总结) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]       自10月初编写算法系列的博客以来,陆陆续续以来写了几十篇.按照计划,还有三个部分的内容没有介绍,主要是(Dijkstra算法.二叉平衡树.红黑树).这部分会在后面的博客补充完整.这里主要是做一个总结,有兴趣的朋友可以好好看看,欢迎大家提出宝贵意见.       (1) 排序算法     快速排序           合并排序     堆排序

一步一步写算法(之排序二叉树)

原文:一步一步写算法(之排序二叉树) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面我们讲过双向链表的数据结构.每一个循环节点有两个指针,一个指向前面一个节点,一个指向后继节点,这样所有的节点像一颗颗珍珠一样被一根线穿在了一起.然而今天我们讨论的数据结构却有一点不同,它有三个节点.它是这样定义的: typedef struct _TREE_NODE { int data; struct _TREE_NODE* parent;

一步一步写算法(之链表逆转)

原文:一步一步写算法(之链表逆转) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     链表逆转是面试环境中经常遇到的一道题目,也是我们在实际开发中可能会遇到的开发需求.和线性逆转不一样,单向链表的节点需要一个一个进行处理.为了显示两者之间的区别,我们分别对线性内存和链表进行逆转:     (1)普通连续内存数据的反转分析 STATUS normal_revert(int array[], int length) { int* pDa

一步一步写算法(之链表排序)

原文:一步一步写算法(之链表排序) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     相比较线性表的排序而言,链表排序的内容稍微麻烦一点.一方面,你要考虑数据插入的步骤:另外一方面你也要对指针有所顾虑.要是有一步的内容错了,那么操作系统会马上给你弹出一个exception.就链表的特殊性而言,适合于链表的排序有哪些呢?     (1)插入排序    (适合)     (2)冒泡排序    (适合)     (3)希尔排序    (适

一步一步写算法(之hash表)

原文:一步一步写算法(之hash表) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     hash表,有时候也被称为散列表.个人认为,hash表是介于链表和二叉树之间的一种中间结构.链表使用十分方便,但是数据查找十分麻烦:二叉树中的数据严格有序,但是这是以多一个指针作为代价的结果.hash表既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便.     打个比方来说,所有的数据就好像许许多多的书本.如果这些书本是一本一本堆

一步一步写算法(之单向链表)

原文:一步一步写算法(之单向链表) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     有的时候,处于内存中的数据并不是连续的.那么这时候,我们就需要在数据结构中添加一个属性,这个属性会记录下面一个数据的地址.有了这个地址之后,所有的数据就像一条链子一样串起来了,那么这个地址属性就起到了穿线连结的作用.     相比较普通的线性结构,链表结构的优势是什么呢?我们可以总结一下:     (1)单个节点创建非常方便,普通的线性内存通常在创

一步一步写算法(之二叉树深度遍历)

原文:一步一步写算法(之二叉树深度遍历) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     深度遍历是软件开发中经常遇到的遍历方法.常用的遍历方法主要有下面三种:(1)前序遍历:(2)中序遍历:(3)后序遍历.按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根.代码实现起来也不复杂.     1)前序遍历 void preorder_traverse(TREE_NOD