算法学习记录栈

栈

栈是一个重要的数据结构，在操作系统中应用非常广泛，特别在多任务操作系统中，进程与进程间的调用都需要用到栈。

现实中最好的例子我认为是枪的弹夹，把子弹压入到弹夹盒子里面，先放进去的最后才能出来（FILO）frist in last out ，

压入子弹的过程叫做进栈。开枪的过程叫出栈。

用c来实现栈，主要操作是 初始化，判断空，出栈，进栈等。

栈和链表一样可以分为两种，顺序栈和链栈。

顺序栈实质上就是数组，移动栈顶指针指向就能操作顺序栈的基本操作，主要是对数组的下标判断和操作。

0.链栈的数据结构：

typedef struct stNode{ //栈的数据结构，一个数据和一个指针
    int data;
    struct stNode *next;
}stkNode,*pStkNode;

typedef struct listst{ //链栈的栈顶结构，一个栈的指针结构和一个计数
    pStkNode top;
    int count;
}listTop;

这里定义了两个数据结构，一个栈的结构和一个栈顶指针的结构。

1.初始化：

初始化结构，至于为什么要用两级指针，参考第一篇文章。

a.设置一个栈顶指针

b.设置栈顶指针

void init_stack(pStkNode *ls,listTop *t)
{
    *ls = (pStkNode)malloc(sizeof(stkNode));
    (*ls)->data = 0;
    (*ls)->next = NULL;
    (*t).count = 0;
    (*t).top = (*ls);
}

 这里可以理解为，*ls *t 作为形参，但是他们的实参绑定了。即*t只指向*ls的链栈。

2.判断空

bool isEmpty(listTop t)
{
    if (t.count != 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

3.进栈

过程：

a.开辟一个栈空间

b.把数据单元赋值给栈空间

c.该栈空间指向top的指向节点。（实质上：新开辟的节点通过top使新开辟的空间的next指向栈顶空间，蓝色的线。）

d.top指向该新生成的节点

代码如下：

void pushstack(int elem,listTop *t)
{
    pStkNode n = (pStkNode)malloc(sizeof(stkNode)); //（a）
    n->data = elem;                                    //（b）
    n->next = (*t).top;                                //（c）
    (*t).top = n;                                    //（d）
    (*t).count = (*t).count +1;
}

4.出栈

过程：

a.标记出栈指针

b.top指针后移

c.free出栈节点

d.计数减1

代码：

void popstack(listTop *t)
{
    pStkNode p = (*t).top;
    (*t).top = (*t).top->next;
    (*t).count = (*t).count - 1;
    free(p);
}

基本操作完成，其他可以自己加。

打印栈，从栈顶开始

void prt_stack(listTop t)
{
    int len = t.count;
    printf("len is %d\n",len);
    pStkNode pos = t.top;
    while (len > 0)
    {
        int x = pos->data;
        printf(" %d ",x);
        pos = pos->next;
        len--;
    }
}

测试：

int _tmain(int argc, _TCHAR* argv[])
{
    int ary[10]= {1,5,89,65,23,14,52,34,26,76};
    pStkNode list = NULL;
    listTop top;
    
                
    init_stack(&list,&top);//初始化

    int i;
    printf("push array in stack!\n");
    for (i=0;i<10;i++)
    {                        //进栈
        pushstack(list,ary[i],&top);
    }
    prt_stack(top);

    printf("pop the top of stack!\n");
    popstack(list,&top);//出栈
    prt_stack(top);

    return 0;
}