随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

栈学习---数组实现

今天学习了栈,据说栈是一个很重要的数据结构。其主要的思想为:
1. 栈是一个后进先出的数据结构(last-in, first-out LIFO)。
2. 他的主要操作有“IsEmpty() 判断栈空。Push()插入数据。Pop弹出数据。
3. 他的核心数据为栈顶,栈数据区域。栈顶表示最后一个数据的位置,也表示了栈中数据的个数。我这里是有一个int来表示。栈空的时候,栈顶位置为0。要得到栈顶元素,只需要用nData[nTop]就可以了。nData是他的数据区域。
4. 实现的一些细节,我栈顶的初始值为0,他代表什么数据也没有,压入数据的时候,先把栈顶加1,然后使nData[nTop] = 数据。这样在出栈和得到栈顶元素都很方便。也很方便的得到栈的数据个数。下标为0的空间没有用,浪费了这个空间得到了操作的方便。还有就是注意判断栈是否满了,如果满了还添加的话,栈溢出。也要判断栈如果已经为空了,就不能在弹出(pop)数据了。
也就这么多了,奉上源代码:我这个是用数组写的:
#include <stdio.h>
#include 
<stdlib.h>
#include 
<assert.h>

//定义一个栈的结构体
struct MyStack 
{
    
int nTop;        //栈顶位置
    int nData[11];    //栈的数据区域
}
;

MyStack g_stack;

//判断栈是否为空,空返回true
bool IsEmpty()
{
    
return !g_stack.nTop;
}


//设置栈为空
int SetEmpty()
{
    g_stack.nTop 
= 0;
    
return 0;
}


//压数据入栈
int Push(int nData)
{
    assert(g_stack.nTop 
< 10);
    
++g_stack.nTop;
    g_stack.nData[g_stack.nTop] 
= nData;
    
return g_stack.nTop;
}


//得到栈顶的引用
int& GetTop()
{
    assert(g_stack.nTop);
    
return g_stack.nData[g_stack.nTop];
}


//弹出栈顶元素,返回弹出的元素。
int Pop(void)
{
    assert(g_stack.nTop);
    
--g_stack.nTop;
    
return g_stack.nData[g_stack.nTop + 1];
}


int main()
{
    SetEmpty();

    
//测试栈
    if (IsEmpty())
    
{
        printf(
"MyStack Is Empty!\n");
    }


    
for (int i = 0; i < 10++i)
    
{
        Push(i);
        printf(
"%d ", GetTop());
    }

    printf(
"\n");
    
while (!IsEmpty())
    
{
        printf(
"%d ", Pop());
    }

    printf(
"\n");

    system(
"pause");
    
return 0;
}

posted on 2009-04-29 20:32 shongbee2 阅读(1458) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理