【数据结构与算法】第五章：栈的表示与操作实现

🙊🙊作者主页：🔗求不脱发的博客

📔📔 精选专栏：🔗数据结构与算法

📋📋 精彩摘要：本章将开启新的内容：栈与队列。栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。本章将简单介绍栈与队列的定义及栈的表示和实现。

💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞

📚目录

📖【数据结构与算法】第五章：栈的表示与操作实现

📝1️⃣栈和队列的定义和特点

📝2️⃣栈的表示和操作的实现

📝3️⃣顺序栈的表示和实现

📝4️⃣栈的表示和实现

📖【数据结构与算法】第五章：栈的表示与操作实现

📝1️⃣栈和队列的定义和特点

✨栈的定义和特点

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。

编辑

在日常生活中，还有很多类似栈的例子。例如，洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面，而用时从上往下逐个取用。栈的操作特点正是上述实际应用的抽象。在程序设计中，如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。

✨队列的定义和特点

和栈相反，队列（queue）是一种先进先出（First In First Out，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。

编辑

这和日常生活中的排队是一致的，最早进入队列的元素最早离开。

在队列中，允许插入的一端称为队尾（rear），允许删除的一端则称为队头（front）。假设队列为q = (a1, a2,…, an)，那么，a1就是队头元素，an则是队尾元素。

队列中的元素是按照a1, a2,…, an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1, a2,…, an − 1都离开队列之后，an才能退出队列。

✨栈和队列与一般线性表的区别

栈、队列是一种特殊（操作受限）的线性表，区别在于运算规则不同。

📝2️⃣栈的表示和操作的实现

栈的基本操作除了入栈和出栈外，还有栈的初始化、栈空的判定，以及取栈顶元素等。

✨栈的抽象数据类型定义

ADT Stack｛
    数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
    数据关系：R={＜ai-1,ai＞|ai-1,ai∈D,i=2,…,n｝
    约定an端为栈顶，a1端为栈底。
//基本操作：
InitStack(&S)
//操作结果：构造一个空栈S。
DestroyStack(&S)
//初始条件：栈S已存在。
//操作结果：栈S被销毁。
ClearStack(&S)
//初始条件：栈S已存在。
//操作结果：将S清为空栈。
StackEmpty(S)
//初始条件：栈S已存在。
//操作结果：若栈S为空栈，则返回true，否则返回false。
StackLength(S)
//初始条件：栈S已存在。
//操作结果：返回S的元素个数，即栈的长度。
GetTop(S)
//初始条件：栈S已存在且非空。
//操作结果：返回S的栈顶元素，不修改栈顶指针。
Push(&S,e)
//初始条件：栈S已存在。
//操作结果：插入元素e为新的栈顶元素。
Pop(&S,&e)
//初始条件：栈S已存在且非空。
//操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse(S)
//初始条件：栈S已存在且非空。
//操作结果：从栈底到栈顶依次对S的每个数据元素进行访问。
}ADT Stack

📝3️⃣顺序栈的表示和实现

编辑

✨类型定义

#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

✨初始化

顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。

【算法步骤】

1. 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
2. 栈顶指针top初始为base，表示栈为空。
3. stacksize置为栈的最大容量MAXSIZE

【算法描述】

Status InitStack(SqStack &S)
{    //构造一个空栈S
    S.base=new SElemType[MAXSIZE]； //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    if(!S.base) 
        exit(OVERFLOW); //存储分配失败
    S.top=S.base; //top初始为base，空栈
    S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    return OK;
}

✨入栈

入栈操作是指在栈顶插入一个新的元素。

【算法步骤】

1. 判断栈是否满，若满则返回ERROR。
2. 将新元素压入栈顶，栈顶指针加1。

【算法描述】

Status Push(SqStack &S，SElemType e)
{    //插入元素e为新的栈顶元素
    if(S.top-S.base==S.stacksize) 
        return ERROR； //栈满
    *S.top++=e； //元素e压入栈顶，栈顶指针加1
    return OK；
}

✨出栈

出栈操作是将栈顶元素删除。

【算法步骤】

1. 判断栈是否空，若空则返回ERROR。
2. 栈顶指针减1，栈顶元素出栈。

【算法描述】

Status Pop(SqStack &S,SElemType &e)
{    //删除S的栈顶元素，用e返回其值
    if(S.top==S.base)
        return ERROR; //栈空
    e=*--S.top; //栈顶指针减1，将栈顶元素赋给e
    return OK;
}

✨取栈顶元素

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。

【算法描述】

SElemType GetTop(SqStack S)
{    //返回S的栈顶元素，不修改栈顶指针
    if(S.top！=S.base) //栈非空
        return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
}

由于顺序栈和顺序表一样，受到最大空间容量的限制，虽然可以在“满员”时重新分配空间扩大容量，但工作量较大，应该尽量避免。因此在应用程序无法预先估计栈可能达到的最大容量时，还是应该使用下面介绍的链栈。

📝4️⃣栈的表示和实现

链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示，如图3.4所示。链栈的结点结构与单链表的结构相同，在此用StackNode表示

编辑

✨类型定义

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

由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。

✨初始化

链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。

【算法描述】

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

✨入栈

和顺序栈的入栈操作不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间。

【算法步骤】：

1. 为入栈元素e分配空间，用指针p指向。
2. 将新结点数据域置为e。
3. 将新结点插入栈顶。
4. 修改栈顶指针为p。

【算法描述】：

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

✨出栈

和顺序栈一样，链栈在出栈前也需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间。

【算法步骤】：

1. 判断栈是否为空，若空则返回ERROR。
2. 将栈顶元素赋给e。
3. 临时保存栈顶元素的空间，以备释放。
4. 修改栈顶指针，指向新的栈顶元素。
5. 释放原栈顶元素的空间。

【算法描述】：

Status Pop(LinkStack &S,SElemType &e)
{    //删除S的栈顶元素，用e返回其值
    if(S==NULL) 
        return ERROR; //栈空
    e=S->data; //将栈顶元素赋给e
    p=S; //用p临时保存栈顶元素空间，以备释放
    S=S->next; //修改栈顶指针
    delete p; //释放原栈顶元素的空间
    return OK;
}

✨取栈顶元素

与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。

【算法描述】：

SElemType GetTop(LinkStack S)
{    //返回S的栈顶元素，不修改栈顶指针
    if(S！=NULL) //栈非空
        return S->data; //返回栈顶元素的值，栈顶指针不变
}