堆栈

堆栈

定义

堆栈是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由一个称为栈顶指针的变量给出。当表中没有元素时，称之为空栈。
由于堆栈只允许在一端操作，后进入的数据往往会先处理，简称为后进先出，如下图

堆栈的基本操作

1、插入（进栈、入栈）
2、删除（出栈、退栈）
3、测试堆栈是否为空
4、测试堆栈是否已满
5、检索当前栈顶元素
其操作收到位置的限制，所以只是一般线性表操作的一个子集。

堆栈的顺序存储结构和操作

1、构造原理
描述堆栈的顺序存储结构最简单的方法是利用一维数组STACK[ 0: M–1 ]来表示，同时定义一个整型变量(不妨取名为top)给出栈顶元素的位置，如下图

C语言实现如下：

#define M 1000
SElemType STACK[M];
int top;

2、初始化堆栈

void INITIALS( int top ){
    top= –1;
}

3、测试堆栈是否为空

int EMPTYS( int top ){
    return top == –1;
}

4、测试堆栈是否已满

int FULLS( int top ){
    return top==M–1;
}

5、插入（进栈）算法

int PUSH( SElemType STACK[ ], int top, SElmeType item ){
    if( FULLS(top) )
        return 0;
    else {
        STACK[++top]=item；
        return 1;
    }
}

6、删除（出栈）算法

int POP( SElemType STACK[ ], int top, SElemType item ){
    if( EMPTYS(top) )
        return 0;
    else{
        item=STACK[top--];
        return 1;
    }
}

堆栈的链式存储结构

1、构造原理
链接堆栈就是用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量( 这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。栈为空时，有top=NULL。如下图

C语言实现如下：

typedef struct node { 
    SElmeType data;
    struct node *link;
} STNode, *STLink;

2、堆栈初始化

void INITIAL( STLink top ){
    top=NULL;
}

3、测试堆栈是否为空

int EMPTYS( STLink top ){
    return top==NULL;
}

4、插入（进栈）算法

int PUSHLINK( STLink top, SElemType item ){ 
    STLink p;
    if( !(p=(STLink)malloc(sizeof(STNode)) )          //申请一个新的链节点
        return 0; 
    else{
        p->data=item;      /*将item送新结点数据域*/
        p->link=top;         /*将新结点插在链表最前面*/
        top=p;                 /*修改栈顶指针的指向*/
        return 1;
    }
}

5、删除（退栈）算法

int POPLINK( STLink top, SElemType item ){ 
    STLink p;
    if ( EMPTYS(top) ) 
        return 0;       /* 删除失败*/
    else {
        p=top;          /* 暂时保存栈顶结点的地址*/
        item=top->data;             /*保存被删栈顶的数据信息*/
        top=top->link;               /* 删除栈顶结点*/
        free(p);                         /* 释放被删除结点*/
        return 1;                       /* 删除成功*/
    }
}