栈的抽象数据类型的类型定义

栈的表示与实现

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现力式。

• 栈的顺序存储——顺序栈
• 栈的链式存储——链栈

顺序栈的表示和实现

顺序栈的存储方式

存储方式：同一般线性表的顺序存储结构完全相同，

• 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
• 附设 top 指针，指示栈顶元素在顺序栈中的位置。
• 另设 base 指针，指示栈底元素在顺序栈中的位置。

但是，为了方便操作，通常 top 指示真正的栈顶元素之上的下标地址

• 另外，用 stacksize 表示栈可使用的最大容量

空栈与满栈：

栈满时的处理方法：

1. 报错返回操作系统。
2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

使用数组作为顺序栈存储方式的特点：

• 简单、方便、但易产生溢出（数组大小固定）

但是容易产生溢出，

• 上溢（overflow）：栈已经满，又要压入元素
• 下溢（underflow）：栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是种结束条件，即问题处理结束。

顺序栈的表示

#define MAXSIZE 100
typedef struct{
    SElemType *base;    // 栈底指针
    SElemType *top;        // 栈顶指针
    int stacksize;        // 栈可用的最大容量
}SqStack;

顺序栈的初始化

// 构造一个空栈
Status InitStack(SqStack &S){
    S.base = new SElemType[MAXSIZE];
    // S.base = (SElemType*)malloc(MAXSIZE *sizeof(SElemType));
    if(!S.base) exit (OVERFLOW); // 存储分配失败
    S.top = S.base;    // 栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

判断栈是否为空

Status StackEmpty(SqStack S){
    // 若栈为空，返回TRUE；否则返回FALSE
    if(S.top == S.base) return TRUE;
    else return FALSE;
}

求顺序栈的长度

int StackLength(SqStack S){
    return S.top - S.base;
}

清空顺序栈

Status ClearStack(SqStack &S){
    if(S.base) S.top = S.base;
    return OK;
}

销毁顺序栈

Status DestoryStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL:
    }
    return OK;
}

顺序栈的入栈

（1）判断是否栈满，若满则出错（上溢）
（2）元素 e 压入栈顶
（3）栈顶指针加 1

Status Push(SqStack &S,SElemType e){
    if(S.top-S.base == S.stacksize) return ERROR;    //栈满
    *S.top = e; // *top top指针所指向的值，解引用
    S.top++;
    // 上面两步可以合并为一步
    // *S.top++ = e;
    return OK;
}

顺序栈的出栈

（1）判断是否栈空，若空则出错（下溢）
（2）栈顶指针减1
（3）获取栈顶元素 e

Status Pop(SqStack &S,SElemType e){
    // 若栈不空，则删除S的栈顶无素，用e返回其值,并返回OK；否则返回ERROR
    if(S.top==S.base) return ERROR;
    --S.top;
    e = *S.top
        // 上面两步可以合并为一步
    // e = *--S.top;
    return OK; 
}

链栈的表示和实现

链栈是运算受限的单链表，只能在链表头部进行操作

它的类型定义，类似于单链表：

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;
LinkStack S;

• 链表的头指针就是栈顶
• 不需要头结点
• 基本不存在栈满的情况
• 空栈相当于头指针指向空
• 插入和删除仅在栈顶处执行

链栈的初始化

void InitStack(LinkStack &S){
    // 构造一个空栈，栈顶指针置为空
    S = NULL;
    return OK;
}

判断链栈是否为空

Status StackEmpty(LinkStack S){
    if (S == NULL) return TRUE;
    else return FALSE;
}

链栈的入栈

Status Push(LinkStack &S,ElemType e){
    p = new StackNode;    // 生成新结点
    p->data = e;     // 将新结点数据域置为e
    p->next = S;    // 将新结点插入栈顶
    S = p;            // 修改栈顶指针
    return OK;
}

链栈的出栈

Status Pop(LinkStack &S,ElemType &e){    // 删除的结点由变量e来返回
    if(S == NULL) return ERROR;
    LinkStack p;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S){
    if(S != NULL)
        return S->data;
}