04栈

4.1栈的定义：后进先出

栈是允许在同一端进行插入和删除操作的数据结构。被允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为出栈（POP）。

由于栈规定只能在同一端进行插入和删除，因此栈的一个典型特点就是后进先出。

为了理解栈的后进先出特性，下面来看一道BAT的笔试题：

一个栈的入栈序列为ABCDE，则不可能的出栈序列为？

A.     ECDBA
B.     DCEAB
C.     DECBA
D.     ABCDE
E.     EDCBA

答案：A,B

分析：

A：E最先出栈，所以ABCD已经先后入栈，所以，根据后进先出，C不可能比D先出栈

B：D出，C出，E入E出，AB已经先后入栈，所以，A不可能比B先出

C：D出E入E出C出B出A出

D：A入A出B入B出C入C出D入D出E入E出

E：E出D出C出B出A出

4.2 栈的结构

栈的底层数据结构包含链表与数组。可以通过链表或者数组来构造栈，如下图所示：上边是基于链表的栈，下边是基于数组的栈。

4.3 栈的基本操作

1栈的创建

int CreateStack();

负责初始化栈的基本结构，比如栈顶指针的初始化。

2入栈

int Push(int data);

将数据从栈顶插入

3出栈

int Pop(int *data);

获取栈顶数据，并将数据从栈顶删除

4栈空判断

int IsStackEmpty();

判断栈是否为空，栈为空，就不能再pop了。

5栈满

int IsStackFull();

判断栈是否为满，栈满就不能再插入数据了。只有基于数组的栈，才需要判断栈是否已满。

4.4 基于链表的栈

现在来实现基于链表的栈的常规操作。（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）。

先定义栈的结点结构：

typedef struct _node
{
    int value;
    struct _node *next;
}node,*pnode;
栈顶指针初始化：
node *top = NULL;
创建栈：
int CreateStack()
{
    top = NULL;
    return 1;
}
判断栈是否为空：
int IsStackEmpty()
{
    return top==NULL?1:0;//top为NULL的时候，栈为空
}
入栈：
int Push(int value)
{
    node *p = (node *)malloc(sizeof(node));
    if(p==NULL)
    {
        return -1;
    }
    memset(p,0,sizeof(node));
    p->value=value;
    p->next=NULL;
    //栈为空的时候，插入的是第一个结点
    if(IsStackEmpty())
    {
        top=p;
        return 1;
    }
    //栈非空的时候，插入一个结点
    p->next = top;
    top=p;
    return 1;
}
出栈
int Pop(int *e)
{
    if(IsStackEmpty())
    {
        return -1;
    }
    if(e==NULL)
    {
        return -1;
    }
    //当栈只有一个结点的时候：
    if(top->next==NULL)
    {
        *e = top->value;
        free(top);
        top=NULL;
        return 1;
    }
    //当栈中存放不止一个元素的时候
    *e = top->value;
    node *p=top;
    top=top->next;
    free(p);
    return 1;
}
栈的遍历：
void TraverseStack()
{
    while(!IsStackEmpty())
    {
        int val;
        Pop(&val);
        printf("%d ", val);
      
    }
    printf("\n");
}
接口测试：
int _tmain(int argc, _TCHAR* argv[])
{
    CreateStack();
    for(int i=0;i<100;i++)
    {
        Push(i+1);
    }
    int val;
    Pop(&val);
    printf("val:%d\n", val);
    TraverseStack();
    return 0;
}

4.5 基于数组的栈

下面来实现基于数组的栈的常规操作。（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）。如下图所示，栈顶top指向数组中下一个空位：

#define MAXSIZE 1000//栈中数组容纳的元素个数
int Stack[MAXSIZE]={0};//栈的底层数据结构：数组stack
int top=0;//栈顶
创建栈
int CreateStack()
{
    top=0;//将top置零
    return 1;
}
判断栈是否满
int IsStackFull()
{
    return top==MAXSIZE?1:0;
}
判断栈是否空
int IsStackEmpty()
{
    return top==0?1:0;
}
入栈：
int push(int val)
{
    if(IsStackFull())
    {
        return -1;
    }
    Stack[top]=val;
    top++;
    return 1;
}
出栈：
int pop(int *e)
{
    if(IsStackEmpty())
    {
        return -1;
    }
    if(e==NULL)
    {
        return -1;
    }
    top--;
    *e = Stack[top];
    return 1;
}
栈的遍历：
void TraverseStack()
{
    while(!IsStackEmpty())
    {
        int val;
        pop(&val);
        printf("%d ",val);
    }
    printf("\n");
}
接口测试：
int _tmain(int argc, _TCHAR* argv[])
{
    CreateStack();
    for(int i=0;i<500;i++)
    {
        push(i+1);
    }
    int val;
    pop(&val);
    printf("val:%d\n", val);
    TraverseStack();
    return 0;
}

本页共215段，3582个字符，5313 Byte(字节)



大

中

小

∧

↑

↓

∨