随感而发

杂七杂八

统计

留言簿(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 阅读(1483) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


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