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

image-20220906160029042

栈的表示与实现

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

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

顺序栈的表示和实现

顺序栈的存储方式

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

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

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

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

image-20220906105937827

空栈与满栈:

image-20220906110756778

栈满时的处理方法:

  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; 
}

链栈的表示和实现

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

image-20220906140818068

它的类型定义,类似于单链表:

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;
}

链栈的入栈

image-20220906142656455

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

链栈的出栈

image-20220906143433009

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;
}
🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/95.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 24 日
赏杯咖啡