2007年十一月月 发布的文章

也谈'万能'栈

在网上搜索"万能"二字的英文翻译,结果却无意中看到有人提到了如何设计"万能栈"。栈(stack)是比较基础(fundamental)的数据结构,实现起来一般都比较容易。但一般的栈(stack)的实现都是局限于某种特定类型的,比如一个存储32-bit整型的栈。如果对于同一份栈实现,要求可以存储多种数据类型的话,那就需要仔细想想了。而这样的栈实现也就被戏称"万能"栈。

这里对"万能"栈再做一个分类:同构数据"万能"栈和异构数据"万能"栈。简单解释一下:同构数据"万能"栈指得是这个栈可以存储多种类型数据,但是每次使用该栈时只使用其中一种类型数据;异构数据"万能"栈则说的是这个栈可以存储多种类型数据,而且使用时也是多种数据混合处理。

对于同构的"万能"栈,像C++、Java这样有模板支持的语言来说,是很好实现的。C++的标准库中就携带了一个通用的stack类,使用起来也很是方便:
stack<int> s;
for( int i=0; i < 10; i++ )
    s.push(i);  

但是对于使用C语言的人来说,栈是需要自己实现的。那么如何实现一个同构数据"万能"栈呢?我的想法是借用union的语法功能:
union general_unit {
        void  *vp;
        void (*fp)(void);
        char  *cp;
        long   l;
        double d;
    long long ll;
};

struct stack_item_t {
        union general_unit item;
};
这样我在准备我的item的时候,就可以按需选取union中提供的相应类型的member。比如:
struct stack_item_t item;
item.item.l = 5;
push(&item);

这里其实也是有些别扭的,别扭在于谁来管理数据存储的问题。对于char, int, long, float, doule这样的语言本身提供的基本数据类型,大可存储在stack中。但是对于其他非基本数据类型的数据,我们只能将其指针放到栈中了,这时你就要保证push到栈中的地址在栈的活动期是有效的,像下面这样的肯定会出错:
typedef struct Foo {
    //…
} Foo;

void foo(void) {
    Foo foo;
    //init…
    struct stack_item_t item;
    item.item.vp = (void*)&foo;
    push(&item);
}

int main(void) {
    struct stack_item_t item;
    item = pop();
    Foo *pfoo = (Foo*)item.vp;
    pfoo->xxx; //error;    
}

如果上面的例子中存储的是函数指针的话,那么问题就不大了,因为函数地址在程序构建之后其地址就是全局可访问且始终不变的。

有了上面的基础,异构的"万能"栈实现也就容易了。异构栈要求:pop时候我也要知道pop出来的item的类型,那么只用union显然不能完成这个任务了,我们需要有一个字段来标识一下存储的类型是什么或者说标识使用了general_unit中的哪个成员,便于上层使用,方法如下:
union general_unit {
        void  *vp;
        void (*fp)(void);
        char  *cp;
        long   l;
        double d;
    long long ll;
};

struct general_item {
    union general_unit unit;
    int ut_type; //用于标识栈中数据的类型
};

struct stack_item_t {
        struct general_item item;
};

这样在pop时我们需要如是做:
item = pop();
switch(item.item.ut_type) {
    case xx:
        //…
    case yy:
        //…
    //…
}
看起来还是比较麻烦的。

以上只是"万能"栈的一种想法而已,C语言博大精深,有很多诡秘的技巧是我所不知的,也许很多人还有更好的方法。

为什么要给万能二字加上引号呢?其实就是说明这个"万能"只是一个相对的概念,这个相对的"万能"带来的是数据存储管理的不一致以及接口的不易用。在平时使用时尽量避免使用这种所谓的"万能"栈,一般来说我们都会使用比较单一类型的栈实现,这样的栈简单、高效、易用且不易出错。

'嫦娥'发回月球照片

今天上午国家首次公布了’嫦娥’发回的月球照片,这里贴出来留作纪念。


‘嫦娥’发回的月表照片

该照片向我们展示的是灰凸凸的月表,貌似没有日本的’月亮女神’发回来的从月球看地球升起’给人的印象深刻。

见证国足进入死亡之组

刚刚看完2010南非世界杯预选赛抽签直播,见证了中国队被分到死亡之组的全过程。

感觉这应该不是什么抽签,都是事先安排好的,那几个抽签嘉宾只是按照一定的顺序从容器里拿出抽签球罢了。从中国队被抽到死亡之组来看,中国足球在亚洲的地位真是不咋地,没地位啊。日本、韩国由此看来应该在亚洲处于领先地位的,而初来咋到的澳大利亚显然需要接受一下亚洲人的考验了。

很讨厌CCTV-5那几个主持人在那胡乱评论,在什么赛程、时差上胡扯。既然赛程已经定了,剩下的就是拼实力和赛前的准备了。说到赛前准备我们应该向德国人学习。前不久看到天下足球才知道,2006世界杯德国门将莱曼扑出阿根廷人两个点球关键就在于赛前德国人研究了阿根廷每位球员的点球习惯,在点球大战前,技术官员递给莱曼一个纸条,通过这个纸条莱曼对站在点球点上阿根廷球员就了如指掌了,哪有不胜的道理。

啥都别想了,努力提高实力才是正道。




这里是Tony Bai的个人Blog,欢迎访问、订阅和留言!订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:


如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:


以太币:


如果您喜欢通过微信App浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:



本站Powered by Digital Ocean VPS。

选择Digital Ocean VPS主机,即可获得10美元现金充值,可免费使用两个月哟!

著名主机提供商Linode 10$优惠码:linode10,在这里注册即可免费获得。

阿里云推荐码:1WFZ0V立享9折!

View Tony Bai's profile on LinkedIn


文章

评论

  • 正在加载...

分类

标签

归档











更多