stack栈的学习

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。

 

栈的定义
    　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
　　(2)当表中没有元素时称为空栈。
　　(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
    　栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

 

1顺序栈（略）栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

 

2链栈：栈的链式存储结构称为链栈。

（1），链栈的类型定义：

   

typedef struct stacknode{
    DataType data;
    struct stacknode *next;
}StackNode; //节点定义

typedef struct{
    StackNode *top;
}LinkStack; //栈顶指针定义

（2）置栈空

void InitStack(LinkStack *s)
{
   s->top = NULL;
}

(3)判栈空

int StackEmpty(LinkStack *s)
{
    return s->top == NULL;
}

(4)进栈

void Push(LinkStack *s,DataType x)
{
    StackNode *p = (StackNode *)malloc(sizeof(StackNode))
    p->data = x;
    p->next = s->top;
    s->top = p;
}

(5)出栈

DataType Pop(LinkStack *s)
{
    DataType x;
    StackNode *p = s->top;
    if(StackEmpty(s))
        Error("Stack underflow");//出错退出

    x = p->data;
    s->top = p->next;
    free(p);

    return x;
}

(6)取栈顶元素

DataType StackTop(LinkStack *s)
{
    StackNode *p = s->top;
    if(StackEmpty(s))
        Error("Stack underflow");//出错退出
    return p->data;
}

注意：
　    链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。 

原文：